{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T15:17:34Z","timestamp":1777735054787,"version":"3.51.4"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2019,2,20]],"date-time":"2019-02-20T00:00:00Z","timestamp":1550620800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2019,12,17]]},"abstract":"<jats:p>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.<\/jats:p>\n          <jats:p>\n            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 |\n            <jats:italic>E<\/jats:italic>\n            |\n            <jats:sup>\n              1\/2+\n              <jats:italic>o<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            with high probability, obtaining a significant speedup with respect to the \u0398(|\n            <jats:italic>E<\/jats:italic>\n            |) worst-case performance. We experimentally show that this new technique achieves similar speedups on real-world complex networks, as well.\n          <\/jats:p>\n          <jats:p>\n            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\n            <jats:italic>k<\/jats:italic>\n            most central nodes. Furthermore, our analysis is general, and it might be extended to other settings.\n          <\/jats:p>","DOI":"10.1145\/3284359","type":"journal-article","created":{"date-parts":[[2019,2,22]],"date-time":"2019-02-22T17:01:44Z","timestamp":1550854904000},"page":"1-35","source":"Crossref","is-referenced-by-count":38,"title":["KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation"],"prefix":"10.1145","volume":"24","author":[{"given":"Michele","family":"Borassi","sequence":"first","affiliation":[{"name":"IMT School for Advanced Studies Lucca, Lucca (LU) - Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8755-3892","authenticated-orcid":false,"given":"Emanuele","family":"Natale","sequence":"additional","affiliation":[{"name":"Max-Planck-Institut f\u00fcr Informatik"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,2,20]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Retrieved on","author":"CAMVIT","year":"2016","unstructured":"CAMVIT : Choice Routing. 2009 . Retrieved on April 21, 2016 from http:\/\/www.camvit.com. CAMVIT: Choice Routing. 2009. Retrieved on April 21, 2016 from http:\/\/www.camvit.com."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03685-9_2"},{"key":"e_1_2_1_3_1","volume-title":"The rush in a directed graph. Stichting Mathematisch Centrum. Mathematische Besliskunde BN, 9\/71","author":"Anthonisse Jac M.","year":"1971","unstructured":"Jac M. Anthonisse . 1971. The rush in a directed graph. Stichting Mathematisch Centrum. Mathematische Besliskunde BN, 9\/71 ( 1971 ), 1--10. Jac M. Anthonisse. 1971. The rush in a directed graph. Stichting Mathematisch Centrum. Mathematische Besliskunde BN, 9\/71 (1971), 1--10."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/1777879.1777889"},{"key":"e_1_2_1_5_1","series-title":"Lecture Notes in Computer Science","volume-title":"Theory and Practice of Algorithms in (Computer) Systems","author":"Bader Roland","unstructured":"Roland Bader , Jonathan Dees , Robert Geisberger , and Peter Sanders . 2011. Alternative route graphs in road networks . In Theory and Practice of Algorithms in (Computer) Systems , Lecture Notes in Computer Science . Springer , Berlin , 21--32. Roland Bader, Jonathan Dees, Robert Geisberger, and Peter Sanders. 2011. Alternative route graphs in road networks. In Theory and Practice of Algorithms in (Computer) Systems, Lecture Notes in Computer Science. Springer, Berlin, 21--32."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.17730\/humo.7.3.f4033344851gl053"},{"key":"e_1_2_1_7_1","unstructured":"Elisabetta Bergamini. 2016. Private communication.  Elisabetta Bergamini. 2016. Private communication."},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Elisabetta Bergamini Michele Borassi Pierluigi Crescenzi Andrea Marino and Henning Meyerhenke. 2016. Computing top-k closeness centrality faster in unweighted graphs. In ALENEX.  Elisabetta Bergamini Michele Borassi Pierluigi Crescenzi Andrea Marino and Henning Meyerhenke. 2016. Computing top-k closeness centrality faster in unweighted graphs. In ALENEX.","DOI":"10.1137\/1.9781611974317.6"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Elisabetta Bergamini and Henning Meyerhenke. 2015. Fully-dynamic approximation of betweenness centrality. In ESA.  Elisabetta Bergamini and Henning Meyerhenke. 2015. Fully-dynamic approximation of betweenness centrality. In ESA.","DOI":"10.1007\/978-3-662-48350-3_14"},{"key":"e_1_2_1_10_1","volume-title":"Faster betweenness centrality updates in evolving networks. arXiv preprint arXiv:1704.08592","author":"Bergamini Elisabetta","year":"2017","unstructured":"Elisabetta Bergamini , Henning Meyerhenke , Mark Ortmann , and Arie Slobbe . 2017. Faster betweenness centrality updates in evolving networks. arXiv preprint arXiv:1704.08592 ( 2017 ). Elisabetta Bergamini, Henning Meyerhenke, Mark Ortmann, and Arie Slobbe. 2017. Faster betweenness centrality updates in evolving networks. arXiv preprint arXiv:1704.08592 (2017)."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2567948.2577304"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(80)80030-8"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/1276871.1276872"},{"key":"e_1_2_1_14_1","unstructured":"Michele Borassi. 2016. Algorithms for Metric Properties of Large Real-world Networks from Theory to Practice and Back. Electronic thesis or dissertation. http:\/\/e-theses.imtlucca.it\/198\/.  Michele Borassi. 2016. Algorithms for Metric Properties of Large Real-world Networks from Theory to Practice and Back. Electronic thesis or dissertation. http:\/\/e-theses.imtlucca.it\/198\/."},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 16th Italian Conference on Theoretical Computer Science (ICTCS\u201915)","author":"Borassi Michele","year":"2015","unstructured":"Michele Borassi , Pierluig Crescenzi , and Michel Habib . 2015 . Into the square - On the complexity of some quadratic-time solvable problems . In Proceedings of the 16th Italian Conference on Theoretical Computer Science (ICTCS\u201915) . 1--17. Michele Borassi, Pierluig Crescenzi, and Michel Habib. 2015. Into the square - On the complexity of some quadratic-time solvable problems. In Proceedings of the 16th Italian Conference on Theoretical Computer Science (ICTCS\u201915). 1--17."},{"key":"e_1_2_1_16_1","volume-title":"An axiomatic and an average-case analysis of algorithms and heuristics for metric properties of graphs. arXiv:1604.01445 {cs} (April","author":"Borassi Michele","year":"2016","unstructured":"Michele Borassi , Pierluigi Crescenzi , and Luca Trevisan . 2016. An axiomatic and an average-case analysis of algorithms and heuristics for metric properties of graphs. arXiv:1604.01445 {cs} (April 2016 ). arXiv: 1604.01445. Michele Borassi, Pierluigi Crescenzi, and Luca Trevisan. 2016. An axiomatic and an average-case analysis of algorithms and heuristics for metric properties of graphs. arXiv:1604.01445 {cs} (April 2016). arXiv: 1604.01445."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.socnet.2005.11.005"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1080\/0022250X.2001.9990249"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.socnet.2007.11.001"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218127407018403"},{"key":"e_1_2_1_21_1","unstructured":"Mostafa Haghir Chehreghani Talel Abdessalem etal 2017. Metropolis-hastings algorithms for estimating betweenness centrality in large networks. arXiv preprint arXiv:1704.07351 .  Mostafa Haghir Chehreghani Talel Abdessalem et al. 2017. Metropolis-hastings algorithms for estimating betweenness centrality in large networks. arXiv preprint arXiv:1704.07351 ."},{"key":"e_1_2_1_22_1","first-page":"1","article-title":"Networks and centres of integration in Indian civilization","volume":"1","author":"Cohn Bernard S.","year":"1958","unstructured":"Bernard S. Cohn and McKim Marriott . 1958 . Networks and centres of integration in Indian civilization . Journal of Social Research 1 , 1 (1958), 1 -- 9 . Bernard S. Cohn and McKim Marriott. 1958. Networks and centres of integration in Indian civilization. Journal of Social Research 1, 1 (1958), 1--9.","journal-title":"Journal of Social Research"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1734213.1734219"},{"key":"e_1_2_1_24_1","volume-title":"Kleinberg","author":"Easley David A.","year":"2010","unstructured":"David A. Easley and Jon M . Kleinberg . 2010 . Networks, crowds, and markets - Reasoning about a highly connected world. In DAGLIB. David A. Easley and Jon M. Kleinberg. 2010. Networks, crowds, and markets - Reasoning about a highly connected world. In DAGLIB."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00081"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"D\u00f3ra Erd\u00f6s Vatche Ishakian Azer Bestavros and Evimaria Terzi. 2015. A divide-and-conquer algorithm for betweenness centrality. CoRR abs\/1406.4173.  D\u00f3ra Erd\u00f6s Vatche Ishakian Azer Bestavros and Evimaria Terzi. 2015. A divide-and-conquer algorithm for betweenness centrality. CoRR abs\/1406.4173.","DOI":"10.1137\/1.9781611974010.49"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/1315958.1315962"},{"key":"e_1_2_1_28_1","unstructured":"Robert Geisberger Peter Sanders Dominik Schultes and Daniel Delling. 2008. Contraction hierarchies: Faster and simpler hierarchical routing in road networks. In WEA.   Robert Geisberger Peter Sanders Dominik Schultes and Daniel Delling. 2008. Contraction hierarchies: Faster and simpler hierarchical routing in road networks. In WEA."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_2_1_30_1","volume-title":"Leon Peeters, and Dagmar Tenfelde-Podehl.","author":"Jacob Riko","year":"2004","unstructured":"Riko Jacob , Dirk Kosch\u00fctzki , Katharina Anna Lehmann , Leon Peeters, and Dagmar Tenfelde-Podehl. 2004 . Algorithms for centrality indices. In DAGSTUHL. Riko Jacob, Dirk Kosch\u00fctzki, Katharina Anna Lehmann, Leon Peeters, and Dagmar Tenfelde-Podehl. 2004. Algorithms for centrality indices. In DAGSTUHL."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/1622776.1622787"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/NSW.2011.6004633"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 15th erence on Very Large Data Bases.","author":"Richard","unstructured":"Richard J. Lipton and Jeffrey F. Naughton. 1989. Estimating the size of generalized transitive closures . In Proceedings of the 15th erence on Very Large Data Bases. Richard J. Lipton and Jeffrey F. Naughton. 1989. Estimating the size of generalized transitive closures. In Proceedings of the 15th erence on Very Large Data Bases."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1050"},{"key":"e_1_2_1_35_1","volume-title":"Chung","author":"Lu Linyuan","year":"2006","unstructured":"Linyuan Lu and Fan R. K . Chung . 2006 . Complex Graphs and Networks. Number 107 in CBMS Regional Conference Series in Mathematics. American Mathematical Society . Linyuan Lu and Fan R. K. Chung. 2006. Complex Graphs and Networks. Number 107 in CBMS Regional Conference Series in Mathematics. American Mathematical Society."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780199206650.001.0001"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.64.016132"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1017\/S000186780000080X"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2187980.2188239"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-010-0185-7"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-015-0423-0"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939770"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1080\/00223980.1954.9712925"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02476438"},{"key":"e_1_2_1_46_1","volume-title":"Networkit: An interactive tool suite for high-performance network analysis. arXiv preprint 1403.3005","author":"Staudt Christian L.","year":"2014","unstructured":"Christian L. Staudt , Aleksejs Sazonovs , and Henning Meyerhenke . 2014 . Networkit: An interactive tool suite for high-performance network analysis. arXiv preprint 1403.3005 (2014), 1--25. Christian L. Staudt, Aleksejs Sazonovs, and Henning Meyerhenke. 2014. Networkit: An interactive tool suite for high-performance network analysis. arXiv preprint 1403.3005 (2014), 1--25."},{"key":"e_1_2_1_47_1","volume-title":"Ahmet Erdem Sariy\u00fcce, and Erik Saule","author":"\u00c7ataly\u00fcrek \u00dcmit V.","year":"2013","unstructured":"\u00dcmit V. \u00c7ataly\u00fcrek , Kamer Kaya , Ahmet Erdem Sariy\u00fcce, and Erik Saule . 2013 . Shattering and compressing networks for betweenness centrality. In SDM. \u00dcmit V. \u00c7ataly\u00fcrek, Kamer Kaya, Ahmet Erdem Sariy\u00fcce, and Erik Saule. 2013. Shattering and compressing networks for betweenness centrality. In SDM."},{"key":"e_1_2_1_48_1","volume-title":"Random Graphs and Complex Networks","author":"van der Hofstad Remco","unstructured":"Remco van der Hofstad . 2014. Random Graphs and Complex Networks . Vol. II . Remco van der Hofstad. 2014. Random Graphs and Complex Networks. Vol. II."},{"key":"e_1_2_1_49_1","volume-title":"Algorithms and heuristics for scalable betweenness centrality computation on multi-GPU systems. CoRR abs\/1602.00963","author":"Vella Flavio","year":"2016","unstructured":"Flavio Vella , Giancarlo Carbone , and Massimo Bernaschi . 2016. Algorithms and heuristics for scalable betweenness centrality computation on multi-GPU systems. CoRR abs\/1602.00963 ( 2016 ). Flavio Vella, Giancarlo Carbone, and Massimo Bernaschi. 2016. Algorithms and heuristics for scalable betweenness centrality computation on multi-GPU systems. CoRR abs\/1602.00963 (2016)."},{"key":"e_1_2_1_50_1","unstructured":"Sebastiano Vigna. 2016. Private communication.  Sebastiano Vigna. 2016. Private communication."},{"key":"e_1_2_1_51_1","volume-title":"Social Network Analysis: Methods and Applications","author":"Wasserman Stanley","unstructured":"Stanley Wasserman and Katherine Faust . 1994. Social Network Analysis: Methods and Applications . Vol. 8 . Cambridge University Press . Stanley Wasserman and Katherine Faust. 1994. Social Network Analysis: Methods and Applications. Vol. 8. Cambridge University Press."}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3284359","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3284359","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:43:49Z","timestamp":1750207429000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3284359"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,2,20]]},"references-count":50,"alternative-id":["10.1145\/3284359"],"URL":"https:\/\/doi.org\/10.1145\/3284359","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,2,20]]}}}