{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,1]],"date-time":"2026-08-01T00:10:59Z","timestamp":1785543059332,"version":"3.56.0"},"publisher-location":"New York, New York, USA","reference-count":23,"publisher":"ACM Press","license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"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":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1145\/2872518.2891063","type":"proceedings-article","created":{"date-parts":[[2017,1,23]],"date-time":"2017-01-23T20:35:52Z","timestamp":1485203752000},"page":"1017-1020","source":"Crossref","is-referenced-by-count":22,"title":["Centrality Measures on Big Graphs"],"prefix":"10.1145","author":[{"given":"Francesco","family":"Bonchi","sequence":"first","affiliation":[{"name":"ISI Foundation, Turin, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gianmarco","family":"De Francisci Morales","sequence":"additional","affiliation":[{"name":"Qatar Computing Research Institute, Doha, Qatar"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Matteo","family":"Riondato","sequence":"additional","affiliation":[{"name":"Two Sigma Investments, New York City, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","reference":[{"key":"key-10.1145\/2872518.2891063-1","unstructured":"E. Bergamini and H. Meyerhenke. Fully-dynamic approximation of betweenness centrality. CoRR, abs\/1504.0709 (to appear in ESA'15), Apr. 2015."},{"key":"key-10.1145\/2872518.2891063-2","doi-asserted-by":"crossref","unstructured":"E. Bergamini, H. Meyerhenke, and C. L. Staudt. Approximating betweenness centrality in large evolving networks. In 17th Workshop on Algorithm Engineering and Experiments, ALENEX 2015, pages 133--146. SIAM, 2015.","DOI":"10.1137\/1.9781611973754.12"},{"key":"key-10.1145\/2872518.2891063-3","doi-asserted-by":"crossref","unstructured":"P. Boldi and S. Vigna. Axioms for centrality. Internet Mathematics, 10 (3--4): 222--262, 2014.","DOI":"10.1080\/15427951.2013.865686"},{"key":"key-10.1145\/2872518.2891063-4","doi-asserted-by":"crossref","unstructured":"U. Brandes. A faster algorithm for betweenness centrality. J. Math. Sociol., 25 (2): 163--177, 2001. 10.1080\/0022250X.2001.9990249.","DOI":"10.1080\/0022250X.2001.9990249"},{"key":"key-10.1145\/2872518.2891063-5","doi-asserted-by":"crossref","unstructured":"U. Brandes and C. Pich. Centrality estimation in large networks. Int. J. Bifurcation and Chaos, 17 (7): 2303--2318, 2007. 10.1142\/S0218127407018403.","DOI":"10.1142\/S0218127407018403"},{"key":"key-10.1145\/2872518.2891063-6","doi-asserted-by":"crossref","unstructured":"D. Eppstein and J. Wang. Fast approximation of centrality. J. Graph Algorithms Appl., 8 (1): 39--45, 2004.","DOI":"10.7155\/jgaa.00081"},{"key":"key-10.1145\/2872518.2891063-7","unstructured":"D. Erd, Hos, V. Ishakian, A. Bestavros, and E. Terzi. A divide-and-conquer algorithm for betweenness centrality. In SIAM Data Mining Conf., 2015."},{"key":"key-10.1145\/2872518.2891063-8","doi-asserted-by":"crossref","unstructured":"R. Geisberger, P. Sanders, and D. Schultes. Better approximation of betweenness centrality. In J. I. Munro and D. Wagner, editors, Algorithm Eng. & Experiments (ALENEX'08), pages 90--100. SIAM, 2008.","DOI":"10.1137\/1.9781611972887.9"},{"key":"key-10.1145\/2872518.2891063-9","doi-asserted-by":"crossref","unstructured":"T. Hayashi, T. Akiba, and Y. Yoshida. Fully dynamic betweenness centrality maintenance on massive networks. Proceedings of the VLDB Endowment, 9 (2): 48--59, 2015.","DOI":"10.14778\/2850578.2850580"},{"key":"key-10.1145\/2872518.2891063-10","doi-asserted-by":"crossref","unstructured":"M. Kas, M. Wachs, K. M. Carley, and L. R. Carley. Incremental algorithm for updating betweenness centrality in dynamically growing networks. In Proceedings of the 2013 IEEE\/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM'13, pages 33--40, New York, NY, USA, 2013. ACM. ISBN 978--1--4503--2240--9. 10.1145\/2492517.2492533. URL http:\/\/doi.acm.org\/10.1145\/2492517.2492533.","DOI":"10.1145\/2492517.2492533"},{"key":"key-10.1145\/2872518.2891063-11","doi-asserted-by":"crossref","unstructured":"N. Kourtellis, G. De Francisci Morales, and F. Bonchi. Scalable online betweenness centrality in evolving graphs. IEEE Trans. Knowl. Data Eng., 27 (9): 2494--2506, 2015. 10.1109\/TKDE.2015.2419666.","DOI":"10.1109\/TKDE.2015.2419666"},{"key":"key-10.1145\/2872518.2891063-12","doi-asserted-by":"crossref","unstructured":"M.-J. Lee, J. Lee, J. Y. Park, R. H. Choi, and C.-W. Chung. QUBE: A quick algorithm for updating betweenness centrality. In Proceedings of the 21st International Conference on World Wide Web, WWW'12, pages 351--360, New York, NY, USA, 2012. ACM. ISBN 978--1--4503--1229--5. 10.1145\/2187836.2187884.","DOI":"10.1145\/2187836.2187884"},{"key":"key-10.1145\/2872518.2891063-13","doi-asserted-by":"crossref","unstructured":"C. Mavroforakis, R. Garcia-Lebron, I. Koutis, and E. Terzi. Spanning edge centrality: Large-scale computation and applications. In Proceedings of the 24th International Conference on World Wide Web, pages 732--742. International World Wide Web Conferences Steering Committee, 2015","DOI":"10.1145\/2736277.2741125"},{"key":"key-10.1145\/2872518.2891063-14","unstructured":"C. Mavroforakis, M. Mathioudakis, and A. Gionis. Absorbing random-walk centrality: Theory and algorithms. arXiv preprint arXiv:1509.02533, 2015."},{"key":"key-10.1145\/2872518.2891063-15","doi-asserted-by":"crossref","unstructured":"M. Nasre, M. Pontecorvi, and V. Ramachandran. Betweenness centrality--incremental and faster. In Mathematical Foundations of Computer Science 2014, pages 577--588. Springer, 2014.","DOI":"10.1007\/978-3-662-44465-8_49"},{"key":"key-10.1145\/2872518.2891063-16","doi-asserted-by":"crossref","unstructured":"M. E. J. Newman. Networks -- An Introduction. Oxford University Press, 2010.","DOI":"10.1093\/acprof:oso\/9780199206650.001.0001"},{"key":"key-10.1145\/2872518.2891063-17","unstructured":"M. Pontecorvi and V. Ramachandran. A faster algorithm for fully dynamic betweenness centrality. arXiv preprint arXiv:1506.05783, 2015."},{"key":"key-10.1145\/2872518.2891063-18","doi-asserted-by":"crossref","unstructured":"M. Riondato and E. M. Kornaropoulos. Fast approximation of betweenness centrality through sampling. Data Mining and Knowledge Discovery, 30 (2): 438--475, 2015. ISSN 1573--756X. 10.1007\/s10618-015-0423-0. URL http:\/\/dx.doi.org\/10.1007\/s10618-015-0423-0.","DOI":"10.1007\/s10618-015-0423-0"},{"key":"key-10.1145\/2872518.2891063-19","doi-asserted-by":"crossref","unstructured":"M. Riondato and E. Upfal. ABRA: Approximating betweenness centrality in static and dynamic graphs with Rademacher averages. CoRR, feb 2016. URL http:\/\/arxiv.org\/abs\/1602.05866.","DOI":"10.1145\/2939672.2939770"},{"key":"key-10.1145\/2872518.2891063-20","doi-asserted-by":"crossref","unstructured":"A. E. Sarıyüce, K. Kaya, E. Saule, and Ü. V. Çatalyürek. Betweenness centrality on GPUs and heterogeneous architectures. In Proceedings of the 6th Workshop on General Purpose Processor Using Graphics Processing Units, pages 76--85. ACM, 2013","DOI":"10.1145\/2458523.2458531"},{"key":"key-10.1145\/2872518.2891063-21","doi-asserted-by":"crossref","unstructured":"A. E. Sarıyüce, K. Kaya, E. Saule, and Ü. V. Çatalyürek. Incremental algorithms for closeness centrality. In IEEE International Conference on BigData, 2013\\natexlabb.","DOI":"10.1109\/BigData.2013.6691611"},{"key":"key-10.1145\/2872518.2891063-22","doi-asserted-by":"crossref","unstructured":"A. E. Sarıyüce, E. Saule, K. Kaya, and Ü. V. Çatalyürek. Shattering and compressing networks for betweenness centrality. In SIAM Data Mining Conf., 2013.","DOI":"10.1137\/1.9781611972832.76"},{"key":"key-10.1145\/2872518.2891063-23","doi-asserted-by":"crossref","unstructured":"Y. Yoshida. Almost linear-time algorithms for adaptive betweenness centrality using hypergraph sketches. In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD'14, pages 1416--1425, New York, NY, USA, 2014. ACM. ISBN 978--1--4503--2956--9. 10.1145\/2623330.2623626.","DOI":"10.1145\/2623330.2623626"}],"event":{"name":"the 25th International Conference Companion","location":"Montréal, Québec, Canada","acronym":"WWW '16 Companion","number":"25","sponsor":["SIGWEB, ACM Special Interest Group on Hypertext, Hypermedia, and Web","IW3C2, International World Wide Web Conference Committee"],"start":{"date-parts":[[2016,4,11]]},"end":{"date-parts":[[2016,4,15]]}},"container-title":["Proceedings of the 25th International Conference Companion on World Wide Web - WWW '16 Companion"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2872518.2891063","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/dl.acm.org\/ft_gateway.cfm?id=2891063&ftid=1707945&dwn=1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:54:23Z","timestamp":1750222463000},"score":1,"resource":{"primary":{"URL":"http:\/\/dl.acm.org\/citation.cfm?doid=2872518.2891063"}},"subtitle":["Exact, Approximated, and Distributed Algorithms"],"proceedings-subject":"World Wide Web","short-title":[],"issued":{"date-parts":[[2016]]},"references-count":23,"URL":"https:\/\/doi.org\/10.1145\/2872518.2891063","relation":{},"subject":[],"published":{"date-parts":[[2016]]}}}