{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,23]],"date-time":"2026-03-23T14:42:36Z","timestamp":1774276956061,"version":"3.50.1"},"reference-count":51,"publisher":"MDPI AG","issue":"9","license":[{"start":{"date-parts":[[2020,8,29]],"date-time":"2020-08-29T00:00:00Z","timestamp":1598659200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100016394","name":"ANR","doi-asserted-by":"publisher","award":["ANR-19-CE23-0010"],"award-info":[{"award-number":["ANR-19-CE23-0010"]}],"id":[{"id":"10.13039\/501100016394","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003407","name":"MIUR","doi-asserted-by":"publisher","award":["AHeAD"],"award-info":[{"award-number":["AHeAD"]}],"id":[{"id":"10.13039\/501100003407","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004434","name":"University of Florence","doi-asserted-by":"publisher","award":["GRANTED"],"award-info":[{"award-number":["GRANTED"]}],"id":[{"id":"10.13039\/501100004434","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>The harmonic closeness centrality measure associates, to each node of a graph, the average of the inverse of its distances from all the other nodes (by assuming that unreachable nodes are at infinite distance). This notion has been adapted to temporal graphs (that is, graphs in which edges can appear and disappear during time) and in this paper we address the question of finding the top-k nodes for this metric. Computing the temporal closeness for one node can be done in O(m) time, where m is the number of temporal edges. Therefore computing exactly the closeness for all nodes, in order to find the ones with top closeness, would require O(nm) time, where n is the number of nodes. This time complexity is intractable for large temporal graphs. Instead, we show how this measure can be efficiently approximated by using a \u201cbackward\u201d temporal breadth-first search algorithm and a classical sampling technique. Our experimental results show that the approximation is excellent for nodes with high closeness, allowing us to detect them in practice in a fraction of the time needed for computing the exact closeness of all nodes. We validate our approach with an extensive set of experiments.<\/jats:p>","DOI":"10.3390\/a13090211","type":"journal-article","created":{"date-parts":[[2020,8,30]],"date-time":"2020-08-30T06:06:22Z","timestamp":1598767582000},"page":"211","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":16,"title":["Finding Top-k Nodes for Temporal Closeness in Large Temporal Graphs"],"prefix":"10.3390","volume":"13","author":[{"given":"Pierluigi","family":"Crescenzi","sequence":"first","affiliation":[{"name":"IRIF, CNRS, Universit\u00e9 de Paris, F-75013 Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cl\u00e9mence","family":"Magnien","sequence":"additional","affiliation":[{"name":"CNRS, LIP6, Sorbonne Universit\u00e9, F-75005 Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrea","family":"Marino","sequence":"additional","affiliation":[{"name":"Dipartimento di Statistica, Informatica, Applicazioni \u201cGiuseppe Parenti\u201d, Universit\u00e0 degli Studi di Firenze, I-50134 Firenze, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2020,8,29]]},"reference":[{"key":"ref_1","first-page":"16","article-title":"A Mathematical Model for Group Structures","volume":"7","author":"Bavelas","year":"1948","journal-title":"Appl. Anthropol."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/0378-8733(78)90021-7","article-title":"Centrality in social networks conceptual clarification","volume":"1","author":"Freeman","year":"1978","journal-title":"Soc. Netw."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1080\/0022250X.2001.9990249","article-title":"A Faster Algorithm for Betweenness Centrality","volume":"25","author":"Brandes","year":"2001","journal-title":"J. Math. Sociol."},{"key":"ref_4","first-page":"39","article-title":"Fast Approximation of Centrality","volume":"8","author":"Eppstein","year":"2004","journal-title":"J. Graph Alg. Appl."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Brandes, U., and Erlebach, T. (2005). Centrality Indices. Network Analysis: Methodological Foundations, Springer.","DOI":"10.1007\/b106453"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"971","DOI":"10.1017\/S0956792516000401","article-title":"Re-conceptualizing centrality in social networks","volume":"27","author":"Schoch","year":"2016","journal-title":"Eur. J. Appl. Math."},{"key":"ref_7","unstructured":"David Schoch (2020, August 27). Periodic Table of Network Centrality. Available online: http:\/\/schochastics.net\/sna\/periodic.html."},{"key":"ref_8","unstructured":"Lin, N. (1976). Foundations of Social Research, McGraw-Hill."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"539","DOI":"10.1016\/S0378-4371(00)00311-3","article-title":"Harmony in the small-world","volume":"285","author":"Marchiori","year":"2000","journal-title":"Phys. A Stat. Mech. Its Appl."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3344719","article-title":"Computing Top-K Closeness Cent. Faster Unweighted Graphs","volume":"13","author":"Bergamini","year":"2019","journal-title":"ACM Trans. Knowl. Discov. Data"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1007\/978-3-642-11269-0_6","article-title":"The Complexity of Satisfiability of Small Depth Circuits","volume":"Volume 5917","author":"Calabro","year":"2009","journal-title":"Lecture Notes in Computer Science"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Cohen, E., Delling, D., Pajor, T., and Werneck, R.F. (2014, January 1\u20132). Computing Classic Closeness Centrality, at Scale. Proceedings of the Second ACM Conference on Online Social Networks, Dublin, Ireland.","DOI":"10.1145\/2660460.2660465"},{"key":"ref_13","unstructured":"(2020, August 27). NetworKit. Available online: https:\/\/networkit.github.io."},{"key":"ref_14","unstructured":"(2020, August 27). SageMath. Available online: http:\/\/www.sagemath.org."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/j.physrep.2012.03.001","article-title":"Temporal networks","volume":"519","author":"Holme","year":"2012","journal-title":"Phys. Rep."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1007\/s13278-018-0537-7","article-title":"Stream graphs and link streams for the modeling of interactions over time","volume":"8","author":"Latapy","year":"2018","journal-title":"Soc. Netw. Anal. Min."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1080\/15427951.2016.1177801","article-title":"An Introduction to Temporal Graphs: An Algorithmic Perspective","volume":"12","author":"Michail","year":"2016","journal-title":"Internet Math."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Tang, J.K., Musolesi, M., Mascolo, C., Latora, V., and Nicosia, V. (2010, January 22\u201325). Analysing information flows and key mediators through temporal centrality metrics. Proceedings of the 3rd Workshop on Social Network Systems, Paris, France.","DOI":"10.1145\/1852658.1852661"},{"key":"ref_19","unstructured":"Santoro, N., Quattrociocchi, W., Flocchini, P., Casteigts, A., and Amblard, F. (2011). Time-Varying Graphs and Social Network Analysis: Temporal Indicators and Metrics. arXiv."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"026107","DOI":"10.1103\/PhysRevE.85.026107","article-title":"Temporal node centrality in complex networks","volume":"85","author":"Kim","year":"2012","journal-title":"Phys. Rev. E"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"1550107","DOI":"10.1142\/S0129183115501077","article-title":"Measures of node centrality in mobile social networks","volume":"26","author":"Gao","year":"2015","journal-title":"Int. J. Mod. Phys. C"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Magnien, C., and Tarissan, F. (2015, January 25\u201328). Time Evolution of the Importance of Nodes in Dynamic Networks. Proceedings of the 2015 IEEE\/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), Paris, France.","DOI":"10.1145\/2808797.2809322"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Pereira, F.S.F., de Amo, S., and Gama, J. (2016, January 13\u201316). Evolving Centralities in Temporal Graphs: A Twitter Network Analysis. Proceedings of the 2016 17th IEEE International Conference on Mobile Data Management (MDM), Porto, Portugal.","DOI":"10.1109\/MDM.2016.88"},{"key":"ref_24","unstructured":"Pereira, F.S.F., de Amo, S., and Gama, J. (2016). Detecting Events in Evolving Social Networks through Node Centrality Analysis. CEUR Workshop Proceedings, STREAMEVOLV@ ECML-PKDD."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"160196","DOI":"10.1098\/rsos.160196","article-title":"Spatio-temporal networks: Reachability, centrality and robustness","volume":"3","author":"Williams","year":"2016","journal-title":"R. Soc. Open Sci."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Vi\u0161\u0148ovsk\u00fd, J. (2018). Evolving Networks and Social Network Analysis Methods and Techniques. Social Media and Journalism: Trends, Connections, Implications, IntechOpen.","DOI":"10.5772\/intechopen.73235"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"940","DOI":"10.1109\/TNSE.2018.2880344","article-title":"Centrality Metrics in Dynamic Networks: A Comparison Study","volume":"6","author":"Ghanem","year":"2019","journal-title":"IEEE Trans. Netw. Sci. Eng."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Wu, H., Huang, Y., Cheng, J., Li, J., and Ke, Y. (2016, January 16\u201320). Reachability and time-based path queries in temporal graphs. Proceedings of the 2016 IEEE 32nd International Conference on Data Engineering (ICDE), Helsinki, Finland.","DOI":"10.1109\/ICDE.2016.7498236"},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Kossinets, G., Kleinberg, J.M., and Watts, D.J. (2008, January 24\u201327). The Structure of Information Pathways in a Social Communication network. Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Las Vegas, LA, USA.","DOI":"10.1145\/1401890.1401945"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"180089","DOI":"10.1038\/sdata.2018.89","article-title":"A collection of public transport network data sets for 25 cities","volume":"5","author":"Kujala","year":"2018","journal-title":"Sci. Data"},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Crescenzi, P., Magnien, C., and Marino, A. (2019). Approximating the Temporal Neighbourhood Function of Large Temporal Graphs. Algorithms, 12.","DOI":"10.3390\/a12100211"},{"key":"ref_32","first-page":"1","article-title":"Connection Scan Algorithm","volume":"23","author":"Dibbelt","year":"2018","journal-title":"J. Exp. Alg."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1007\/s41060-019-00189-x","article-title":"Temporal betweenness centrality in dynamic graphs","volume":"9","author":"Tsalouchidou","year":"2020","journal-title":"Int. J. Data Sci. Anal."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"1215","DOI":"10.1016\/j.physleta.2019.01.041","article-title":"PageRank centrality for temporal networks","volume":"383","author":"Lv","year":"2019","journal-title":"Phys. Lett. A"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1016\/j.socnet.2018.02.002","article-title":"Embedding time in positions: Temporal measures of centrality for social network analysis","volume":"54","author":"Falzon","year":"2018","journal-title":"Soc. Netw."},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Ni, P., Hanai, M., Tan, W.J., and Cai, W. (2019, January 27\u201330). Efficient closeness centrality computation in time-evolving graphs. Proceedings of the 2019 IEEE\/ACM International Conference on Advances in Social Networks Analysis and Mining, Vancouver, Canada.","DOI":"10.1145\/3341161.3342865"},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Okamoto, K., Chen, W., and Li, X. (2008). Ranking of Closeness Centrality for Large-Scale Social Networks. International Workshop on Frontiers in Algorithmics, Springer.","DOI":"10.1007\/978-3-540-69311-6_21"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"432","DOI":"10.1016\/j.ipl.2014.03.006","article-title":"Heuristical top-k: Fast estimation of centralities in complex networks","volume":"114","author":"Merrer","year":"2014","journal-title":"Inf. Process. Lett."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1080\/17445760.2012.668546","article-title":"Time-varying graphs and dynamic networks","volume":"27","author":"Casteigts","year":"2012","journal-title":"Int. J. Parallel Emergent Distrib. Syst."},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Crescenzi, P., Grossi, R., Lanzi, L., and Marino, A. (2011). A Comparison of Three Algorithms for Approximating the Distance Distribution in Real-World Graphs. International Conference on Theory and Practice of Algorithms in (Computer) Systems, TAPAS; Springer.","DOI":"10.1007\/978-3-642-19754-3_11"},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Dubhashi, D.P., and Panconesi, A. (2009). Concentration of Measure for the Analysis of Randomized Algorithms, Cambridge University Press.","DOI":"10.1017\/CBO9780511581274"},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1145\/1052812.1052825","article-title":"Collecting the Internet AS-level Topology","volume":"35","author":"Zhang","year":"2005","journal-title":"ACM SIGCOMM Comput. Commun. Rev."},{"key":"ref_43","doi-asserted-by":"crossref","unstructured":"Kunegis, J. (2013, January 13\u201317). KONECT: The Koblenz Network Collection. Proceedings of the 22nd International Conference on World Wide Web, Rio de Janeiro, Brazil.","DOI":"10.1145\/2487788.2488173"},{"key":"ref_44","unstructured":"Kunegis, J. (2020, August 27). The KONECT Project. Available online: http:\/\/konect.cc."},{"key":"ref_45","unstructured":"IMDb (2020, August 27). IMDb Datasets. Available online: http:\/\/www.imdb.com\/interfaces."},{"key":"ref_46","doi-asserted-by":"crossref","unstructured":"Viswanath, B., Mislove, A., Cha, M., and Gummadi, K.P. (2009, January 17). On the Evolution of User Interaction in Facebook. Proceedings of the 2nd ACM Workshop on Online Social Networks, WOSN, Barcelona, Spain.","DOI":"10.1145\/1592665.1592675"},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1108\/AJIM-09-2013-0094","article-title":"Programmed method: Developing a toolset for capturing and analyzing tweets","volume":"66","author":"Borra","year":"2014","journal-title":"Aslib J. Inf. Manag."},{"key":"ref_48","unstructured":"Borra, E., and Rieder, B. (2020, August 27). Twitter Migrants Network. Available online: http:\/\/data.complexnetworks.fr\/Migrants\/."},{"key":"ref_49","doi-asserted-by":"crossref","unstructured":"Vigna, S. (2015, January 18\u201322). A Weighted Correlation Index for Rankings with Ties. Proceedings of the 24th International Conference on World Wide Web, Florence, Italy.","DOI":"10.1145\/2736277.2741088"},{"key":"ref_50","unstructured":"Gauvin, L., G\u00e9nois, M., Karsai, M., Kivel\u00e4, M., Takaguchi, T., Valdano, E., and Vestergaard, C.L. (2018). Randomized reference models for temporal networks. arXiv."},{"key":"ref_51","doi-asserted-by":"crossref","unstructured":"Olsen, P.W., Labouseur, A.G., and Hwang, J. (April, January 31). Efficient top-k closeness centrality search. Proceedings of the 2014 IEEE 30th International Conference on Data Engineering, Chicago, IL, USA.","DOI":"10.1109\/ICDE.2014.6816651"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/9\/211\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T10:04:44Z","timestamp":1760177084000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/9\/211"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,29]]},"references-count":51,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2020,9]]}},"alternative-id":["a13090211"],"URL":"https:\/\/doi.org\/10.3390\/a13090211","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,8,29]]}}}