Document Open Access Logo

KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation

Authors Michele Borassi, Emanuele Natale

PDF

File

Thumbnail PDF
PDF
LIPIcs.ESA.2016.20.pdf
  • Filesize: 0.69 MB
  • 18 pages

Document Identifiers

Subject Classification

Keywords
  • Betweenness centrality
  • shortest path algorithm
  • graph mining
  • sampling
  • network analysis

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

We present KADABRA, a new algorithm to approximate betweenness centrality in directed and undirected graphs, which significantly outperforms all previous approaches on real-world complex networks.
The efficiency of the new algorithm relies on two new theoretical contributions, of independent interest.

The first contribution focuses on sampling shortest paths, a subroutine used by most algorithms that approximate betweenness centrality. We show that, on realistic random graph models, we can perform this task in time |E|^{1/2+o(1)} with high probability, obtaining a significant speedup with respect to the Theta(|E|) worst-case performance. We experimentally show that this new technique achieves similar speedups on real-world complex networks, as well.

The second contribution is a new rigorous application of the adaptive sampling technique. This approach decreases the total number of shortest paths that need to be sampled to compute all betweenness centralities with a given absolute error, and it also handles more general problems, such as computing the k most central nodes. Furthermore, our analysis is general, and it might be extended to other settings, as well.

Cite As Get BibTex

Michele Borassi and Emanuele Natale. KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 20:1-20:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ESA.2016.20

Author Details

Michele Borassi
Emanuele Natale

