×

Efficient algorithms for updating betweenness centrality in fully dynamic graphs. (English) Zbl 1390.05226

Summary: Betweenness centrality of a vertex (edge) in a graph is a measure for the relative participation of the vertex (edge) in the shortest paths in the graph. Betweenness centrality is widely used in various areas such as biology, transportation, and social networks. In this paper, we study the update problem of betweenness centrality in fully dynamic graphs. The proposed update algorithm substantially reduces the number of shortest paths which should be re-computed when a graph is changed. In addition, we adapt a community detection algorithm using the proposed algorithm to show how much benefit can be obtained from the proposed algorithm in a practical application. Experimental results on real graphs show that the proposed algorithm efficiently update betweenness centrality and detect communities in a graph.

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
05C82 Small world graphs, complex networks (graph-theoretic aspects)

Software:

Algorithm 447
PDFBibTeX XMLCite
Full Text: DOI

References:

[6] Anthonisse, J., Stichting Mathematisch Centrum/1Amsterdam. Afdeling Mathematische besliskunde, The Rush in a Directed Graph, Technical report (1971)
[7] Backes, A. R.; Bruno, O. M., Polygonal approximation of digital planar curves through vertex betweenness, Inf. Sci., 222, 795-804 (2013) · Zbl 1293.68280
[8] Bader, D. A.; Kintali, S.; Madduri, K.; Mihail, M., Approximating betweenness centrality, Proceedings of the Fifth International Conference on Algorithms and Models for the Web-graph. Proceedings of the Fifth International Conference on Algorithms and Models for the Web-graph, WAW’07, 124-137 (2007), Springer-Verlag: Springer-Verlag Berlin, Heidelberg · Zbl 1136.68320
[9] Bader, D. A.; Madduri, K., Parallel algorithms for evaluating centrality indices in real-world networks, Proceedings of the 2006 International Conference on Parallel Processing. Proceedings of the 2006 International Conference on Parallel Processing, ICPP ’06, 539-550 (2006), IEEE Computer Society: IEEE Computer Society Washington, DC, USA
[10] Bhowmick, S.; Rykov, V. V.; Ufimtsev, V., ACM SRC poster: a scalable group testing based algorithm for finding d-highest betweenness centrality vertices in large scale networks, SC Companion, 121-122 (2011)
[11] Boguñá, M.; Pastor-Satorras, R.; Diaz-Guilera, A.; Arenas, A., Models of social networks based on social distance attachment, Phys. Rev. E, 70, 5, 056122 (2004)
[12] Brandes, U., A faster algorithm for betweenness centrality, J. Math. Sociol., 25, 1994, 163-177 (2001) · Zbl 1051.91088
[13] Brandes, U., On variants of shortest-path betweenness centrality and their generic computation, Soc. Netw., 30, 2, 136-145 (2008)
[14] Brandes, U.; Pich, C., Centrality estimation in large networks, Int. J. Bifurc. Chaos, 17, 7, 2303 (2007) · Zbl 1143.05304
[15] Brass, D. J., Being in the right place: a structural analysis of individual influence in an organization, Admin. Sci. Quart., 29, 4, 518-539 (1984)
[16] Demetrescu, C.; Italiano, G. F., A new approach to dynamic all pairs shortest paths, J. ACM, 51, 6, 968-992 (2004) · Zbl 1125.68393
[17] Demetrescu, C.; Italiano, G. F., Experimental analysis of dynamic all pairs shortest path algorithms, ACM Trans. Algor. (TALG), 2, 4, 578-601 (2006) · Zbl 1321.05257
[18] Dolev, S.; Elovici, Y.; Puzis, R., Routing betweenness centrality, J. ACM, 57, 4, 25:1-25:27 (2010) · Zbl 1327.68027
[19] Dunn, R.; Dudbridge, F.; Sanderson, C. M., The use of edge-betweenness clustering to investigate biological function in protein interaction networks, BMC Bioinform., 6, 1, 39 (2005)
[20] Fleming, D. K.; Hayuth, Y., Spatial characteristics of transportation hubs: centrality and intermediacy, J. Transp. Geogr., 2, 1, 3-18 (1994)
[21] Fredman, M. L.; Tarjan, R. E., Fibonacci heaps and their uses in improved network optimization algorithms, J. ACM, 34, 3, 596-615 (1987) · Zbl 1412.68048
[22] Freeman, L. C., A set of measures of centrality based on betweenness, Sociometry, 40, 1, 35-41 (1977)
[23] Freeman, L. C.; Borgatti, S. P.; White, D. R., Centrality in valued graphs: a measure of betweenness based on network flow, Soc. Netw., 13, 2, 141-154 (1991)
[24] Geisberger, R.; Sanders, P.; Schultes, D., Better approximation of betweenness centrality., (Munro, J. I.; Wagner, D., ALENEX (2008), SIAM), 90-100 · Zbl 1428.68213
[25] Goel, K.; Singh, R. R.; Iyengar, S.; Sukrit, A faster algorithm to update betweenness centrality after node alteration, WAW, 170-184 (2013) · Zbl 1342.05032
[26] Goh, K.-I.; Cusick, M. E.; Valle, D.; Childs, B.; Vidal, M.; Barabási, A.-L., The human disease network, Proceedings of the National Academy of Sciences, 104, 21, 8685-8690 (2007)
[27] Green, O.; McColl, R.; Bader, D. A., A fast algorithm for streaming betweenness centrality, SocialCom/PASSAT, 11-20 (2012)
[28] Holme, P., Congestion and centrality in traffic flow on complex networks, Adv. Complex Syst., 6, 2, 163-176 (2003) · Zbl 1203.90047
[29] Hopcroft, J.; Tarjan, R., Algorithm 447: efficient algorithms for graph manipulation, Commun. ACM, 16, 6, 372-378 (1973)
[30] Jin, S.; Huang, Z.; Chen, Y.; Chavarria-Miranda, D. G.; Feo, J.; Wong, P. C., A novel application of parallel betweenness centrality to power grid contingency analysis., IPDPS, 1-7 (2010), IEEE
[31] Kang, U.; Papadimitriou, S.; Sun, J.; Tong, H., Centralities in large networks: algorithms and observations, SDM, 119-130 (2011)
[32] Kas, M.; Wachs, M.; Carley, K. M.; Carley, L. R., Incremental algorithm for updating betweenness centrality in dynamically growing networks, ASONAM, 33-40 (2013)
[33] Kolaczyk, E. D.; Chua, D. B.; Barthélemy, M., Group betweenness and co-betweenness: inter-related notions of coalition centrality, Soc. Netw., 31, 3, 190-203 (2009)
[34] Koschützki, D.; Lehmann, K. A.; Peeters, L.; Richter, S.; Tenfelde-Podehl, D.; Zlotowski, O., Centrality indices, Network Analysis, 16-61 (2004) · Zbl 1118.68330
[35] Kourtellis, N.; Alahakoon, T.; Simha, R.; Iamnitchi, A.; Tripathi, R., Identifying high betweenness centrality nodes in large social networks, Soc. Netw. Anal. Mining, 3, 4, 899-914 (2013)
[36] Lammer, S.; Gehlsen, B.; Helbing, D., Scaling laws in the spatial structure of urban road networks, Phys. A: Stat. Mech. Appl., 363, 1, 89-95 (2006)
[37] Lee, M.-J.; Chung, C.-W., Finding \(k\)-highest betweenness centrality vertices in graphs, Proceedings of the Companion Publication of the 23rd International Conference on World Wide Web. Proceedings of the Companion Publication of the 23rd International Conference on World Wide Web, WWW Companion ’14, 339-340 (2014)
[38] Lee, M.-J.; Lee, J.; Park, J. Y.; Choi, R. H.; Chung, C.-W., QUBE: a quick algorithm for updating betweenness centrality, Proceedings of the 21st International Conference on World Wide Web, 351-360 (2012), ACM
[39] Leskovec, J.; Kleinberg, J.; Faloutsos, C., Graph evolution: densification and shrinking diameters, ACM Trans. Knowl. Discov. Data, 1, 1, 2 (2007)
[40] Leydesdorff, L., Betweenness centrality as an indicator of the interdisciplinarity of scientific journals, J. Am. Soc. Inf. Sci. Technol., 58, 9, 1303-1309 (2009)
[41] Moon, S.; Lee, J.-G.; Kang, M., Scalable community detection from networks by computing edge betweenness on mapreduce, International Conference on Big Data and Smart Computing, BIGCOMP 2014, Bangkok, Thailand, January 15-17, 2014, 145-148 (2014)
[43] Newman, M. E.J., A measure of betweenness centrality based on random walks, Soc. Netw., 27, 1, 39-54 (2005)
[44] Newman, M. E.J.; Girvan, M., Finding and evaluating community structure in networks, Phys. Rev. E, 69, 2, 26113 (2004)
[46] Olsen, P. W.; Labouseur, A. G.; Hwang, J.-H., Efficient top-\(k\) closeness centrality search, IEEE 30th International Conference on Data Engineering, Chicago, ICDE 2014, IL, USA, March 31-April 4, 2014, 196-207 (2014)
[47] Pinney, J. W.; Westhead, D. R., Betweenness-based decomposition methods for social and biological networks, Interdisciplinary Statistics and Bioinformatics, 87-90 (2006), Leeds University Press
[48] Ramalingam, G.; Reps, T., On the Computational Complexity of Incremental Algorithms (1991), University of Wisconsin-Madison. Computer Sciences Department
[49] Thorup, M., Worst-case update times for fully-dynamic all-pairs shortest paths, Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of Computing. Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of Computing, STOC ’05, 112-119 (2005), ACM: ACM New York, NY, USA · Zbl 1192.68493
[50] Zhuge, H., Communities and emerging semantics in semantic link network: discovery and learning, IEEE Trans. Knowl. Data Eng., 21, 6, 785-799 (2009)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.