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

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

RIGHTS & PERMISSIONS

Higher Education Press