Exact and Approximate Algorithms for Computing Betweenness Centrality in Directed Graphs

• Autorzy: Chehreghani Mostafa Haghir , Bifet, Albert , Abdessalem Talel

Identyfikatory

DOI

10.3233/FI-2021-2071

• Języki publikacji: EN

Abstrakty

EN

Graphs (networks) are an important tool to model data in different domains. Real- world graphs are usually directed, where the edges have a direction and they are not symmetric. Betweenness centrality is an important index widely used to analyze networks. In this paper, first given a directed network G and a vertex r ∈ V (G), we propose an exact algorithm to compute betweenness score of r. Our algorithm pre-computes a set RV(r), which is used to prune a huge amount of computations that do not contribute to the betweenness score of r. Time com- plexity of our algorithm depends on |RV(r)| and it is respectively Θ(|RV(r)| · |E(G)|) and Θ(|RV(r)| · |E(G)| + |RV(r)| · |V (G)| log |V (G)|) for unweighted graphs and weighted graphs with positive weights. |RV(r)| is bounded from above by |V (G)| − 1 and in most cases, it is a small constant. Then, for the cases where RV(r) is large, we present a simple randomized algo- rithm that samples from RV(r) and performs computations for only the sampled elements. We show that this algorithm provides an (ǫ, δ)-approximation to the betweenness score of r. Finally, we perform extensive experiments over several real-world datasets from different domains for several randomly chosen vertices as well as for the vertices with the highest betweenness scores. Our experiments reveal that for estimating betweenness score of a single vertex, our algorithm

Słowa kluczowe

EN

Computer Science; Data Structures and Algorithms; Social and Information Networks

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2021
• Tom: Vol. 182, nr 3
• Strony: 219--242
• Opis fizyczny: Bibliogr. 41poz., rys., tab.

Twórcy

autor

Chehreghani Mostafa Haghir

• Department of Computer Engineering Amirkabir University of Technology (Tehran Polytechnic), Iran [e-mail].i

autor

Bifet, Albert

• LTCI, T´el´ecom-Paris IP-Paris, France

autor

Abdessalem Talel

• LTCI, T´el´ecom-Paris IP-Paris, France

Bibliografia

