Vertex Betweenness Centrality Computation Method over Temporal Graphs

Zhang Tianming; Zhao Jie; Jin Lu; Chen Lu; Cao Bin; Fan Jing

doi:10.7544/issn1000-1239.202220650

Journal of Computer Research and Development > 2023 > 60(10): 2383-2393. > DOI: 10.7544/issn1000-1239.202220650

Zhang Tianming, Zhao Jie, Jin Lu, Chen Lu, Cao Bin, Fan Jing. Vertex Betweenness Centrality Computation Method over Temporal Graphs[J]. Journal of Computer Research and Development, 2023, 60(10): 2383-2393. DOI: 10.7544/issn1000-1239.202220650

Citation:

PDF (1338 KB)

Vertex Betweenness Centrality Computation Method over Temporal Graphs

1.
College of Computer Science and Technology, Zhejiang University of Technology, Hangzhou 310023
2.
College of Computer Science and Technology, Zhejiang University, Hangzhou 310013

Funds: This work was supported by the Natural Science Foundation of Zhejiang Province (LQ22F020018) and the Key Research and Development Project of Zhejiang Province (2023C01048).

More Information

Author Bio:
Zhang Tianming: born in 1988. PhD, lecturer. Member of CCF. Her main research interests include graph data management and deep learning

Zhao Jie: born in 1998. Master candidate. Student member of CCF. His main research interests include graph querying and processing

Jin Lu: born in 1998. Master candidate. His main research interest includes graph analysis and mining

Chen Lu: born in 1989. PhD, plan-100 professor, PhD supervisor. Member of CCF. Her main research interests include database, big data management, and AI-driven database technology

Cao Bin: born in 1985. PhD, associate professor, PhD supervisor. Member of CCF. His main research interests include spatial-temporal database and data mining

Fan Jing: born in 1969. PhD, professor, PhD supervisor. Distinguished member of CCF. Her main research interests include middleware, virtual reality and visualization
Received Date: July 23, 2022
Revised Date: January 15, 2023
Available Online: May 22, 2023

Graphical Abstract

Abstract

Abstract

In social network analysis, betweenness centrality is utilized to measure the contribution of a vertex to the network structure and is a widely used vertex importance metric. This metric evaluates the vertex importance mainly by counting the number of shortest paths through the vertices. The current studies for betweenness centrality computation mostly focus on general graphs, few focus on temporal ones. For general graphs, the betweenness centrality calculation methods are mainly designed based on the Brandes’ algorithm. The key theory is that the subpaths of a shortest path is still shortest, i.e., the optimal sub-structure property. However, temporal graphs contain temporal information, and there are various types of temporal paths that do not satisfy the optimal sub-structure property. Therefore, the theory and methods for betweenness centrality calculation on general graphs are no longer suitable for temporal graphs. In view of this, we define two types of temporal paths, i.e., strict (ascending timing order) and non-strict (non-descending timing order), and study the theory and methods for betweenness centrality on temporal graphs. An efficient two-stage iterative computing framework based on message propagation is proposed. The first stage adopts the top-down breadth-first traversal paradigm to calculate temporal shortest paths; the second stage employs the bottom-up method to calculate the contributions of the vertex’s successors and children to its betweenness centrality, and designs a message propagation based iterative accumulation method. In order to improve the efficiency and scalability, a multi-thread parallel FTBC (fast temporal betweenness centrality) algorithm based on OpenMP (open multiprocessing) framework is implemented. Using eight real temporal graphs, it’s showed that our proposed betweenness centrality calculation method has better computational performance than state-of-the-art methods in our experiment.
- temporal graph,
- betweenness centrality,
- temporal path,
- parallel processing,
- graph algorithm

FullText(HTML)

References (41)

References

