Matteo Riondato
Eli Upfal
ABSTRACT
We present ABRA, a suite of algorithms to compute and maintain probabilistically-guaranteed, high-quality, approximations of the betweenness centrality of all nodes (or edges) on both static and fully dynamic graphs. Our algorithms use progressive random sampling and their analysis rely on Rademacher averages and pseudodimension, fundamental concepts from statistical learning theory. To our knowledge, this is the first application of these concepts to the field of graph analysis. Our experimental results show that ABRA is much faster than exact methods, and vastly outperforms, in both runtime and number of samples, state-of-the-art algorithms with the same quality guarantees.
- D. Anguita, A. Ghio, L. Oneto, and S. Ridella. A deep connection between the Vapnik-Chervonenkis entropy and the Rademacher complexity. IEEE Trans. Neural Netw. Learn. Sys., 25 (12): 2202--2211, 2014.Google Scholar
Cross Ref
- J. M. Anthonisse. The rush in a directed graph. TR BN 9/71, Stichting Mathematisch Centrum, 1971.Google Scholar
- D. A. Bader, S. Kintali, K. Madduri, and M. Mihail. Approximating betweenness centrality. Algorithms and Models for the Web-Graph, 124--137, 2007. Google ScholarDigital Library
- E. Bergamini and H. Meyerhenke. Fully-dynamic approximation of betweenness centrality. ESA'15.Google Scholar
- }BergaminiM15arXivE. Bergamini and H. Meyerhenke. Approximating betweenness centrality in fully-dynamic networks. Internet Mathematics, to appear.Google Scholar
- E. Bergamini, H. Meyerhenke, and C. L. Staudt. Approximating betweenness centrality in large evolving networks. ALENEX'15, 2015. Google ScholarDigital Library
- S. Boucheron, O. Bousquet, and G. Lugosi. Theory of classification : A survey of some recent advances. ESAIM: Probability and Statistics, 9: 323--375, 2005.Google ScholarCross Ref
- S. Boyd and L. Vandenberghe. Convex optimization. Cambridge university press, 2004. Google ScholarCross Ref
- U. Brandes. A faster algorithm for betweenness centrality. J. Math. Sociol., 25 (2): 163--177, 2001.Google ScholarCross Ref
- U. Brandes and C. Pich. Centrality estimation in large networks. Int. J. Bifurc. Chaos, 17 (7): 2303--2318, 2007.Google ScholarCross Ref
- T. Elomaa and M. Kaariainen. Progressive Rademacher sampling. AAAI '01, 2001. Google ScholarDigital Library
- D. Erdos, V. Ishakian, A. Bestavros, and E. Terzi. A divide-and-conquer algorithm for betweenness centrality. SDM'15, 2015.Google ScholarCross Ref
- L. C. Freeman. A set of measures of centrality based on betweenness. Sociometry, 40: 35--41, 1977.Google ScholarCross Ref
- R. Geisberger, P. Sanders, and D. Schultes. Better approximation of betweenness centrality. ALENEX'08, 2008. Google ScholarDigital Library
- O. Green, R. McColl, and D. Bader. A fast algorithm for streaming betweenness centrality. PASSAT'12, 2012. Google ScholarDigital Library
- T. Hayashi, T. Akiba, and Y. Yoshida. Fully dynamic betweenness centrality maintenance on massive networks. VLDB'16, 2015. Google ScholarDigital Library
- M. Kas, M. Wachs, K. M. Carley, and L. R. Carley. Incremental algorithm for updating betweenness centrality in dynamically growing networks. ASONAM'13, 2013. Google ScholarDigital Library
- N. Kourtellis, G. D. F. Morales, and F. Bonchi. Scalable online betweenness centrality in evolving graphs. IEEE Trans. Knowl. Data Eng., 27 (9): 2494--2506, 2015.Google ScholarDigital Library
- M.-J. Lee, J. Lee, J. Y. Park, R. H. Choi, and C.-W. Chung. QUBE: A quick algorithm for updating betweenness centrality. WWW'12, 2012. Google ScholarDigital Library
- J. Leskovec and A. Krevl. SNAP Datasets: Stanford large network dataset collection. http://snap.stanford.edu/data, 2014.Google Scholar
- M. E. J. Newman. Networks -- An Introduction. Oxford University Press, 2010. Google ScholarDigital Library
- L. Oneto, A. Ghio, D. Anguita, and S. Ridella. An improved analysis of the Rademacher data-dependent bound using its self bounding property. Neur. Netw., 44:0, 2013.Google ScholarCross Ref
- D. Pollard. Convergence of stochastic processes. Springer-Verlag, 1984.Google ScholarCross Ref
- M. Riondato and E. M. Kornaropoulos. Fast approximation of betweenness centrality through sampling. Data Mining Knowl. Disc., 30: (2) 438--475, 2015. Google ScholarDigital Library
- M. Riondato and E. Upfal. Approximating betweenness centrality in static and dynamic graphswith Rademacher averages (extended version) http://rionda.to/papers/RiondatoUpfal-ABRA-ext.pdf, 2016.Google Scholar
- M. Riondato and E. Upfal. Mining frequent itemsets through progressive sampling with Rademacher averages. KDD'15, 2015. Google ScholarDigital Library
- A. E. Saríyüce, E. Saule, K. Kaya, and U. V. Çatalyürek. Shattering and compressing networks for betweenness centrality. SDM'15, 2015.Google Scholar
- S. Shalev-Shwartz and S. Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014. Google ScholarCross Ref
- C. Staudt, A. Sazonovs, and H. Meyerhenke. NetworKit: A tool suite for high-performance network analysis. Network Science, to appear.Google Scholar
- V. N. Vapnik. The Nature of Statistical Learning Theory. Springer-Verlag, 1999. Google Scholar
Index Terms
- ABRA: Approximating Betweenness Centrality in Static and Dynamic Graphs with Rademacher Averages
Recommendations
ABRA: Approximating Betweenness Centrality in Static and Dynamic Graphs with Rademacher Averages
ABPA Ξ AΣ (ABRAXAS): Gnostic word of mystic meaning.
We present ABRA, a suite of algorithms to compute and maintain probabilistically guaranteed high-quality approximations of the betweenness centrality of all nodes (or edges) on both static and fully ...
Axiomatic Analysis of Medial Centrality Measures
AAMAS '23: Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent SystemsWe perform the first axiomatic analysis of medial centrality measures. These measures, also called betweenness-like centralities, assess the role of a node in connecting others in the network. We focus on a setting with one target node and several source ...
Centrality Measures on Big Graphs: Exact, Approximated, and Distributed Algorithms
WWW '16 Companion: Proceedings of the 25th International Conference Companion on World Wide WebCentrality measures allow to measure the relative importance of a node or an edge in a graph w.r.t.~other nodes or edges. Several measures of centrality have been developed in the literature to capture different aspects of the informal concept of ...
Comments