References

  1. Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, apsp and diameter. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1681-1697. SIAM, 2015. Google Scholar
  2. Amir Abboud, Virginia V. Williams, and Joshua Wang. Approximation and fixed parameter subquadratic algorithms for radius and diameter. In Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 377-391, may 2016. URL: http://arxiv.org/abs/1506.0179.
  3. Ankit Aggarwal, Amit Deshpande, and Ravi Kannan. Adaptive Sampling for k-Means Clustering. In Irit Dinur, Klaus Jansen, Joseph Naor, and José Rolim, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, number 5687 in Lecture Notes in Computer Science. Springer Berlin Heidelberg, 2009. Google Scholar
  4. Jac M Anthonisse. The rush in a directed graph. Stichting Mathematisch Centrum. Mathematische Besliskunde, BN(9/71):1-10, 1971. Google Scholar
  5. David A. Bader, Shiva Kintali, Kamesh Madduri, and Milena Mihail. Approximating betweenness centrality. The 5th Workshop on Algorithms and Models for the Web-Graph, 2007. Google Scholar
  6. Alex Bavelas. A mathematical model for group structures. Human organization, 7(3):16-30, 1948. Google Scholar
  7. Elisabetta Bergamini. private communication, 2016. Google Scholar
  8. Elisabetta Bergamini and Henning Meyerhenke. Fully-dynamic approximation of betweenness centrality. In ESA, 2015. Google Scholar
  9. Béla Bollobás. A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. European Journal of Combinatorics, 1(4):311-316, 1980. URL: http://dx.doi.org/10.1016/S0195-6698(80)80030-8.
  10. Michele Borassi, Pierluig Crescenzi, and Michel Habib. Into the square - On the complexity of some quadratic-time solvable problems. In Proceedings of the 16th Italian Conference on Theoretical Computer Science (ICTCS), pages 1-17, 2015. Google Scholar
  11. Michele Borassi, Pierluigi Crescenzi, and Luca Trevisan. An Axiomatic and an Average-Case Analysis of Algorithms and Heuristics for Metric Properties of Graphs. arXiv:1604.01445 [cs], April 2016. Google Scholar
  12. Michele Borassi and Emanuele Natale. Kadabra is an adaptive algorithm for betweenness via random approximation. arXiv preprint arXiv:1604.08553, 2016. Google Scholar
  13. Stephen P. Borgatti and Martin G. Everett. A graph-theoretic perspective on centrality. Social Networks, 28:466-484, 2006. Google Scholar
  14. Ulrik Brandes. A faster algorithm for betweenness centrality. The Journal of Mathematical Sociology, 25(2):163-177, jun 2001. URL: http://dx.doi.org/10.1080/0022250X.2001.9990249.
  15. Ulrik Brandes. On variants of shortest-path betweenness centrality and their generic computation. Social Networks, 30:136-145, 2008. Google Scholar
  16. Ulrik Brandes and Christian Pich. Centrality Estimation in Large Networks. International Journal of Bifurcation and Chaos, 17(07):2303-2318, 2007. URL: http://dx.doi.org/10.1142/S0218127407018403.
  17. Bernard S Cohn and McKim Marriott. Networks and centres of integration in indian civilization. Journal of social Research, 1(1):1-9, 1958. Google Scholar
  18. Shlomi Dolev, Yuval Elovici, and Rami Puzis. Routing betweenness centrality. J. ACM, 57, 2010. Google Scholar
  19. David A. Easley and Jon M. Kleinberg. Networks, crowds, and markets - reasoning about a highly connected world. In DAGLIB, 2010. Google Scholar
  20. David Eppstein and Joseph Wang. Fast approximation of centrality. J. Graph Algorithms Appl., 8:39-45, 2001. Google Scholar
  21. Dóra Erdős, Vatche Ishakian, Azer Bestavros, and Evimaria Terzi. A divide-and-conquer algorithm for betweenness centrality. In Proceedings of the 2015 SIAM International Conference on Data Mining, pages 433-441, 2015. Google Scholar
  22. Robert Geisberger, Peter Sanders, Dominik Schultes, and Daniel Delling. Contraction hierarchies: Faster and simpler hierarchical routing in road networks. In Catherine C. McGeoch, editor, Experimental Algorithms: 7th International Workshop, WEA 2008, pages 319-333. Springer Berlin Heidelberg, 2008. Google Scholar
  23. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which Problems Have Strongly Exponential Complexity? Journal of Computer and System Sciences, 63(4):512-530, dec 2001. URL: http://dx.doi.org/10.1006/jcss.2001.1774.
  24. Riko Jacob, Dirk Koschützki, Katharina Anna Lehmann, Leon Peeters, and Dagmar Tenfelde-Podehl. Algorithms for centrality indices. In DAGSTUHL, 2004. Google Scholar
  25. Hermann Kaindl and Gerhard Kainz. Bidirectional heuristic search reconsidered. J. Artif. Intell. Res. (JAIR), 7:283-317, 1997. Google Scholar
  26. Yeon-sup Lim, Daniel S Menasché, Bruno Ribeiro, Don Towsley, and Prithwish Basu. Online estimating the k central nodes of a network. Proceedings of IEEE NSW, pages 118-122, 2011. Google Scholar
  27. Richard J. Lipton and Jeffrey F. Naughton. Query Size Estimation by Adaptive Sampling. Journal of Computer and System Sciences, 51(1):18-25, August 1995. URL: http://dx.doi.org/10.1006/jcss.1995.1050.
  28. Richard J. Lipton and Naughton, Jeffrey F. Estimating the size of generalized transitive closures. In Proceedings of the 15th Int. Conf. on Very Large Data Bases, 1989. Google Scholar
  29. Linyuan Lu and Fan R. K. Chung. Complex graphs and networks. Number no. 107 in CBMS regional conference series in mathematics. American Mathematical Society, 2006. Google Scholar
  30. Mark Newman. Networks: an introduction. OUP Oxford, 2010. Google Scholar
  31. Mark EJ Newman. Scientific collaboration networks. ii. shortest paths, weighted networks, and centrality. Physical review E, 64(1):016132, 2001. Google Scholar
  32. Ilkka Norros and Hannu Reittu. On a conditionally Poissonian graph process. Advances in Applied Probability, 38(1):59-75, 2006. Google Scholar
  33. Jürgen Pfeffer and Kathleen M Carley. k-centralities: local approximations of global measures based on shortest paths. In Proceedings of the 21st international conference companion on World Wide Web, pages 1043-1050. ACM, 2012. Google Scholar
  34. Andrea Pietracaprina, Matteo Riondato, Eli Upfal, and Fabio Vandin. Mining Top-K Frequent Itemsets Through Progressive Sampling. Data Mining and Knowledge Discovery, 21(2):310-326, September 2010. URL: http://dx.doi.org/10.1007/s10618-010-0185-7.
  35. Ira Pohl. Bi-directional and heuristic search in path problems. PhD thesis, Dept. of Computer Science, Stanford University., 1969. Google Scholar
  36. Matteo Riondato and Evgenios M Kornaropoulos. Fast approximation of betweenness centrality through sampling. Data Mining and Knowledge Discovery, 30(2):438-475, 2015. Google Scholar
  37. Matteo Riondato and Eli Upfal. ABRA: Approximating Betweenness Centrality in Static and Dynamic Graphs with Rademacher Averages. arXiv preprint 1602.05866, pages 1-27, 2016. URL: http://arxiv.org/abs/1602.05866.
  38. Ahmet Erdem Sariyüce, Erik Saule, Kamer Kaya, and Ümit V Çatalyürek. Shattering and compressing networks for betweenness centrality. In SIAM Data Mining Conference (SDM). SIAM, 2013. Google Scholar
  39. Marvin E Shaw. Group structure and the behavior of individuals in small groups. The Journal of psychology, 38(1):139-149, 1954. Google Scholar
  40. Alfonso Shimbel. Structural parameters of communication networks. The bulletin of mathematical biophysics, 15(4):501-507, 1953. Google Scholar
  41. Christian L. Staudt, Aleksejs Sazonovs, and Henning Meyerhenke. Networkit: an interactive tool suite for high-performance network analysis. arXiv preprint 1403.3005, pages 1-25, 2014. Google Scholar
  42. Remco van der Hofstad. Random graphs and complex networks. Vol. II. Manuscript, 2014. Google Scholar
  43. Flavio Vella, Giancarlo Carbone, and Massimo Bernaschi. Algorithms and heuristics for scalable betweenness centrality computation on multi-gpu systems. CoRR, abs/1602.00963, 2016. Google Scholar
  44. Stanley Wasserman and Katherine Faust. Social network analysis: Methods and applications, volume 8. Cambridge university press, 1994. Google Scholar
  45. Ryan Williams and Huacheng Yu. Finding orthogonal vectors in discrete structures. In Proceedings of the 24th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1867-1877, 2014. URL: http://dx.doi.org/10.1137/1.9781611973402.135.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact