Labeling-based centrality approaches for identifying critical edges on temporal graphs

Abstract

Edge closeness and betweenness centralities are widely used path-based metrics for characterizing the importance of edges in networks. In general graphs, edge closeness centrality indicates the importance of edges by the shortest distances from the edge to all the other vertices. Edge betweenness centrality ranks which edges are significant based on the fraction of all-pairs shortest paths that pass through the edge. Nowadays, extensive research efforts go into centrality computation over general graphs that omit time dimension. However, numerous real-world networks are modeled as temporal graphs, where the nodes are related to each other at different time instances. The temporal property is important and should not be neglected because it guides the flow of information in the network. This state of affairs motivates the paper’s study of edge centrality computation methods on temporal graphs. We introduce the concepts of the label, and label dominance relation, and then propose multi-thread parallel labeling-based methods on OpenMP to efficiently compute edge closeness and betweenness centralities w.r.t. three types of optimal temporal paths. For edge closeness centrality computation, a time segmentation strategy and two observations are presented to aggregate some related temporal edges for uniform processing. For edge betweenness centrality computation, to improve efficiency, temporal edge dependency formulas, a labeling-based forward-backward scanning strategy, and a compression-based optimization method are further proposed to iteratively accumulate centrality values. Extensive experiments using 13 real temporal graphs are conducted to provide detailed insights into the efficiency and effectiveness of the proposed methods. Compared with state-of-the-art methods, labeling-based methods are capable of up to two orders of magnitude speedup.

Graphical abstract

Keywords

temporal graph / closeness centrality / betweenness centrality / temporal path

Tianming Zhang received the BS and MS degrees in computer science from Northeastern University, China in 2012 and 2014, respectively, and the PhD degree in computer science from Zhejiang University, China in 2020. She is currently a lecturer in the College of Computer Science, Zhejiang University of Technology, China. Her research interest includes graph data management and analysis

Jie Zhao is currently working toward the MS degree in the College of Computer Science, Zhejiang University of Technology, China. His main research interests include graph querying and processing

Cibo Yu is currently working toward the BS degree in the College of Computer Science, Zhejiang University of Technology, China. His main research interests include graph analysis and mining

Lu Chen received the PhD degree in computer science from Zhejiang University, China in 2016. She was an associate professor in Aalborg University, Denmark. She is currently a ZJU Plan 100 professor in the College of Computer Science, Zhejiang University, China. Her research interests include indexing and querying metric spaces, graph databases, and database usability

Yunjun Gao (Member, IEEE) received the PhD degree in computer science from Zhejiang University, China in 2008. He is currently a professor in the College of Computer Science, Zhejiang University, China. His research interests include spatial and spatio-temporal databases, metric and incomplete/uncertain data management, graph databases, spatio-textual data processing, and database usability. He is a member of the ACM and the IEEE

Bin Cao (Member, IEEE) received his PhD degree in computer science from Zhejiang University, China in 2013. He then worked as a research associate in Hongkong University of Science and Technology and Noah’s Ark Lab, Huawei, China. He joined Zhejiang University of Technology, China in 2014, and is now an associate professor in the College of Computer Science. His research interests include spatio-temporal database and data mining

Jing Fan received the BS, MS, and PhD degree in computer science from Zhejiang University, China in 1990, 1993, and 2003, respectively. She is currently a professor in the College of Computer Science, Zhejiang University of Technology, China. She is Vice-Director of Key Laboratory of Visual Media Intelligent Processing Technology of Zhejiang Province, China. Her current research interests include service computing, software middleware, virtual reality and visualization. She is a Director of China Computer Federation (CCF), and Member of CCF Technical Committee on Service Computing

Ge Yu (Member, IEEE) received the PhD degree in computer science from the Kyushu University of Japan in 1996. He is currently a professor and the PhD supervisor at the Northeastern University of China. His research interests include distributed and parallel database, OLAP and data warehousing, data integration, graph data management, etc. He is a member of the IEEE Computer Society, ACM, and a fellow of the China Computer Federation (CCF)

References

[1] Freeman L C . Centrality in social networks conceptual clarification. Social Networks, 1978−1979, 1( 3): 215–239

[2] Girvan M, Newman M E . Community structure in social and biological networks. Proceedings of the National Academy of Sciences of the United States of America, 2002, 99( 12): 7821–7826

[3] Pournajar M, Zaiser M, Moretti P . Edge betweenness centrality as a failure predictor in network models of structurally disordered materials. Scientific Reports, 2022, 12( 1): 11814

[4] Simone A, Ridolfi L, Laucelli D, Berardi L, Giustolisi O . Centrality metrics for water distribution networks. EPiC Series in Engineering, 2018, 3: 1979–1988

[5] Cuzzocrea A, Papadimitriou A, Katsaros D, Manolopoulos Y . Edge betweenness centrality: a novel algorithm for QoS-based topology control over wireless sensor networks. Journal of Network and Computer Applications, 2012, 35( 4): 1210–1217

[6] Ni P, Hanai M, Tan W J, Cai W. Efficient closeness centrality computation in time-evolving graphs. In: Proceedings of 2019 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. 2019, 378−385

[7] Tsalouchidou I, Baeza-Yates R, Bonchi F, Liao K, Sellis T . Temporal betweenness centrality in dynamic graphs. International Journal of Data Science and Analytics, 2020, 9( 3): 257–272

[8] Ghanem M. Temporal centralities: a study of the importance of nodes in dynamic graphs. Sorbonne Universités, Dissertation, 2018

[9] Wu H, Cheng J, Huang S, Ke Y, Lu Y, Xu Y . Path problems in temporal graphs. Proceedings of the VLDB Endowment, 2014, 7( 9): 721–732

[10] Saxena A, Iyengar S. Centrality measures in complex networks: a survey. 2020, arXiv preprint arXiv: 2011.07190

[11] Eppstein D, Wang J . Fast approximation of centrality. Journal of Graph Algorithms and Applications, 2004, 8( 1): 39–45

[12] Hoeffding W . Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 1963, 58( 301): 13–30

[13] Okamoto K, Chen W, Li X Y. Ranking of closeness centrality for large-scale social networks. In: Proceedings of the 2nd Annual International Workshop on Frontiers in Algorithmics. 2008, 186−195

[14] Cohen E, Delling D, Pajor T, Werneck R F. Computing classic closeness centrality, at scale. In: Proceedings of the 2nd ACM Conference on Online Social Networks. 2014, 37−50

[15] Olsen P W, Labouseur A G, Hwang J H. Efficient top-k closeness centrality search. In: Proceedings of the 30th IEEE International Conference on Data Engineering. 2014, 196−207

[16] Guimarães A, Vieira A B, Silva A P C, Ziviani A. Fast centrality-driven diffusion in dynamic networks. In: Proceedings of the 22nd International Conference on World Wide Web. 2013, 821−828

[17] Shao Z, Guo N, Gu Y, Wang Z, Li F, Yu G. Efficient closeness centrality computation for dynamic graphs. In: Proceedings of the 25th International Conference on Database Systems for Advanced Applications. 2020, 534−550

[18] Oettershagen L, Mutzel P. Efficient top-k temporal closeness calculation in temporal networks. In: Proceedings of 2020 IEEE International Conference on Data Mining. 2020, 402−411

[19] Oettershagen L, Mutzel P . Computing top-k temporal closeness in temporal networks. Knowledge and Information Systems, 2022, 64( 2): 507–535

[20] Bergamini E, Borassi M, Crescenzi P, Marino A, Meyerhenke H . Computing top-k closeness centrality faster in unweighted graphs. ACM Transactions on Knowledge Discovery from Data, 2019, 13( 5): 53

[21] Brandes U . A faster algorithm for betweenness centrality. The Journal of Mathematical Sociology, 2001, 25( 2): 163–177

[22] Erdős D, Ishakian V, Bestavros A, Terzi E. A divide-and-conquer algorithm for betweenness centrality. In: Proceedings of 2015 SIAM International Conference on Data Mining. 2015, 433−441

[23] Sariyüce A E, Kaya K, Saule E, Çatalyürek Ü V . Graph manipulations for fast centrality computation. ACM Transactions on Knowledge Discovery from Data, 2017, 11( 3): 26

[24] Baglioni M, Geraci F, Pellegrini M, Lastres E. Fast exact computation of betweenness centrality in social networks. In: Proceedings of 2012 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. 2012, 450−456

[25] Kanwar K, Kaushal S, Kumar H, Gupta G, Khari M . BCDCN: a new edge centrality measure to identify and rank critical edges pertaining to SIR diffusion in complex networks. Social Network Analysis and Mining, 2022, 12( 1): 49

[26] De Meo P, Ferrara E, Fiumara G, Ricciardello A . A novel measure of edge centrality in social networks. Knowledge-Based Systems, 2012, 30: 136–150

[27] Brandes U, Pich C . Centrality estimation in large networks. International Journal of Bifurcation and Chaos, 2007, 17( 7): 2303–2318

[28] Riondato M, Kornaropoulos E M. Fast approximation of betweenness centrality through sampling. In: Proceedings of the 7th ACM International Conference on Web Search and Data Mining. 2014, 413−422

[29] Cousins C, Wohlgemuth C, Riondato M. Bavarian: betweenness centrality approximation with variance-aware rademacher averages. In: Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining. 2021, 196−206

[30] Lee M J, Lee J, Park J Y, Choi R H, Chung C W. QUBE: a quick algorithm for updating betweenness centrality. In: Proceedings of the 21st International Conference on World Wide Web. 2012, 351−360

[31] Green O, McColl R, Bader D A. A fast algorithm for streaming betweenness centrality. In: Proceedings of 2012 International Conference on Privacy, Security, Risk and Trust and 2012 International Confernece on Social Computing. 2012, 11−20

[32] Kourtellis N, De Francisci Morales G, Bonchi F . Scalable online betweenness centrality in evolving graphs. IEEE Transactions on Knowledge and Data Engineering, 2015, 27( 9): 2494–2506

[33] Kas M, Wachs M, Carley K M, Carley L R. Incremental algorithm for updating betweenness centrality in dynamically growing networks. In: Proceedings of 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. 2013, 33−40

[34] Bergamini E, Meyerhenke H, Staudt C L. Approximating betweenness centrality in large evolving networks. In: Proceedings of Meeting on Algorithm Engineering & Expermiments. 2015, 133−146

[35] Hayashi T, Akiba T, Yoshida Y . Fully dynamic betweenness centrality maintenance on massive networks. Proceedings of the VLDB Endowment, 2015, 9( 2): 48–59

[36] Buß S, Molter H, Niedermeier R, Rymar M. Algorithmic aspects of temporal betweenness. In: Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2020, 2084−2092

[37] Knight W R . A computer method for calculating Kendall’s tau with ungrouped data. Journal of the American Statistical Association, 1966, 61( 314): 436–439

Acknowledgements

This work was supported by the National Natural Science Foundation of China (Grant Nos. 62302451 and 62276233), the Natural Science Foundation of Zhejiang Province of China (No. LQ22F020018), and the Key Research Project of Zhejiang Province of China (No. 2023C01048).

Competing interests

The authors declare that they have no competing interests or financial conflicts to disclose.

RIGHTS & PERMISSIONS

2025 Higher Education Press