[1]	Freeman L C. A set of measures of centrality based on betweenness[J]. Sociometry, 1977, 40(1): 35−41 doi: 10.2307/3033543
[2]	罗浩,闫光辉,张萌,等. 融合多元信息的多关系社交网络节点重要性研究[J]. 计算机研究与发展,2020,57(5):954−970 doi: 10.7544/issn1000-1239.2020.20190331 Luo Hao, Yan Guanghui, Zhang Meng, et al. Research on node importance fused multi-information for multi-relational social networks[J]. Journal of Computer Research and Development, 2020, 57(5): 954−970 (in Chinese) doi: 10.7544/issn1000-1239.2020.20190331
[3]	杨建祥,王朝坤,王萌,等. 全动态多维网络局部介数中心度算法[J]. 计算机学报,2015,38(9):1852−1864 doi: 10.11897/SP.J.1016.2015.01852 Yang Jianxiang, Wang Chaokun, Wang Meng, et al. Alogrithms for local betweeness centrality of fully dynamic multi-dimensional networks[J]. Chinese Journal of Computers, 2015, 38(9): 1852−1864 (in Chinese) doi: 10.11897/SP.J.1016.2015.01852
[4]	Viacava F A. Centrality of drug targets in protein networks[J]. BMC Bioinformatics, 2021, 22(1): 1−29 doi: 10.1186/s12859-020-03881-z
[5]	Girvan M, Newman M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences, 2002, 99(12): 7821−7826 doi: 10.1073/pnas.122653799
[6]	Juszczyszyn K, Kazienko P, Gabrys B. Temporal changes in local topology of an email-based social network[J]. Computing and Informatics, 2009, 28(6): 763−779
[7]	Gunturi V, Shekhar S, Joseph K, et al. Scalable computational techniques for centrality metrics on temporally detailed social network[J]. Machine Learning, 2017, 106(8): 1133−1169 doi: 10.1007/s10994-016-5583-7
[8]	Michalski R, Palus S, Kazienko P. Matching organizational structure and social network extracted from email communication [C] //Proc of the 14th Int Conf on Business Information Systems. Berlin: Springer, 2011: 197−206
[9]	Dekker A H. Network centrality and super-spreaders in infectious disease epidemiology [C] ///Proc of the 20th Int Congress on Modelling and Simulation. Christchurch, New Zealand: MSSANZ, 2013: 331−337
[10]	Zaoli S, Mazzarisi P, Lillo F. Betweenness centrality for temporal multiplexes[J]. Scientific Reports, 2021, 11(1): 1−9 doi: 10.1038/s41598-020-79139-8
[11]	Brandes U. A faster algorithm for betweenness centrality[J]. Journal of Mathematical Sociology, 2001, 25(2): 163−177 doi: 10.1080/0022250X.2001.9990249
[12]	Erdős D, Ishakian V, Bestavros A, et al. A divide-and-conquer algorithm for betweenness centrality [C] //Proc of SIAM Int Conf on Data Mining. Philadelphia, PA: SIAM, 2015: 433−441
[13]	Sariyüce A E, Kaya K, Saule E, et al. Graph manipulations for fast centrality computation[J]. ACM Transactions on Knowledge Discovery from Data, 2017, 11(3): 1−25
[14]	Baglioni M, Geraci F, Pellegrini M, et al. Fast exact computation of betweenness centrality in social networks [C] //Proc of IEEE/ACM Int Conf on Advances in Social Networks Analysis and Mining. Piscataway, NJ: IEEE, 2012: 450−456
[15]	Brandes U, Pich C. Centrality estimation in large networks[J]. International Journal of Bifurcation and Chaos, 2007, 17(7): 2303−2318 doi: 10.1142/S0218127407018403
[16]	Hoeffding W. Probability inequalities for sums of bounded random variables[J]. Journal of the American Statistical Association, 1963, 58(301): 13−30 doi: 10.1080/01621459.1963.10500830
[17]	Riondato M, Kornaropoulos E M. Fast approximation of betweenness centrality through sampling[J]. Data Mining and Knowledge Discovery, 2016, 30(2): 438−475 doi: 10.1007/s10618-015-0423-0
[18]	Vapnik V N, Chervonenkis A Y. On the uniform convergence of relative frequencies of events to their probabilities[J]. Theory of Probability and Its Applications, 1971, 16(2): 264−280 doi: 10.1137/1116025
[19]	Borassi M, Natale E. KADABRA is an adaptive algorithm for betweenness via random approximation[J]. Journal of Experimental Algorithmics, 2019, 24(1): 1−35
[20]	Riondato M, Upfal E. ABRA: Approximating betweenness centrality in static and dynamic graphs with rademacher averages[J]. ACM Transactions on Knowledge Discovery from Data, 2018, 12(5): 1−38
[21]	Cousins C, Wohlgemuth C, Riondato M. BAVARIAN: Betweenness centrality approximation with variance-aware rademacher averages [C] //Proc of the 27th ACM SIGKDD Conf on Knowledge Discovery & Data Mining. New York: ACM, 2021: 196−206
[22]	Vapnik V. Statistical Learning Theory [M]. Hoboken, NJ: John Wiley & Sons, 1998
[23]	Pellegrina L, Vandin F. SILVAN: Estimating betweenness centralities with progressive sampling and non-uniform rademacher bounds[J]. arXiv preprint, arXiv: 2106.03462, 2021
[24]	Lee M J, Lee J, Park J Y, et al. QUBE: A quick algorithm for updating betweenness centrality [C] //Proc of the 21st Int Conf on World Wide Web. New York: ACM, 2012: 351−360
[25]	Green O, Mccoll R, Bader D A. A fast algorithm for streaming betweenness centrality [C] //Proc of Int Conf on Privacy, Security, Risk and Trust and Int Conf on Social Computing. Piscataway, NJ: IEEE, 2012: 11−20
[26]	Kourtellis N, Morales G D F, Bonchi F. Scalable online betweenness centrality in evolving graphs[J]. IEEE Transactions on Knowledge and Data Engineering, 2015, 27(9): 2494−2506 doi: 10.1109/TKDE.2015.2419666
[27]	Kas M, Wachs M, Carley K M, et al. Incremental algorithm for updating betweenness centrality in dynamically growing networks [C] //Proc of IEEE/ACM Int Conf on Advances in Social Networks Analysis and Mining. Piscataway, NJ: IEEE, 2013: 33−40
[28]	Ramalingam G, Reps T. An incremental algorithm for a generalization of the shortest-path problem[J]. Journal of Algorithms, 1996, 21(2): 267−305 doi: 10.1006/jagm.1996.0046
[29]	Bergamini E, Meyerhenke H, Staudt C L. Approximating betweenness centrality in large evolving networks [C] //Proc of the 17th Workshop on Algorithm Engineering and Experiments. Philadelphia, PA: SIAM, 2014: 133−146
[30]	Hayashi T, Akiba T, Yoshida Y. Fully dynamic betweenness centrality maintenance on massive networks[J]. Proceedings of the VLDB Endowment, 2015, 9(2): 48−59 doi: 10.14778/2850578.2850580
[31]	Buß S, Molter H, Niedermeier R, et al. Algorithmic aspects of temporal betweenness [C] //Proc of the 26th ACM SIGKDD Int Conf on Knowledge Discovery & Data Mining. New York: ACM, 2020: 2084−2092
[32]	Tsalouchidou I, Baeza-Yates R, Bonchi F, et al. Temporal betweenness centrality in dynamic graphs[J]. International Journal of Data Science and Analytics, 2020, 9(3): 257−272 doi: 10.1007/s41060-019-00189-x
[33]	Isella L, Stehlé J, Barrat A, et al. What's in a crowd? Analysis of face-to-face behavioral networks[J]. Journal of Theoretical Biology, 2011, 271(1): 166−180 doi: 10.1016/j.jtbi.2010.11.033
[34]	Fournet J, Barrat A. Contact patterns among high school students[J]. PloS One, 2014, 9(9): e107878 doi: 10.1371/journal.pone.0107878
[35]	Gemmetto V, Barrat A, Cattuto C. Mitigation of infectious disease at school: Targeted class closure vs school closure[J]. BMC Infectious Diseases, 2014, 14(1): 1−10 doi: 10.1186/1471-2334-14-1
[36]	Stehlé J, Voirin N, Barrat A, et al. High-resolution measurements of face-to-face contact patterns in a primary school[J]. PloS One, 2011, 6(8): e23176 doi: 10.1371/journal.pone.0023176
[37]	Vanhems P, Barrat A, Cattuto C, et al. Estimating potential infection transmission routes in hospital wards using wearable proximity sensors[J]. PloS One, 2013, 8(9): e73970 doi: 10.1371/journal.pone.0073970
[38]	Jérôme K. The KONECT Project [EB/OL]. 2013[2022-01-03]. http:// konect.uni-koblenz.de
[39]	ISI Foundation. SocioPatterns [EB/OL]. 2008[2022-01-03]. http://www. sociopatterns.org/datasets
[40]	Buß S, Molter H, Niedermeier R, et al. Temporal betweenness source code [CP/OL]. 2020[2022-01-10].https://fpt.akt.tu-berlin.de/software/ temporal_betweenness
[41]	Tsalouchidou I, Baeza-Yates R, Bonchi F, et al. TBC source code [CP/OL]. 2018[2022-01-10].https://goo.gl/PAAJvp