• [1] Newman MEJ. The structure and function of complex networks. SIAM REVIEW, 2003. 45:167-256. doi:10.1137/S003614450342480.
• [2] Freeman LC. A set of measures of centrality based upon betweenness, Sociometry. Social Networks, 1977. 40:35-41. doi:10.2307/3033543.
• [3] Girvan M, Newman MEJ. Community structure in social and biological networks. Natl. Acad. Sci. USA, 2002. 99:7821-7826. doi:10.1073/pnas.122653799.
• [4] Brandes U. A faster algorithm for betweenness centrality. Journal of Mathematical Sociology, 2001. 25(2):163-177. doi:10.1080/0022250X.2001.9990249.
• [5] Wang Y, Di Z, Fan Y. Identifying and Characterizing Nodes Important to Community Structure Using the Spectrum of the Graph. PLoS ONE, 2011. 6(11):e27418. doi:10.1371/journal.pone.0027418
• [6] Agarwal M, Singh RR, Chaudhary S, Iyengar SRS. An Efficient Estimation of a Node’s Betweenness. In: Mangioni G, Simini F, Uzzo SM, Wang D (eds.), Complex Networks VI - Proceedings of the 6th Workshop on Complex Networks CompleNet 2015, New York City, USA, March 25-27, 2015, volume 597 of Studies in Computational Intelligence. Springer. ISBN 978-3-319-16111-2, 2015 pp. 111-121. doi:10.1007/978-3-319-16112-9\11.
• [7] Agarwal M, Singh RR, Chaudhary S, Iyengar S. Betweenness Ordering Problem : An Efficient Non-Uniform Sampling Technique for Large Graphs. CoRR, 2014. abs/1409.6470. URL http://arxiv.org/abs/1409.6470.
• [8] Stergiopoulos G, Kotzanikolaou P, Theocharidou M, Gritzalis D. Risk mitigation strategies for critical in-frastructures based on graph centrality analysis. International Journal of Critical Infrastructure Protection, 2015. 10:34 - 44. doi:10.1016/j.ijcip.2015.05.003.
• [9] Chehreghani MH. An Efficient Algorithm for Approximate Betweenness Centrality Computation. Comput. J., 2014. 57(9):1371-1382. doi:10.1093/comjnl/bxu003.
• [10] Malighetti G, Martini G, Paleari S, Redondi R. The Impacts of Airport Centrality in the EU Network and Inter- Airport Competition on Airport Efficiency. MPRA Paper 17673, University Library of Munich,Germany, 2009. URL https://ideas.repec.org/p/pra/mprapa/17673.html.
• [11] Bergamini E, Crescenzi P, D’Angelo G, Meyerhenke H, Severini L, Velaj Y. Improving the Betweenness Centrality of a Node by Adding Links. ACM Journal of Experimental Algorithmics, 2018. 23. URL https://dl.acm.org/citation.cfm?id=3166071.
• [12] Riondato M, Kornaropoulos EM. Fast approximation of betweenness centrality through sampling. Data Mining and Knowledge Discovery, 2016. 30(2):438-475. doi:10.1007/s10618-015-0423-0.
• [13] Chehreghani MH, Bifet A, Abdessalem T. Efficient Exact and Approximate Algorithms for Computing Betweenness Centrality in Directed Graphs. In: 22nd Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD. 2018 URL http://arxiv.org/abs/1708.08739.
• [14] Cataly¨urek ¨UV, Kaya K, Sariy¨uce AE, Saule E. Shattering and Compressing Networks for Betweenness Centrality. In: Proceedings of the 13th SIAM International Conference on Data Mining, May 2-4, 2013 Austin, Texas, USA. SIAM. ISBN 978-1-61197-262-7, 2013 pp. 686-694. doi:10.1137/1.9781611972832.76.
• [15] Holme P. Congestion and centrality in traffic flow on complex networks. Adv. Complex. Syst., 2003. 6(2):163-176. doi:10.1142/S0219525903000803.
• [16] Barthelemy M. Betweenness centrality in large complex networks. The Europ. Phys. J. B – Condensed Matter, 2004. 38(2):163-168. doi:10.1140/epjb/e2004-00111-4.
• [17] Barabasi AL, Albert R. Emergence of scaling in random networks. Science, 1999. 286:509-512.
• [18] Furno A, Faouzi NE, Sharma R, Zimeo E. Two-level clustering fast betweenness centrality computation for requirement-driven approximation. In: Nie J, Obradovic Z, Suzumura T, Ghosh R, Nambiar R, Wang C, Zang H, Baeza-Yates R, Hu X, Kepner J, Cuzzocrea A, Tang J, Toyoda M (eds.), 2017 IEEE International Conference on Big Data, BigData 2017, Boston, MA, USA, December 11-14, 2017. IEEE Computer Society, 2017 pp. 1289-1294. doi:10.1109/BigData.2017.8258057.
• [19] Everett M, Borgatti S. The centrality of groups and classes. Journal of Mathematical Sociology, 1999. 23(3):181-201.
• [20] Kolaczyk ED, Chua DB, Barthelemy M. Group-betweenness and co-betweenness: Inter-related notions of coalition centrality. Social Networks, 2009. 31(3):190-203. doi:10.1016/j.socnet.2009.02.003.
• [21] Chehreghani MH. Effective co-betweenness centrality computation. In: Seventh ACM International Conference on Web Search and Data Mining (WSDM). 2014 pp. 423-432. doi:10.1145/2556195.2556263.
• [22] Puzis R, Elovici Y, Dolev S. Fast algorithm for successive computation of group betweenness centrality. Phys. Rev. E, 2007. 76(5):056709. doi:10.1103/PhysRevE.76.056709.
• [23] Puzis R, Elovici Y, Dolev S. Finding the most prominent group in complex networks. AI Commun., 2007. 20(4):287-296.
• [24] Chehreghani MH, Bifet A, Abdessalem T. An In-depth Comparison of Group Betweenness Centrality Estimation Algorithms. In: Abe N, Liu H, Pu C, Hu X, Ahmed NK, Qiao M, Song Y, Kossmann D, Liu B, Lee K, Tang J, He J, Saltz JS (eds.), IEEE International Conference on Big Data, Big Data 2018, Seattle, WA, USA, December 10-13, 2018. IEEE, 2018 pp. 2104-2113. doi:10.1109/BigData.2018.8622133.
• [25] Brandes U, Pich C. Centrality estimation in large networks. Intl. Journal of Bifurcation and Chaos, 2007. 17(7):303-318.
• [26] Bader DA, Kintali S, Madduri K, Mihail M. Approximating betweenness centrality. In: Proceedings of 5th International Conference on Algorithms and Models for the Web-Graph (WAW). 2007 pp. 124-137. doi:10.1007/978-3-540-77004-6 10.
• [27] Geisberger R, Sanders P, Schultes D. Better approximation of betweenness centrality. In: Proceedings of the Tenth Workshop on Algorithm Engineering and Experiments (ALENEX). 2008 pp. 90-100.
• [28] Vapnik VN, Chervonenkis AY. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probab. and its Applications, 1971. 16(2):264-280.
• [29] Riondato M, Upfal E. ABRA: Approximating Betweenness Centrality in Static and Dynamic Graphs with Rademacher Averages. In: Proceedings of the 22Nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’16. ACM, New York, NY, USA. ISBN 978-1-4503-4232-2, 2016 pp. 1145-1154. doi:10.1145/2939672.2939770.
• [30] Shalev-Shwartz S, Ben-David S. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, New York, NY, USA, 2014. ISBN 1107057132, 9781107057135.
• [31] Borassi M, Natale E. KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation. In: Sankowski P, Zaroliagis CD (eds.), 24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark, volume 57 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. ISBN 978-3-95977-015-6, 2016 pp. 20:1-20:18. doi:10.4230/LIPIcs.ESA.2016.20.
• [32] Chehreghani MH, Abdessalem T, Bifet A. Metropolis-Hastings Algorithms for Estimating Betweenness Centrality. In: Herschel M, Galhardas H, Reinwald B, Fundulaki I, Binnig C, Kaoudi Z (eds.), Advances in Database Technology - 22nd International Conference on Extending Database Technology, EDBT 2019, Lisbon, Portugal, March 26-29, 2019. OpenProceedings.org, 2019 pp. 686-689. doi:10.5441/002/edbt.2019.87.
• [33] Lee MJ, Lee J, Park JY, Choi RH, Chung CW. QUBE: A quick algorithm for updating betweenness centrality. In: Proceedings of the 21st World Wide Web Conference (WWW). 2012 pp. 351-360.
• [34] Bergamini E, Meyerhenke H, Staudt C. Approximating Betweenness Centrality in Large Evolving Networks. In: Brandes U, Eppstein D (eds.), Proceedings of the Seventeenth Workshop on Algorithm Engineering and Experiments, ALENEX 2015, San Diego, CA, USA, January 5, 2015. SIAM. ISBN 978-1-61197-375-4, 2015 pp. 133-146. doi:10.1137/1.9781611973754.12.
• [35] Hayashi T, Akiba T, Yoshida Y. Fully Dynamic Betweenness Centrality Maintenance on Massive Networks. Proceedings of the VLDB Endowment (PVLDB), 2015. 9(2):48-59. URL http://www.vldb.org/pvldb/vol9/p48-hayashi.pdf.
• [36] Haghir Chehreghani M. Dynamical algorithms for data mining and machine learning over dynamic graphs.
• WIREs Data Mining and Knowledge Discovery, 2021. 11(2):e1393. doi:10.1002/widm.1393.
• [37] Hoeffding W. Probability Inequalities for Sums of Bounded Random Variables. Journal of the American Statistical Association, 1963. 58(301):13-30. URL http://www.jstor.org/stable/2282952?
• [38] Leskovec J, Adamic LA, Huberman BA. The dynamics of viral marketing. ACM Transactions on the Web (TWEB), 2007. 1(1). doi:10.1145/1232722.1232727.
• [39] Yang J, Leskovec J. Defining and Evaluating Network Communities Based on Ground-Truth. In: Zaki MJ, Siebes A, Yu JX, Goethals B, Webb GI, Wu X (eds.), 12th IEEE International Conference on Data Mining, ICDM 2012, Brussels, Belgium, December 10-13, 2012. IEEE Computer Society. ISBN 978-1-4673-4649-8, 2012 pp. 745-754. doi:10.1109/ICDM.2012.138.
• [40] Leskovec J, Kleinberg JM, Faloutsos C. Graph evolution: Densification and shrinking diameters. ACM Transactions on Knowledge Discovery from Data (TKDD), 2007. 1(1). doi:10.1145/1217299.1217301. URL http://doi.acm.org/10.1145/1217299.1217301.
• [41] Leskovec J, Huttenlocher DP, Kleinberg JM. Signed networks in social media. In: Mynatt ED, Schoner D, Fitzpatrick G, Hudson SE, Edwards WK, Rodden T (eds.), Proceedings of the 28th International Conference on Human Factors in Computing Systems, CHI 2010, Atlanta, Georgia, USA, April 10-15, 2010. ACM. ISBN 978-1-60558-929-9, 2010 pp. 1361-1370. doi:10.1145/1753326.1753532.

Uwagi

Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023). (PL)