Document Open Access Logo

On Computing the Diameter of (Weighted) Link Streams

Authors Marco Calamai, Pierluigi Crescenzi, Andrea Marino

PDF
Thumbnail PDF

File

LIPIcs.SEA.2021.11.pdf
  • Filesize: 1.18 MB
  • 21 pages

Document Identifiers

Author Details

Marco Calamai
  • University of Florence, Italy
Pierluigi Crescenzi
  • Gran Sasso Science Institute, L'Aquila, Italy
Andrea Marino
  • University of Florence, Italy

Funding

Partially supported by MIUR under PRIN Project n. 20174LF3T8 AHeAD (Efficient Algorithms for HArnessing Networked Data), and by the University of Florence under Project GRANTED (GRaph Algorithms for Networked TEmporal Data).

Acknowledgements

We thank Filippo Brunelli and Laurent Viennot for several discussions concerning the complexity of computing single source (target) best paths in temporal graphs. We also thank Roberto Grossi for kindly providing us the computing platform.

Cite As Get BibTex

Marco Calamai, Pierluigi Crescenzi, and Andrea Marino. On Computing the Diameter of (Weighted) Link Streams. In 19th International Symposium on Experimental Algorithms (SEA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 190, pp. 11:1-11:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.SEA.2021.11

Abstract

A weighted link stream is a pair (V,𝔼) comprising V, the set of nodes, and 𝔼, the list of temporal edges (u,v,t,λ), where u,v are two nodes in V, t is the starting time of the temporal edge, and λ is its travel time. By making use of this model, different notions of diameter can be defined, which refer to the following distances: earliest arrival time, latest departure time, fastest time, and shortest time. After proving that any of these diameters cannot be computed in time sub-quadratic with respect to the number of temporal edges, we propose different algorithms (inspired by the approach used for computing the diameter of graphs) which allow us to compute, in practice very efficiently, the diameter of quite large real-world weighted link stream for several definitions of the diameter. Indeed, all the proposed algorithms require very often a very low number of single source (or target) best path computations. We verify the effectiveness of our approach by means of an extensive set of experiments on real-world link streams. We also experimentally prove that the temporal version of the well-known 2-sweep technique, for computing a lower bound on the diameter of a graph, is quite effective in the case of weighted link stream, by returning very often tight bounds.

Subject Classification

ACM Subject Classification
  • Theory of computation → Shortest paths
Keywords
  • Temporal graph
  • shortest path
  • diameter

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Supplementary Materials

References

  1. M. Borassi, D. Coudert, P. Crescenzi, and A. Marino. On computing the hyperbolicity of real-world graphs. In Proc. 23rd Annual European Symposium on Algorithms, pages 215-226, 2015. Google Scholar
  2. M. Borassi, P. Crescenzi, and M. Habib. Into the square: On the complexity of some quadratic-time solvable problems. Electron. Notes Theor. Comput. Sci., 322:51-67, 2016. Google Scholar
  3. M. Borassi, P. Crescenzi, M. Habib, W. A. Kosters, A. Marino, and F. W. Takes. Fast diameter and radius bfs-based computation in (weakly connected) real-world graphs: With an application to the six degrees of separation games. Theor. Comput. Sci., 586:59-80, 2015. Google Scholar
  4. F. Brunelli, P. Crescenzi, and L. Viennot. On computing pareto optimal paths in weighted time-dependent networks. Inf. Proc. Let., 168:106086, 2021. Google Scholar
  5. A. Casteigts, J. G. Peters, and J. Schoeters. Temporal cliques admit sparse spanners. In Proc. 46th ICALP, pages 134:1-134:14, 2019. Google Scholar
  6. P. Crescenzi, R. Grossi, M. Habib, L. Lanzi, and A. Marino. On computing the diameter of real-world undirected graphs. Theor. Comput. Sci., 514:84-95, 2013. Google Scholar
  7. P. Crescenzi, R. Grossi, C. Imbrenda, L. Lanzi, and A. Marino. Finding the diameter in real-world graphs - experimentally turning a lower bound into an upper bound. In Proc. 18th Annual European Symposium on Algorithms, pages 302-313, 2010. Google Scholar
  8. P. Crescenzi, R. Grossi, L. Lanzi, and A. Marino. On computing the diameter of real-world directed (weighted) graphs. In Proc. 11th International Symposium on Experimental Algorithms, pages 99-110. Springer, 2012. Google Scholar
  9. P. Crescenzi, C. Magnien, and A. Marino. Approximating the temporal neighbourhood function of large temporal graphs. Algorithms, 12(10):211, 2019. Google Scholar
  10. P. Crescenzi, C. Magnien, and A. Marino. Finding top-k nodes for temporal closeness in large temporal graphs. Algorithms, 13(9):211, 2020. Google Scholar
  11. IMDb. IMDb Datasets. URL: http://www.imdb.com/interfaces.
  12. R. Impagliazzo, R. Paturi, and F. Zane. Which problems have strongly exponential complexity? J. Comput. Syst. Sci., 63(4):512-530, 2001. Google Scholar
  13. R. Kujala, C. Weckström, R. Darst, M. Madlenocić, and J. Saramäki. A collection of public transport network data sets for 25 cities. Sci. Data, 5, 2018. Google Scholar
  14. M. Latapy, T. Viard, and C. Magnien. Stream graphs and link streams for the modeling of interactions over time. Soc. Netw. Anal. Min., 8(1):61:1-61:29, 2018. Google Scholar
  15. J. Leskovec. Stanford Large Network Dataset Collection (SNAP). URL: http://snap.stanford.edu/data/index.html.
  16. M. Ley. DBLP - some lessons learned. Proc. VLDB Endow., 2(2):1493-1500, 2009. Google Scholar
  17. Institute of Web Science and Technologies. The Koblenz Network Collection. Available online: URL: http://konect.uni-koblenz.de.
  18. F. W. Takes and W. A. Kosters. Determining the diameter of small world networks. In Proceedings of the 20th ACM Conference on Information and Knowledge Management, pages 1191-1196, 2011. Google Scholar
  19. F. W. Takes and W. A. Kosters. Computing the eccentricity distribution of large graphs. Algorithms, 6(1):100-118, 2013. Google Scholar
  20. Jie Tang, Jing Zhang, Limin Yao, Juanzi Li, Li Zhang, and Zhong Su. Arnetminer: extraction and mining of academic social networks. In Proc. 14th KDD, pages 990-998, 2008. Google Scholar
  21. V. Vassilevska Williams and R. Williams. Subcubic equivalences between path, matrix and triangle problems. In 51th Annual IEEE FOCS, pages 645-654, 2010. Google Scholar
  22. H. Wu, J. Cheng, S. Huang, Y. Ke, Y. Lu, and Y. Xu. Path problems in temporal graphs. Proc. of the VLDB Endowment, 7(9):721-732, 2014. Google Scholar
  23. H. Wu, J. Cheng, Y. Ke, S. Huang, Y. Huang, and H. Wu. Efficient algorithms for temporal path computation. IEEE Trans. on Knowl. and Data Eng., 28(11):2927-2942, 2016. Google Scholar
  24. B. Xuan, A. Ferreira, and A. Jarry. Computing shortest, fastest, and foremost journeys in dynamic networks. Int. J. of Found. of Comp. Sci., 14(02):267-285, 2003. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact