{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,13]],"date-time":"2026-03-13T14:57:41Z","timestamp":1773413861487,"version":"3.50.1"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2019,9,24]],"date-time":"2019-09-24T00:00:00Z","timestamp":1569283200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Italian Ministry of Education, and Research","award":["PRIN 2012C4E3KT"],"award-info":[{"award-number":["PRIN 2012C4E3KT"]}]},{"name":"AMANDA\u2014Algorithmics for MAssive and Networked DAta"},{"DOI":"10.13039\/501100001659","name":"German Research Foundation","doi-asserted-by":"crossref","award":["ME 3619\/3-2"],"award-info":[{"award-number":["ME 3619\/3-2"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2019,10,31]]},"abstract":"<jats:p>\n            Given a connected graph\n            <jats:italic>G<\/jats:italic>\n            =(\n            <jats:italic>V<\/jats:italic>\n            ,\n            <jats:italic>E<\/jats:italic>\n            ), where\n            <jats:italic>V<\/jats:italic>\n            denotes the set of nodes and\n            <jats:italic>E<\/jats:italic>\n            the set of edges of the graph, the length (that is, the number of edges) of the shortest path between two nodes\n            <jats:italic>v<\/jats:italic>\n            and\n            <jats:italic>w<\/jats:italic>\n            is denoted by\n            <jats:italic>d<\/jats:italic>\n            (\n            <jats:italic>v<\/jats:italic>\n            ,\n            <jats:italic>w<\/jats:italic>\n            ). The closeness centrality of a vertex\n            <jats:italic>v<\/jats:italic>\n            is then defined as\n            <jats:italic>n<\/jats:italic>\n            =1\/\u03a3\n            <jats:sub>\n              <jats:italic>w<\/jats:italic>\n              \u2208\n              <jats:italic>V<\/jats:italic>\n            <\/jats:sub>\n            <jats:italic>d<\/jats:italic>\n            (\n            <jats:italic>v<\/jats:italic>\n            ,\n            <jats:italic>w<\/jats:italic>\n            ), where\n            <jats:italic>n<\/jats:italic>\n            =|\n            <jats:italic>V<\/jats:italic>\n            |. This measure is widely used in the analysis of real-world complex networks, and the problem of selecting the\n            <jats:italic>k<\/jats:italic>\n            most central vertices has been deeply analyzed in the last decade. However, this problem is computationally not easy, especially for large networks: in the first part of the article, we prove that it is not solvable in time\n            <jats:italic>O<\/jats:italic>\n            (|\n            <jats:italic>E<\/jats:italic>\n            |\n            <jats:sup>2=\u03f5<\/jats:sup>\n            ) on directed graphs, for any constant \u03f5 &gt; 0, under reasonable complexity assumptions. Furthermore, we propose a new algorithm for selecting the\n            <jats:italic>k<\/jats:italic>\n            most central nodes in a graph: we experimentally show that this algorithm improves significantly both the textbook algorithm, which is based on computing the distance between all pairs of vertices, and the state of the art. For example, we are able to compute the top\n            <jats:italic>k<\/jats:italic>\n            nodes in few dozens of seconds in real-world networks with millions of nodes and edges. Finally, as a case study, we compute the 10 most central actors in the Internet Movie Database (IMDB) collaboration network, where two actors are linked if they played together in a movie, and in the Wikipedia citation network, which contains a directed edge from a page\n            <jats:italic>p<\/jats:italic>\n            to a page\n            <jats:italic>q<\/jats:italic>\n            if\n            <jats:italic>p<\/jats:italic>\n            contains a link to\n            <jats:italic>q<\/jats:italic>\n            .\n          <\/jats:p>","DOI":"10.1145\/3344719","type":"journal-article","created":{"date-parts":[[2019,9,25]],"date-time":"2019-09-25T12:57:52Z","timestamp":1569416272000},"page":"1-40","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":23,"title":["Computing top-\n            <i>k<\/i>\n            Closeness Centrality Faster in Unweighted Graphs"],"prefix":"10.1145","volume":"13","author":[{"given":"Elisabetta","family":"Bergamini","sequence":"first","affiliation":[{"name":"Karlsruhe Institute of Technology, Karlsruhe, Germany"}]},{"given":"Michele","family":"Borassi","sequence":"additional","affiliation":[{"name":"IMT Institute for Advanced Studies Lucca, Italy"}]},{"given":"Pierluigi","family":"Crescenzi","sequence":"additional","affiliation":[{"name":"Universit\u00e0 degli Studi di Firenze and Universit\u00e9 de Paris, France"}]},{"given":"Andrea","family":"Marino","sequence":"additional","affiliation":[{"name":"Universit\u00e0 degli Studi di Firenze, Firenze, Italy"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7769-726X","authenticated-orcid":false,"given":"Henning","family":"Meyerhenke","sequence":"additional","affiliation":[{"name":"Karlsruhe Institute of Technology and Humboldt-Universit\u00e4t zu Berlin, Berlin, Germany"}]}],"member":"320","published-online":{"date-parts":[[2019,9,24]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 26th ACM\/SIAM Symposium on Discrete Algorithms (SODA\u201915)","author":"Abboud Amir","unstructured":"Amir Abboud , Fabrizio Grandoni , and Virginia V. Williams . 2015. Subcubic equivalences between graph centrality problems, APSP and diameter . In Proceedings of the 26th ACM\/SIAM Symposium on Discrete Algorithms (SODA\u201915) . 1681--1697. Retrieved from http:\/\/people.idsia.ch\/&sim;grandoni\/Pubblicazioni\/AGV15soda.pdf. Amir Abboud, Fabrizio Grandoni, and Virginia V. Williams. 2015. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proceedings of the 26th ACM\/SIAM Symposium on Discrete Algorithms (SODA\u201915). 1681--1697. Retrieved from http:\/\/people.idsia.ch\/&sim;grandoni\/Pubblicazioni\/AGV15soda.pdf."},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 55th Annual Symposium on Foundations of Computer Science (FOCS\u201914)","author":"Abboud Amir","unstructured":"Amir Abboud and Virginia V. Williams . 2014. Popular conjectures imply strong lower bounds for dynamic problems . In Proceedings of the 55th Annual Symposium on Foundations of Computer Science (FOCS\u201914) . 434--443. Retrieved from http:\/\/arxiv.org\/abs\/1402.0054. Amir Abboud and Virginia V. Williams. 2014. Popular conjectures imply strong lower bounds for dynamic problems. In Proceedings of the 55th Annual Symposium on Foundations of Computer Science (FOCS\u201914). 434--443. Retrieved from http:\/\/arxiv.org\/abs\/1402.0054."},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 27th ACM\/SIAM Symposium on Discrete Algorithms (SODA\u201916)","author":"Abboud Amir","year":"2016","unstructured":"Amir Abboud , Virginia V. Williams , and Joshua Wang . 2016 . Approximation and fixed parameter subquadratic algorithms for radius and diameter . In Proceedings of the 27th ACM\/SIAM Symposium on Discrete Algorithms (SODA\u201916) . 377--391. Amir Abboud, Virginia V. Williams, and Joshua Wang. 2016. Approximation and fixed parameter subquadratic algorithms for radius and diameter. In Proceedings of the 27th ACM\/SIAM Symposium on Discrete Algorithms (SODA\u201916). 377--391."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43948-7_4"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1121\/1.1906679"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974317.6"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDMW.2013.10"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2013.865686"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2016.05.002"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 16th Italian Conference on Theoretical Computer Science (ICTCS\u201915)","author":"Borassi Michele","year":"2015","unstructured":"Michele Borassi , Pierluigi Crescenzi , and Michel Habib . 2015 a. 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. Retrieved from http:\/\/arxiv.org\/abs\/1407.4972. Michele Borassi, Pierluigi Crescenzi, and Michel Habib. 2015a. 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. Retrieved from http:\/\/arxiv.org\/abs\/1407.4972."},{"key":"e_1_2_1_11_1","unstructured":"Michele Borassi Pierluigi Crescenzi and Andrea Marino. 2015b. Fast and simple computation of top-k closeness centralities. arXiv:1507.01490.  Michele Borassi Pierluigi Crescenzi and Andrea Marino. 2015b. Fast and simple computation of top-k closeness centralities. arXiv:1507.01490."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-31856-9_44"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM\u201915)","volume":"40","author":"Chechik Shiri","year":"2015","unstructured":"Shiri Chechik , Edith Cohen , and Haim Kaplan . 2015 . Average distance queries through weighted samples in graphs and metric spaces: High scalability with tight statistical guarantees . In Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM\u201915) . LIPIcs, Vol. 40 , Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 659--679. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.APPROX-RANDOM. 2015.659 10.4230\/LIPIcs.APPROX-RANDOM.2015.659 Shiri Chechik, Edith Cohen, and Haim Kaplan. 2015. Average distance queries through weighted samples in graphs and metric spaces: High scalability with tight statistical guarantees. In Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM\u201915). LIPIcs, Vol. 40, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 659--679. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.APPROX-RANDOM.2015.659"},{"key":"e_1_2_1_14_1","volume-title":"Identifying influential nodes in complex networks. Physica A: Statistical Mechanics and its Applications 391, 4","author":"Chen Duanbing","year":"2012","unstructured":"Duanbing Chen , Linyuan Lu , Ming-Sheng Shang , Yi-Cheng Zhang , and Tao Zhou . 2012. Identifying influential nodes in complex networks. Physica A: Statistical Mechanics and its Applications 391, 4 ( 2012 ), 1777--1787. DOI:https:\/\/doi.org\/10.1016\/j.physa.2011.09.017 10.1016\/j.physa.2011.09.017 Duanbing Chen, Linyuan Lu, Ming-Sheng Shang, Yi-Cheng Zhang, and Tao Zhou. 2012. Identifying influential nodes in complex networks. Physica A: Statistical Mechanics and its Applications 391, 4 (2012), 1777--1787. DOI:https:\/\/doi.org\/10.1016\/j.physa.2011.09.017"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 2nd ACM Conference on Online Social Networks (COSN\u201914)","author":"Cohen Edith","unstructured":"Edith Cohen , Daniel Delling , Thomas Pajor , and Renato F. Werneck . 2014. Computing classic closeness centrality, at scale . In Proceedings of the 2nd ACM Conference on Online Social Networks (COSN\u201914) . 37--50. Edith Cohen, Daniel Delling, Thomas Pajor, and Renato F. Werneck. 2014. Computing classic closeness centrality, at scale. In Proceedings of the 2nd ACM Conference on Online Social Networks (COSN\u201914). 37--50."},{"key":"e_1_2_1_16_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","unstructured":"Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , and Clifford Stein . 2009. Introduction to Algorithms ( 3 rd ed.). MIT Press . Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms (3rd ed.). MIT Press.","edition":"3"},{"key":"e_1_2_1_17_1","first-page":"1","article-title":"The igraph software package for complex network research. InterJournal, Vol","volume":"1695","author":"Cs\u00e1rdi G\u00e1bor","year":"2006","unstructured":"G\u00e1bor Cs\u00e1rdi and Tam\u00e1s Nepusz . 2006 . The igraph software package for complex network research. InterJournal, Vol : Complex Systems 1695 , 5 (2006), 1 -- 9 . Retrieved from http:\/\/www.necsi.edu\/events\/iccs6\/papers\/c1602a3c126ba822d0bc4293371c.pdf. G\u00e1bor Cs\u00e1rdi and Tam\u00e1s Nepusz. 2006. The igraph software package for complex network research. InterJournal, Vol: Complex Systems 1695, 5 (2006), 1--9. Retrieved from http:\/\/www.necsi.edu\/events\/iccs6\/papers\/c1602a3c126ba822d0bc4293371c.pdf.","journal-title":"Complex Systems"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00081"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.80"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2608628.2608664"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 7th Python in Science Conference (SCIPY\u201908)","author":"Hagberg Aric A.","year":"2008","unstructured":"Aric A. Hagberg , Daniel A. Schult , and Pieter J. Swart . 2008. Exploring network structure, dynamics, and function using NetworkX . In Proceedings of the 7th Python in Science Conference (SCIPY\u201908) . 11--15. Retrieved from https:\/\/conference.scipy.org\/proceedings\/scipy 2008 \/paper_2\/full_text.pdf. Aric A. Hagberg, Daniel A. Schult, and Pieter J. Swart. 2008. Exploring network structure, dynamics, and function using NetworkX. In Proceedings of the 7th Python in Science Conference (SCIPY\u201908). 11--15. Retrieved from https:\/\/conference.scipy.org\/proceedings\/scipy2008\/paper_2\/full_text.pdf."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972818.11"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2014.03.006"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/NSW.2011.6004633"},{"key":"e_1_2_1_26_1","volume-title":"Foundations of Social Research","author":"Lin Nan","unstructured":"Nan Lin . 1976. Foundations of Social Research . McGraw-Hill . Retrieved from http:\/\/books.google.it\/books?id&equals;DIowAAAAMAAJ. Nan Lin. 1976. Foundations of Social Research. McGraw-Hill. Retrieved from http:\/\/books.google.it\/books?id&equals;DIowAAAAMAAJ."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0378-4371(00)00311-3"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780199206650.001.0001"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-69311-6_21"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2014.6816651"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the 21st ACM\/SIAM Symposium on Discrete Algorithms (SODA\u201910)","author":"P\u01cetra\u015fcu Mihai","year":"2010","unstructured":"Mihai P\u01cetra\u015fcu and Ryan Williams . 2010 . On the possibility of faster SAT algorithms . In Proceedings of the 21st ACM\/SIAM Symposium on Discrete Algorithms (SODA\u201910) . Retrieved from http:\/\/epubs.siam.org\/doi\/abs\/10.1137\/1.978161 1973075.86. Mihai P\u01cetra\u015fcu and Ryan Williams. 2010. On the possibility of faster SAT algorithms. In Proceedings of the 21st ACM\/SIAM Symposium on Discrete Algorithms (SODA\u201910). Retrieved from http:\/\/epubs.siam.org\/doi\/abs\/10.1137\/1.9781611973075.86."},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC\u201913)","author":"Roditty Liam","unstructured":"Liam Roditty and Virginia V. Williams . 2013. Fast approximation algorithms for the diameter and radius of sparse graphs . In Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC\u201913) . 515--524. DOI:https:\/\/doi.org\/10.1145\/2488608.2488673 10.1145\/2488608.2488673 Liam Roditty and Virginia V. Williams. 2013. Fast approximation algorithms for the diameter and radius of sparse graphs. In Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC\u201913). 515--524. DOI:https:\/\/doi.org\/10.1145\/2488608.2488673"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the IEEE International Conference on Big Data (ICBDA\u201913)","author":"Sariy\u00fcce Ahmet E.","unstructured":"Ahmet E. Sariy\u00fcce , Kamer Kaya , Erik Saule , and Umit V. Catalyurek . 2013. Incremental algorithms for closeness centrality . In Proceedings of the IEEE International Conference on Big Data (ICBDA\u201913) . 118--122. Ahmet E. Sariy\u00fcce, Kamer Kaya, Erik Saule, and Umit V. Catalyurek. 2013. Incremental algorithms for closeness centrality. In Proceedings of the IEEE International Conference on Big Data (ICBDA\u201913). 118--122."},{"key":"e_1_2_1_34_1","volume-title":"Lie Quan Lee, and Andrew Lumsdaine","author":"Siek Jeremy G.","year":"2001","unstructured":"Jeremy G. Siek , Lie Quan Lee, and Andrew Lumsdaine . 2001 . The Boost Graph Library : User Guide and Reference Manual. Pearson Education. Retrieved from http:\/\/books.google.it\/books?id&equals;CPi7g1hjyIYC. Jeremy G. Siek, Lie Quan Lee, and Andrew Lumsdaine. 2001. The Boost Graph Library: User Guide and Reference Manual. Pearson Education. Retrieved from http:\/\/books.google.it\/books?id&equals;CPi7g1hjyIYC."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1017\/nws.2016.20"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1101884.1101889"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACC.2014.6858727"},{"key":"e_1_2_1_38_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 . Cambridge University Press . Retrieved from http:\/\/books.google.it\/books?id&equals;CAm2DpIqRUIC. Stanley Wasserman and Katherine Faust. 1994. Social Network Analysis: Methods and Applications. Cambridge University Press. Retrieved from http:\/\/books.google.it\/books?id&equals;CAm2DpIqRUIC."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.023"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214056"},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the 51st IEEE Annual Symposium on Foundations of Computer Science (FOCS\u201910)","author":"Virginia","unstructured":"Virginia V. Williams and Ryan Williams. 2010. Subcubic equivalences between path, matrix and triangle problems . In Proceedings of the 51st IEEE Annual Symposium on Foundations of Computer Science (FOCS\u201910) . 645--654. Virginia V. Williams and Ryan Williams. 2010. Subcubic equivalences between path, matrix and triangle problems. In Proceedings of the 51st IEEE Annual Symposium on Foundations of Computer Science (FOCS\u201910). 645--654."}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3344719","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3344719","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:54:27Z","timestamp":1750204467000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3344719"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9,24]]},"references-count":41,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2019,10,31]]}},"alternative-id":["10.1145\/3344719"],"URL":"https:\/\/doi.org\/10.1145\/3344719","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,9,24]]},"assertion":[{"value":"2016-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-09-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}