[1]	Wang Jingjing, Wang Yanhao, Jiang Wenjun, Zeng Yifu, Zhu Tuanfei. Fast Algorithm for Approximate Motif Counting in Temporal Graph Streams[J]. Journal of Computer Research and Development, 2025, 62(3): 709-719. DOI: 10.7544/issn1000-1239.202330788
[2]	Xue Xin, Zhu Tianchen, Sun Qingyun, Zhou Haoyi, Li Jianxin. Efficient Subgraph Matching Algorithm with Graph Neural Network[J]. Journal of Computer Research and Development, 2025, 62(3): 694-708. DOI: 10.7544/issn1000-1239.202330732
[3]	Zhang Tianming, Xu Yiheng, Cai Xinwei, Fan Jing. A Shortest Path Query Method over Temporal Graphs[J]. Journal of Computer Research and Development, 2022, 59(2): 362-375. DOI: 10.7544/issn1000-1239.20210893
[4]	Zhang Chenglong, Cao Huawei, Wang Guobo, Hao Qinfen, Zhang Yang, Ye Xiaochun, Fan Dongrui. Efficient Optimization of Graph Computing on High-Throughput Computer[J]. Journal of Computer Research and Development, 2020, 57(6): 1152-1163. DOI: 10.7544/issn1000-1239.2020.20200115
[5]	Gu Yu, Yang Jiaxue, Bao Yubin, Yu Ge. Vertex-Driven Parallel Minimum Spanning Tree Algorithms on Large Graphs[J]. Journal of Computer Research and Development, 2014, 51(12): 2688-2701. DOI: 10.7544/issn1000-1239.2014.20131331
[6]	Chai Xiaolong, Jiang Yunfei, Chen Aixiang. Ant Colony Planning Algorithm Based on Planning Graph[J]. Journal of Computer Research and Development, 2009, 46(9): 1471-1479.
[7]	Liu Yi, Zhang Xin, Li He, Qian Depei. A Heuristic Task Allocation Algorithm for Multi-Core Based Parallel Systems[J]. Journal of Computer Research and Development, 2009, 46(6): 1058-1064.
[8]	Wu Lihua, Chen Aixiang, Jiang Yunfei. Using Genetic Algorithm to Solve Temporal Planning Problems Under the Framework of the Planning Graph[J]. Journal of Computer Research and Development, 2008, 45(6).
[9]	Lin Jiao, Chen Wenguang, Li Qiang, Zheng Weimin, Zhang Yimin. A New Data Clustering Algorithm for Parallel Whole-Genome Shotgun Sequence Assembly[J]. Journal of Computer Research and Development, 2006, 43(8): 1323-1329.
[10]	Wang Jinling, Jin Beihong, and Li Jing. An Efficient Matching Algorithm for RDF Graph Patterns[J]. Journal of Computer Research and Development, 2005, 42(10): 1763-1770.