IDEAS home Printed from https://ideas.repec.org/a/nat/natcom/v15y2024i1d10.1038_s41467-024-54280-4.html
   My bibliography  Save this article

An embedding-based distance for temporal graphs

Author

Listed:
  • Lorenzo Dall’Amico

    (ISI Foundation)

  • Alain Barrat

    (CPT)

  • Ciro Cattuto

    (ISI Foundation)

Abstract

Temporal graphs are commonly used to represent time-resolved relations between entities in many natural and artificial systems. Many techniques were devised to investigate the evolution of temporal graphs by comparing their state at different time points. However, quantifying the similarity between temporal graphs as a whole is an open problem. Here, we use embeddings based on time-respecting random walks to introduce a new notion of distance between temporal graphs. This distance is well-defined for pairs of temporal graphs with different numbers of nodes and different time spans. We study the case of a matched pair of graphs, when a known relation exists between their nodes, and the case of unmatched graphs, when such a relation is unavailable and the graphs may be of different sizes. We use empirical and synthetic temporal network data to show that the distance we introduce discriminates graphs with different topological and temporal properties. We provide an efficient implementation of the distance computation suitable for large-scale temporal graphs.

Suggested Citation

  • Lorenzo Dall’Amico & Alain Barrat & Ciro Cattuto, 2024. "An embedding-based distance for temporal graphs," Nature Communications, Nature, vol. 15(1), pages 1-11, December.
    • Handle: RePEc:nat:natcom:v:15:y:2024:i:1:d:10.1038_s41467-024-54280-4
    DOI: 10.1038/s41467-024-54280-4
    as

    Download full text from publisher

    File URL: https://www.nature.com/articles/s41467-024-54280-4
    File Function: Abstract
    Download Restriction: no
    File URL: https://libkey.io/10.1038/s41467-024-54280-4?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Jari Saramäki & Petter Holme, 2015. "Exploring temporal networks with greedy walks," The European Physical Journal B: Condensed Matter and Complex Systems, Springer;EDP Sciences, vol. 88(12), pages 1-8, December.
    2. G. Cencetti & G. Santin & A. Longa & E. Pigani & A. Barrat & C. Cattuto & S. Lehmann & M. Salathé & B. Lepri, 2021. "Digital proximity tracing on empirical contact networks for pandemic control," Nature Communications, Nature, vol. 12(1), pages 1-12, December.
    3. Ciro Cattuto & Wouter Van den Broeck & Alain Barrat & Vittoria Colizza & Jean-François Pinton & Alessandro Vespignani, 2010. "Dynamics of Person-to-Person Interactions from Distributed RFID Sensor Networks," PLOS ONE, Public Library of Science, vol. 5(7), pages 1-9, July.
    4. Remy Cazabet & Pablo Jensen & Pierre Borgnat, 2018. "Tracking the evolution of temporal patterns of usage in bicycle-Sharing systems using nonnegative matrix factorization on multiple sliding windows," International Journal of Urban Sciences, Taylor & Francis Journals, vol. 22(2), pages 147-161, April.
    5. Dina Mistry & Maria Litvinova & Ana Pastore y Piontti & Matteo Chinazzi & Laura Fumanelli & Marcelo F. C. Gomes & Syed A. Haque & Quan-Hui Liu & Kunpeng Mu & Xinyue Xiong & M. Elizabeth Halloran & Ira, 2021. "Inferring high-resolution human mixing patterns for disease modeling," Nature Communications, Nature, vol. 12(1), pages 1-12, December.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Stefano Guarino & Enrico Mastrostefano & Massimo Bernaschi & Alessandro Celestini & Marco Cianfriglia & Davide Torre & Lena Rebecca Zastrow, 2021. "Inferring Urban Social Networks from Publicly Available Data," Future Internet, MDPI, vol. 13(5), pages 1-45, April.
    2. Gregory, Steve, 2012. "Ordered community structure in networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 391(8), pages 2752-2763.
    3. De Martino, Giuseppe & Spina, Serena, 2015. "Exploiting the time-dynamics of news diffusion on the Internet through a generalized Susceptible–Infected model," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 438(C), pages 634-644.
    4. Kobayashi, Teruyoshi & Takaguchi, Taro, 2018. "Identifying relationship lending in the interbank market: A network approach," Journal of Banking & Finance, Elsevier, vol. 97(C), pages 20-36.
    5. Thomas Ash & Antonio M. Bento & Daniel Kaffine & Akhil Rao & Ana I. Bento, 2022. "Disease-economy trade-offs under alternative epidemic control strategies," Nature Communications, Nature, vol. 13(1), pages 1-14, December.
    6. Leto Peel & Tiago P. Peixoto & Manlio De Domenico, 2022. "Statistical inference links data and theory in network science," Nature Communications, Nature, vol. 13(1), pages 1-15, December.
    7. Fabio Caccioli & Paolo Barucca & Teruyoshi Kobayashi, 2018. "Network models of financial systemic risk: a review," Journal of Computational Social Science, Springer, vol. 1(1), pages 81-114, January.
    8. Ghahramani, Ali & Pantelic, Jovan & Lindberg, Casey & Mehl, Matthias & Srinivasan, Karthik & Gilligan, Brian & Arens, Edward, 2018. "Learning occupants’ workplace interactions from wearable and stationary ambient sensing systems," Applied Energy, Elsevier, vol. 230(C), pages 42-51.
    9. Mark Kibanov & Raphael H. Heiberger & Simone Rödder & Martin Atzmueller & Gerd Stumme, 2019. "Social studies of scholarly life with sensor-based ethnographic observations," Scientometrics, Springer;Akadémiai Kiadó, vol. 119(3), pages 1387-1428, June.
    10. Masoud Shakiba & Azam Zavvari & Nader Aleebrahim & Mandeep Jit Singh, 2016. "Evaluating the academic trend of RFID technology based on SCI and SSCI publications from 2001 to 2014," Scientometrics, Springer;Akadémiai Kiadó, vol. 109(1), pages 591-614, October.
    11. Laura Ozella & Francesco Gesualdo & Michele Tizzoni & Caterina Rizzo & Elisabetta Pandolfi & Ilaria Campagna & Alberto Eugenio Tozzi & Ciro Cattuto, 2018. "Close encounters between infants and household members measured through wearable proximity sensors," PLOS ONE, Public Library of Science, vol. 13(6), pages 1-16, June.
    12. Massimo Riccaboni & Anna Romiti & Gianna Giudicati, 2011. "Co-experience Network Dynamics: Lessons from the Dance Floor," DISA Working Papers 2011/02, Department of Computer and Management Sciences, University of Trento, Italy, revised 28 Mar 2011.
    13. Barmak, D.H. & Dorso, C.O. & Otero, M., 2016. "Modelling dengue epidemic spreading with human mobility," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 447(C), pages 129-140.
    14. Mikaela Irene D. Fudolig & Daniel Monsivais & Kunal Bhattacharya & Hang-Hyun Jo & Kimmo Kaski, 2020. "Different patterns of social closeness observed in mobile phone communication," Journal of Computational Social Science, Springer, vol. 3(1), pages 1-17, April.
    15. Benjamin Faucher & Rania Assab & Jonathan Roux & Daniel Levy-Bruhl & Cécile Tran Kiem & Simon Cauchemez & Laura Zanetti & Vittoria Colizza & Pierre-Yves Boëlle & Chiara Poletto, 2022. "Agent-based modelling of reactive vaccination of workplaces and schools against COVID-19," Nature Communications, Nature, vol. 13(1), pages 1-11, December.
    16. Teruyoshi Kobayashi & Taro Takaguchi, 2017. "Significant ties: Identifying relationship lending in temporal interbank networks," Discussion Papers 1717, Graduate School of Economics, Kobe University.
    17. José F. Fontanari, 2023. "Stochastic Simulations of Casual Groups," Mathematics, MDPI, vol. 11(9), pages 1-16, May.
    18. Matthew Baggetta & Brad R. Fulton & Zoe Caplan, 2022. "Space and Interaction in Civil Society Organizations: An Exploratory Study in a US City," Social Inclusion, Cogitatio Press, vol. 10(3), pages 307-318.
    19. Dun, Han & Shuting, Yan & She, Han & Lingfei, Qian & Chris, Ampimah Benjamin, 2019. "Research on how the difference of personal propagation ability influences the epidemic spreading in activity-driven network," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 514(C), pages 311-318.
    20. Nan Zhang & Boni Su & Pak-To Chan & Te Miao & Peihua Wang & Yuguo Li, 2020. "Infection Spread and High-Resolution Detection of Close Contact Behaviors," IJERPH, MDPI, vol. 17(4), pages 1-18, February.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:nat:natcom:v:15:y:2024:i:1:d:10.1038_s41467-024-54280-4. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.nature.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.