{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:49:02Z","timestamp":1760240942566,"version":"build-2065373602"},"reference-count":42,"publisher":"MDPI AG","issue":"10","license":[{"start":{"date-parts":[[2019,10,10]],"date-time":"2019-10-10T00:00:00Z","timestamp":1570665600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"ANR (French National Agency of Research) under grant ANR-15-CE38-0001 (Algodiv)","award":["ANR-15-CE38-0001"],"award-info":[{"award-number":["ANR-15-CE38-0001"]}]},{"name":"Thales within the CLEAR SU-Thales joint lab","award":["NN"],"award-info":[{"award-number":["NN"]}]},{"name":"the Ile-de-France program FUI21 under grant 16010629 (iTRAC)","award":["16010629"],"award-info":[{"award-number":["16010629"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Temporal networks are graphs in which edges have temporal labels, specifying their starting times and their traversal times. Several notions of distances between two nodes in a temporal network can be analyzed, by referring, for example, to the earliest arrival time or to the latest starting time of a temporal path connecting the two nodes. In this paper, we mostly refer to the notion of temporal reachability by using the earliest arrival time. In particular, we first show how the sketch approach, which has already been used in the case of classical graphs, can be applied to the case of temporal networks in order to approximately compute the sizes of the temporal cones of a temporal network. By making use of this approach, we subsequently show how we can approximate the temporal neighborhood function (that is, the number of pairs of nodes reachable from one another in a given time interval) of large temporal networks in a few seconds. Finally, we apply our algorithm in order to analyze and compare the behavior of 25 public transportation temporal networks. Our results can be easily adapted to the case in which we want to refer to the notion of distance based on the latest starting time.<\/jats:p>","DOI":"10.3390\/a12100211","type":"journal-article","created":{"date-parts":[[2019,10,11]],"date-time":"2019-10-11T03:07:11Z","timestamp":1570763231000},"page":"211","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Approximating the Temporal Neighbourhood Function of Large Temporal Graphs"],"prefix":"10.3390","volume":"12","author":[{"given":"Pierluigi","family":"Crescenzi","sequence":"first","affiliation":[{"name":"Institut de Recherche en Informatique Fondamentale, Centre National de la Recherche Scientifique, Universit\u00e9 de Paris, F-75013 Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cl\u00e9mence","family":"Magnien","sequence":"additional","affiliation":[{"name":"Centre National de la Recherche Scientifique, Laboratoire d\u2019Informatique de Paris 6, 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":[[2019,10,10]]},"reference":[{"key":"ref_1","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_2","doi-asserted-by":"crossref","unstructured":"Bhadra, S., and Ferreira, A. (2003, January 8\u201310). Complexity of Connected Components in Evolving Graphs and the Computation of Multicast Trees in Dynamic Networks. Proceedings of the ADHOC-NOW, Montreal, QC, Canada.","DOI":"10.1007\/978-3-540-39611-6_23"},{"key":"ref_3","first-page":"387","article-title":"Time-varying graphs and dynamic networks","volume":"27","author":"Casteigts","year":"2012","journal-title":"IJPEDS"},{"key":"ref_4","unstructured":"Borgnat, P., Fleury, E., Guillaume, J., Magnien, C., Robardet, C., and Scherrer, A. (2007). Evolving networks. Mining Massive Data Sets for Security, IOS Press."},{"key":"ref_5","first-page":"61:1","article-title":"Stream graphs and link streams for the modeling of interactions over time","volume":"8","author":"Latapy","year":"2018","journal-title":"Soc. Netw. Analys. Min."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"721","DOI":"10.14778\/2732939.2732945","article-title":"Path Problems in Temporal Graphs","volume":"7","author":"Wu","year":"2014","journal-title":"Proc. VLDB Endow."},{"key":"ref_7","unstructured":"Palmer, C.R., Gibbons, P.B., and Faloutsos, C. (2002, January 23\u201326). ANF: A fast and scalable tool for data mining in massive graphs. Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Edmonton, AB, Canada."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Boldi, P., Rosa, M., and Vigna, S. (2011). HyperANF: Approximating the neighbourhood function of very large graphs on a budget. arXiv.","DOI":"10.1145\/1963405.1963493"},{"key":"ref_9","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 32nd IEEE International Conference on Data Engineering, ICDE, Helsinki, Finland.","DOI":"10.1109\/ICDE.2016.7498236"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1006\/jcss.1997.1534","article-title":"Size-Estimation Framework with Applications to Transitive Closure and Reachability","volume":"55","author":"Cohen","year":"1997","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_11","first-page":"213","article-title":"Tighter estimation using bottom k sketches","volume":"1","author":"Cohen","year":"2008","journal-title":"PVLDB"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Cohen, E. (2016). All-Distances Sketches. Encyclopedia of Algorithms, Springer.","DOI":"10.1007\/978-1-4939-2864-4_574"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Crescenzi, P., and Marino, A. (2019). Degrees of Separation and Diameter in Large Graphs. Encyclopedia of Big Data Technologies, Springer.","DOI":"10.1007\/978-3-319-77525-8_59"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Kujala, R., Weckstr\u00f6m, C., Darst, R., Madlenoci\u0107, M., and Saram\u00e4ki, J. (2018). A collection of public transport network data sets for 25 cities. Sci. Data, 5.","DOI":"10.1038\/sdata.2018.89"},{"key":"ref_15","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, NV, USA.","DOI":"10.1145\/1401890.1401945"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Huang, S., Fu, A.W.C., and Liu, R. (June, January 31). Minimum Spanning Trees in Temporal Graphs. Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, Melbourne, Australia.","DOI":"10.1145\/2723372.2723717"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1142\/S0129054115500288","article-title":"Shortest, Fastest, and Foremost Broadcast in Dynamic Networks","volume":"26","author":"Casteigts","year":"2015","journal-title":"Int. J. Found. Comput. Sci."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Bast, H., Delling, D., Goldberg, A.V., M\u00fcller-Hannemann, M., Pajor, T., Sanders, P., Wagner, D., and Werneck, R.F. (2016). Route Planning in Transportation Networks. Algorithm Engineering\u2014Selected Results and Surveys, Springer.","DOI":"10.1007\/978-3-319-49487-6_2"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Kosowski, A., and Viennot, L. (2017, January 16\u201319). Beyond Highway Dimension: Small Distance Labels Using Tree Skeletons. Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, Barcelona, Spain.","DOI":"10.1137\/1.9781611974782.95"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1016\/j.ejor.2014.06.046","article-title":"Finding optimal hyperpaths in large transit networks with realistic headway distributions","volume":"240","author":"Li","year":"2015","journal-title":"Eur. J. Oper. Res."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"1092","DOI":"10.1016\/j.tre.2011.04.009","article-title":"Hub location problems in transportation networks","volume":"47","author":"Gelareh","year":"2011","journal-title":"Transp. Res. Part E: Logist. Transp. Rev."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"434","DOI":"10.1016\/j.trb.2009.11.001","article-title":"Structure of competitive transit networks","volume":"44","author":"Daganzo","year":"2010","journal-title":"Transp. Res. Part B Methodol."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1016\/j.tra.2010.02.003","article-title":"Identifying critical road segments and measuring system-wide robustness in transportation networks with isolating links: A link-based capacity-reduction approach","volume":"44","author":"Sullivan","year":"2010","journal-title":"Transp. Res. Part A Policy Pract."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"1633","DOI":"10.1016\/j.cor.2011.09.017","article-title":"Measuring and maximizing resilience of freight transportation networks","volume":"39","author":"Zhang","year":"2012","journal-title":"Comput. Oper. Res."},{"key":"ref_25","first-page":"1066","article-title":"Performance indicators for public transit connectivity in multi-modal transportation networks","volume":"46","author":"Mishra","year":"2012","journal-title":"Transp. Res. Part A: Policy Pract."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"911","DOI":"10.1002\/asi.21015","article-title":"Patterns and dynamics of users\u2019 behavior and interaction: Network analysis of an online community","volume":"60","author":"Panzarasa","year":"2009","journal-title":"J. Am. Soc. Inf. Sci. Technol."},{"key":"ref_27","unstructured":"Leskovec, J., and Krevl, A. (2019, October 10). SNAP Datasets: Stanford Large Network Dataset Collection. Available online: http:\/\/snap.stanford.edu\/data."},{"key":"ref_28","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, Barcelona, Spain.","DOI":"10.1145\/1592665.1592675"},{"key":"ref_29","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_30","unstructured":"Institute of Web Science and Technologies (2019, October 10). The Koblenz Network Collection. Available online: http:\/\/konect.uni-koblenz.de."},{"key":"ref_31","unstructured":"IMDb (2019, October 10). IMDb Datasets. Available online: http:\/\/www.imdb.com\/interfaces."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"1755","DOI":"10.1109\/TMC.2010.247","article-title":"Density-Aware Routing in Highly Dynamic DTNs: The RollerNet Case","volume":"10","author":"Tournoux","year":"2011","journal-title":"IEEE Trans. Mob. Comput."},{"key":"ref_33","unstructured":"Crawdad (2019, October 10). Rollernet dataset. Available online: https:\/\/crawdad.org\/upmc\/rollernet\/20090202\/."},{"key":"ref_34","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":"SIGCOMM Comput. Commun. Rev."},{"key":"ref_35","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_36","unstructured":"Borra, E., and Rieder, B. (2019, October 10). Twitter migrants network. Available online: http:\/\/data.complexnetworks.fr\/Migrants\/."},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Leskovec, J., Huttenlocher, D., and Kleinberg, J. (2010, January 23\u201326). Governance in Social Media: A Case Study of the Wikipedia Promotion Process. Proceedings of the Conference on Weblogs and Social Media, Washington, DC, USA.","DOI":"10.1609\/icwsm.v4i1.14013"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1016\/0022-0000(85)90041-8","article-title":"Probabilistic Counting Algorithms for Data Base Applications","volume":"31","author":"Flajolet","year":"1985","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Crescenzi, P., Grossi, R., Imbrenda, C., Lanzi, L., and Marino, A. (2010). Finding the Diameter in Real-World Graphs-Experimentally Turning a Lower Bound into an Upper Bound, ESA.","DOI":"10.1007\/978-3-642-15775-2_26"},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/j.tcs.2015.02.033","article-title":"Fast diameter and radius BFS-based computation in (weakly connected) real-world graphs: With an application to the six degrees of separation games","volume":"586","author":"Borassi","year":"2015","journal-title":"Theor. Comput. Sci."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"39","DOI":"10.7155\/jgaa.00081","article-title":"Fast Approximation of Centrality","volume":"8","author":"Eppstein","year":"2004","journal-title":"J. Graph Algorithms Appl."},{"key":"ref_42","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 IEEE\/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), Paris, France.","DOI":"10.1145\/2808797.2809322"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/10\/211\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T13:29:06Z","timestamp":1760189346000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/10\/211"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10,10]]},"references-count":42,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2019,10]]}},"alternative-id":["a12100211"],"URL":"https:\/\/doi.org\/10.3390\/a12100211","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2019,10,10]]}}}