{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,2]],"date-time":"2026-04-02T18:24:48Z","timestamp":1775154288115,"version":"3.50.1"},"reference-count":54,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,1,8]],"date-time":"2022-01-08T00:00:00Z","timestamp":1641600000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,1,8]],"date-time":"2022-01-08T00:00:00Z","timestamp":1641600000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["EXC-2047\/1 - 390685813"],"award-info":[{"award-number":["EXC-2047\/1 - 390685813"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Knowl Inf Syst"],"published-print":{"date-parts":[[2022,2]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The closeness centrality of a vertex in a classical static graph is the reciprocal of the sum of the distances to all other vertices. However, networks are often dynamic and change over time. Temporal distances take these dynamics into account. In this work, we consider the harmonic temporal closeness with respect to the shortest duration distance. We introduce an efficient algorithm for computing the exact top-<jats:italic>k<\/jats:italic>temporal closeness values and the corresponding vertices. The algorithm can be generalized to the task of computing all closeness values. Furthermore, we derive heuristic modifications that perform well on real-world data sets and drastically reduce the running times. For the case that edge traversal takes an equal amount of time for all edges, we lift two approximation algorithms to the temporal domain. The algorithms approximate the transitive closure of a temporal graph (which is an essential ingredient for the top-<jats:italic>k<\/jats:italic>algorithm) and the temporal closeness for all vertices, respectively, with high probability. We experimentally evaluate all our new approaches on real-world data sets and show that they lead to drastically reduced running times while keeping high quality in many cases. Moreover, we demonstrate that the top-<jats:italic>k<\/jats:italic>temporal and static closeness vertex sets differ quite largely in the considered temporal networks.<\/jats:p>","DOI":"10.1007\/s10115-021-01639-4","type":"journal-article","created":{"date-parts":[[2022,1,8]],"date-time":"2022-01-08T05:02:30Z","timestamp":1641618150000},"page":"507-535","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Computing top-k temporal closeness in temporal networks"],"prefix":"10.1007","volume":"64","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2526-8762","authenticated-orcid":false,"given":"Lutz","family":"Oettershagen","sequence":"first","affiliation":[]},{"given":"Petra","family":"Mutzel","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,1,8]]},"reference":[{"issue":"6","key":"1639_CR1","doi-asserted-by":"publisher","first-page":"725","DOI":"10.1121\/1.1906679","volume":"22","author":"A Bavelas","year":"1950","unstructured":"Bavelas A (1950) Communication patterns in task-oriented groups. The J Acoust Soc Am 22(6):725\u2013730","journal-title":"The J Acoust Soc Am"},{"issue":"1","key":"1639_CR2","doi-asserted-by":"publisher","first-page":"32:1","DOI":"10.1007\/s41109-018-0080-5","volume":"3","author":"F B\u00e9res","year":"2018","unstructured":"B\u00e9res F, P\u00e1lovics R, Ol\u00e1h A, Bencz\u00far Andr\u00e1s A (2018) Temporal walk based centrality metric for graph streams. Appl Netw Sci 3(1):32:1-32:26","journal-title":"Appl Netw Sci"},{"issue":"5","key":"1639_CR3","doi-asserted-by":"publisher","first-page":"53:1","DOI":"10.1145\/3344719","volume":"13","author":"E Bergamini","year":"2019","unstructured":"Bergamini E, Borassi M, Crescenzi P, Marino A, Meyerhenke H (2019) Computing top-k closeness centrality faster in unweighted graphs. ACM Trans Knowl Discov Data 13(5):53:1-53:40","journal-title":"ACM Trans Knowl Discov Data"},{"key":"1639_CR4","doi-asserted-by":"crossref","unstructured":"Bisenius P, Bergamini E, Angriman E, and Meyerhenke H (2018) Computing top-k closeness centrality in fully-dynamic graphs. In: Proceedings of the twentieth workshop on algorithm engineering and experiments, ALENEX, pp. 21\u201335. SIAM","DOI":"10.1137\/1.9781611975055.3"},{"key":"1639_CR5","doi-asserted-by":"crossref","unstructured":"Braha D and Bar-Yam Y (2009) Time-dependent complex networks: dynamic centrality, dynamic motifs, and cycles of social interactions. In: Adaptive Networks, Springer, pp. 39\u201350","DOI":"10.1007\/978-3-642-01284-6_3"},{"issue":"2","key":"1639_CR6","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1080\/0022250X.2001.9990249","volume":"25","author":"Ulrik Brandes","year":"2001","unstructured":"Brandes Ulrik (2001) A faster algorithm for betweenness centrality. The J Math Sociol 25(2):163\u2013177","journal-title":"The J Math Sociol"},{"issue":"02","key":"1639_CR7","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1142\/S0129054103001728","volume":"14","author":"B-M Bui-Xuan","year":"2003","unstructured":"Bui-Xuan B-M, Ferreira A, Jarry A (2003) Computing shortest, fastest, and foremost journeys in dynamic networks. Int J Found Comput Sci 14(02):267\u2013285","journal-title":"Int J Found Comput Sci"},{"issue":"3","key":"1639_CR8","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1006\/jcss.1997.1534","volume":"55","author":"E Cohen","year":"1997","unstructured":"Cohen E (1997) Size-estimation framework with applications to transitive closure and reachability. J Comput Syst Sci 55(3):441\u2013453","journal-title":"J Comput Syst Sci"},{"key":"1639_CR9","doi-asserted-by":"crossref","unstructured":"Cohen E, Delling D, Pajor T, and Werneck RF (2014) Computing classic closeness centrality, at scale. In: Proceedings of the second ACM conference on Online social networks, pp. 37\u201350","DOI":"10.1145\/2660460.2660465"},{"issue":"3","key":"1639_CR10","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1016\/0022-247X(66)90009-6","volume":"14","author":"KL Cooke","year":"1966","unstructured":"Cooke KL, Halsey E (1966) The shortest route through a network with time-dependent internodal transit times. J Math Anal Appl 14(3):493\u2013498","journal-title":"J Math Anal Appl"},{"issue":"9","key":"1639_CR11","doi-asserted-by":"publisher","first-page":"211","DOI":"10.3390\/a13090211","volume":"13","author":"P Crescenzi","year":"2020","unstructured":"Crescenzi P, Magnien Cl\u00e9mence, Marino A (2020) Finding top-k nodes for temporal closeness in large temporal graphs. Algorithms 13(9):211","journal-title":"Algorithms"},{"issue":"1","key":"1639_CR12","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/s13278-018-0493-2","volume":"8","author":"Kousik Das","year":"2018","unstructured":"Das Kousik, Samanta S, Pal M (2018) Study on centrality measures in social networks: a survey. Soc Netw Anal Min 8(1):13","journal-title":"Soc Netw Anal Min"},{"key":"1639_CR13","unstructured":"Eppstein D, Wang J (2001) Fast approximation of centrality. In: Proceedings of the twelfth annual symposium on discrete algorithms, January 7-9, 2001, Washington, DC, USA. ACM\/SIAM, pp. 228\u2013229"},{"key":"1639_CR14","doi-asserted-by":"crossref","unstructured":"Grando F, Noble D, and Lamb LC (2016) An analysis of centrality measures for complex and social networks. In: 2016 IEEE Global Communications Conference (GLOBECOM), pp. 1\u20136. IEEE","DOI":"10.1109\/GLOCOM.2016.7841580"},{"issue":"7","key":"1639_CR15","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/S0895-7177(97)00050-2","volume":"25","author":"F Harary","year":"1997","unstructured":"Harary F, Gupta G (1997) Dynamic graph models. Math Comput Model 25(7):79\u201387","journal-title":"Math Comput Model"},{"key":"1639_CR16","doi-asserted-by":"crossref","unstructured":"Hoeffding W (1994) Probability inequalities for sums of bounded random variables. In: The collected works of Wassily Hoeffding, pp. 409\u2013426. Springer: New York, NY","DOI":"10.1007\/978-1-4612-0865-5_26"},{"issue":"1","key":"1639_CR17","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1140\/epjds5","volume":"1","author":"T Hogg","year":"2012","unstructured":"Hogg T, Lerman Kristina (2012) Social dynamics of digg. EPJ Data Sci 1(1):5","journal-title":"EPJ Data Sci"},{"issue":"9","key":"1639_CR18","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1140\/epjb\/e2015-60657-4","volume":"88","author":"Petter Holme","year":"2015","unstructured":"Holme Petter (2015) Modern temporal network theory: a colloquium. The Eur Phys J B 88(9):234","journal-title":"The Eur Phys J B"},{"key":"1639_CR19","unstructured":"Huang S, Cheng J, and Wu H (2014) Temporal graph traversals: definitions, algorithms, and applications. CoRR, abs\/1401.1919"},{"issue":"1","key":"1639_CR20","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1016\/j.jtbi.2010.11.033","volume":"271","author":"L Isella","year":"2011","unstructured":"Isella L, Stehl\u00e9 J, Barrat A, Cattuto C, Pinton J-F, Van den Broeck W (2011) What\u2019s in a crowd? Analysis of face-to-face behavioral networks. J Theor Biol 271(1):166\u2013180","journal-title":"J Theor Biol"},{"issue":"4","key":"1639_CR21","doi-asserted-by":"publisher","first-page":"820","DOI":"10.1006\/jcss.2002.1829","volume":"64","author":"D Kempe","year":"2002","unstructured":"Kempe D, Kleinberg JM, Kumar A (2002) Connectivity and inference problems for temporal networks. J Comput Syst Sci 64(4):820\u2013842","journal-title":"J Comput Syst Sci"},{"key":"1639_CR22","doi-asserted-by":"publisher","first-page":"105","DOI":"10.4086\/toc.2015.v011a004","volume":"11","author":"D Kempe","year":"2015","unstructured":"Kempe D, Kleinberg JM, Tardos \u00c9 (2015) Maximizing the spread of influence through a social network. Theory Comput 11:105\u2013147","journal-title":"Theory Comput"},{"issue":"1\/2","key":"1639_CR23","doi-asserted-by":"publisher","first-page":"81","DOI":"10.2307\/2332226","volume":"30","author":"MG Kendall","year":"1938","unstructured":"Kendall MG (1938) A new measure of rank correlation. Biometrika 30(1\/2):81\u201393","journal-title":"Biometrika"},{"issue":"3","key":"1639_CR24","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1093\/biomet\/33.3.239","volume":"33","author":"MG Kendall","year":"1945","unstructured":"Kendall MG (1945) The treatment of ties in ranking problems. Biometrika 33(3):239\u2013251","journal-title":"Biometrika"},{"issue":"2","key":"1639_CR25","doi-asserted-by":"publisher","first-page":"026107","DOI":"10.1103\/PhysRevE.85.026107","volume":"85","author":"H Kim","year":"2012","unstructured":"Kim H, Anderson R (2012) Temporal node centrality in complex networks. Phys Rev E 85(2):026107","journal-title":"Phys Rev E"},{"issue":"5757","key":"1639_CR26","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1126\/science.1116869","volume":"311","author":"Gueorgi Kossinets","year":"2006","unstructured":"Kossinets Gueorgi, Watts DJ (2006) Empirical analysis of an evolving social network. Science 311(5757):88\u201390","journal-title":"Science"},{"issue":"6","key":"1639_CR27","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1007\/s12599-010-0127-3","volume":"2","author":"A Landherr","year":"2010","unstructured":"Landherr A, Friedl B, Heidemann J (2010) A critical review of centrality measures in social networks. Bus Inform Syst Eng 2(6):371\u2013385","journal-title":"Bus Inform Syst Eng"},{"issue":"1","key":"1639_CR28","doi-asserted-by":"publisher","first-page":"61:1","DOI":"10.1007\/s13278-018-0537-7","volume":"8","author":"M Latapy","year":"2018","unstructured":"Latapy M, Viard T, Magnien C (2018) Stream graphs and link streams for the modeling of interactions over time. Soc Netw Anal Min 8(1):61:1-61:29","journal-title":"Soc Netw Anal Min"},{"key":"1639_CR29","doi-asserted-by":"crossref","unstructured":"Leskovec J, Huttenlocher D, and Kleinberg J (2010) Governance in social media: a case study of the wikipedia promotion process. In: Fourth International AAAI conference on weblogs and social media","DOI":"10.1145\/1753326.1753532"},{"key":"1639_CR30","doi-asserted-by":"crossref","unstructured":"Leskovec J, Kleinberg J, and Faloutsos C (2007) Graph evolution: densification and shrinking diameters. ACM Trans Knowl Discov Data, 1(1):2\u2013es","DOI":"10.1145\/1217299.1217301"},{"issue":"3\u20134","key":"1639_CR31","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1016\/S0378-4371(00)00311-3","volume":"285","author":"M Marchiori","year":"2000","unstructured":"Marchiori M, Latora Vito (2000) Harmony in the small-world. Physica A Stati Mech Appl 285(3\u20134):539\u2013546","journal-title":"Physica A Stati Mech Appl"},{"issue":"1","key":"1639_CR32","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1038\/s41598-018-37186-2","volume":"9","author":"N Masuda","year":"2019","unstructured":"Masuda N, Holme Petter (2019) Detecting sequences of system states in temporal networks. Sci Rep 9(1):1\u201311","journal-title":"Sci Rep"},{"issue":"4","key":"1639_CR33","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1080\/15427951.2016.1177801","volume":"12","author":"Othon Michail","year":"2016","unstructured":"Michail Othon (2016) An introduction to temporal graphs: an algorithmic perspective. Internet Math. 12(4):239\u2013280","journal-title":"Internet Math."},{"key":"1639_CR34","doi-asserted-by":"crossref","unstructured":"Mislove A, Koppula HS, Gummadi KP, Druschel P, and Bhattacharjee B (2008) Growth of the flickr social network. In: Proceedings of the first workshop on Online social networks, pp. 25\u201330","DOI":"10.1145\/1397735.1397742"},{"key":"1639_CR35","unstructured":"Mislove AE (2009) Online social networks: measurement, analysis, and applications to distributed information systems. PhD thesis, Rice University"},{"key":"1639_CR36","doi-asserted-by":"crossref","unstructured":"Mutzel P and Oettershagen L (2019) On the enumeration of bicriteria temporal paths. In: Theory and applications of models of computation, TAMC, volume 11436 of lecture notes in computer science, Springer, pp. 518\u2013535","DOI":"10.1007\/978-3-030-14812-6_32"},{"key":"1639_CR37","doi-asserted-by":"crossref","unstructured":"Nicosia V, Tang J, Mascolo C, Musolesi M, Russo G, Latora V (2013) Graph metrics for temporal networks. In: Temporal Networks, Springer, pp. 15\u201340","DOI":"10.1007\/978-3-642-36461-7_2"},{"key":"1639_CR38","doi-asserted-by":"crossref","unstructured":"Oettershagen L and Mutzel P (2020) Efficient top-k temporal closeness calculation in temporal networks. In: 2020 IEEE international conference on data mining, ICDM, pp. 402\u2013411. IEEE","DOI":"10.1109\/ICDM50108.2020.00049"},{"key":"1639_CR39","doi-asserted-by":"crossref","unstructured":"Okamoto K, Chen W, and Li X-Y (2008) Ranking of closeness centrality for large-scale social networks. In: Frontiers in algorithmics, second annual international workshop, FAW. Springer, pp. 186\u2013195","DOI":"10.1007\/978-3-540-69311-6_21"},{"issue":"7136","key":"1639_CR40","doi-asserted-by":"publisher","first-page":"664","DOI":"10.1038\/nature05670","volume":"446","author":"G Palla","year":"2007","unstructured":"Palla G, Barab\u00e1si A-L, Vicsek T (2007) Quantifying social group evolution. Nature 446(7136):664\u2013667","journal-title":"Nature"},{"issue":"1","key":"1639_CR41","doi-asserted-by":"publisher","first-page":"016105","DOI":"10.1103\/PhysRevE.84.016105","volume":"84","author":"RK Pan","year":"2011","unstructured":"Pan RK, Saram\u00e4ki J (2011) Path lengths, correlations, and centrality in temporal networks. Phys Rev E 84(1):016105","journal-title":"Phys Rev E"},{"issue":"9","key":"1639_CR42","doi-asserted-by":"publisher","first-page":"3715","DOI":"10.1016\/j.eswa.2012.12.077","volume":"40","author":"U Redmond","year":"2013","unstructured":"Redmond U, Cunningham P (2013) A temporal network analysis reveals the unprofitability of arbitrage in the prosper marketplace. Exp Syst Appl 40(9):3715\u20133721","journal-title":"Exp Syst Appl"},{"key":"1639_CR43","doi-asserted-by":"crossref","unstructured":"Rodrigues FA (2019) Network centrality: an introduction. In: A mathematical modeling approach from nonlinear dynamics to complex systems, Springer, pp. 177\u2013196","DOI":"10.1007\/978-3-319-78512-7_10"},{"key":"1639_CR44","doi-asserted-by":"crossref","unstructured":"Rozenshtein P and Gionis A (2016) Temporal pagerank. In: Machine learning and knowledge discovery in databases - European Conference, ECML PKDD, volume 9852 of lecture notes in computer science, Springer, pp. 674\u2013689","DOI":"10.1007\/978-3-319-46227-1_42"},{"key":"1639_CR45","unstructured":"Santoro N, Quattrociocchi W, Flocchini P, Casteigts A, Amblard F (2011) Time-varying graphs and social network analysis: temporal indicators and metrics. https:\/\/arxiv.org\/abs\/1102.0629"},{"key":"1639_CR46","unstructured":"Saxena A and Iyengar S (2020) Centrality measures in complex networks: a survey. CoRR, abs\/2011.07190"},{"key":"1639_CR47","doi-asserted-by":"crossref","unstructured":"Sun J, Kunegis J, and Staab S (2016) Predicting user roles in social networks using transfer learning with feature transformation. In: IEEE international conference on data mining workshops, pp. 128\u2013135. IEEE Computer Society","DOI":"10.1109\/ICDMW.2016.0026"},{"key":"1639_CR48","doi-asserted-by":"crossref","unstructured":"Tang J, Leontiadis I, Scellato S, Nicosia V, Mascolo C, Musolesi M, and Latora V (2013) Applications of temporal graph metrics to real-world networks. In: Temporal Networks. Springer, pp. 135\u2013159","DOI":"10.1007\/978-3-642-36461-7_7"},{"key":"1639_CR49","doi-asserted-by":"crossref","unstructured":"Tang J, Musolesi M, Mascolo C, Latora V and Nicosia V (2010) Analysing information flows and key mediators through temporal centrality metrics. In: Proc 3rd Workshop on Social Network Systems, pp. 1\u20136","DOI":"10.1145\/1852658.1852661"},{"key":"1639_CR50","doi-asserted-by":"crossref","unstructured":"Tsalouchidou I, Baeza-Yates R, Bonchi F, Liao K, and Sellis T (2019) Temporal betweenness centrality in dynamic graphs. Int J Data Sci Analy, pp. 1\u201316","DOI":"10.1007\/s41060-019-00189-x"},{"key":"1639_CR51","doi-asserted-by":"crossref","unstructured":"Viswanath B, Mislove A, Cha M, and Gummadi KP (2009) On the evolution of user interaction in facebook. In: Proceedings of the 2nd ACM workshop on Online social networks, pp. 37\u201342","DOI":"10.1145\/1592665.1592675"},{"issue":"9","key":"1639_CR52","doi-asserted-by":"publisher","first-page":"721","DOI":"10.14778\/2732939.2732945","volume":"7","author":"W Huanhuan","year":"2014","unstructured":"Huanhuan W, Cheng J, Huang S, Ke Y, Yi L, Yanyan X (2014) Path problems in temporal graphs. Proc VLDB Endow 7(9):721\u2013732","journal-title":"Proc VLDB Endow"},{"issue":"10","key":"1639_CR53","doi-asserted-by":"publisher","first-page":"2107","DOI":"10.1002\/asi.21128","volume":"60","author":"E Yan","year":"2009","unstructured":"Yan E, Ding Y (2009) Applying centrality measures to impact analysis: a coauthorship network analysis. J Am Socr Inform Sci Technol 60(10):2107\u20132118","journal-title":"J Am Socr Inform Sci Technol"},{"issue":"1","key":"1639_CR54","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s40537-016-0062-3","volume":"4","author":"J Zhan","year":"2017","unstructured":"Zhan J, Gurung S, Parsa Sai Phani Krishna (2017) Identification of top-k nodes in large networks using Katz centrality. J Big Data 4(1):1\u201319","journal-title":"J Big Data"}],"container-title":["Knowledge and Information Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10115-021-01639-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10115-021-01639-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10115-021-01639-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,22]],"date-time":"2023-01-22T08:39:38Z","timestamp":1674376778000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10115-021-01639-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,8]]},"references-count":54,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,2]]}},"alternative-id":["1639"],"URL":"https:\/\/doi.org\/10.1007\/s10115-021-01639-4","relation":{},"ISSN":["0219-1377","0219-3116"],"issn-type":[{"value":"0219-1377","type":"print"},{"value":"0219-3116","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1,8]]},"assertion":[{"value":"29 January 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 November 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 December 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 January 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}