pith. sign in

arxiv: 1907.02146 · v1 · pith:LZ2TV4ACnew · submitted 2019-07-03 · 💻 cs.SI · cs.DM

On computing distances and latencies in Link Streams

Fr\'ed\'eric Simard This is my paper

Pith reviewed 2026-05-25 09:12 UTC · model grok-4.3

classification 💻 cs.SI cs.DM
keywords link streamstemporal networksdistanceslatenciesshortest pathscentralityalgorithmscomplexity bounds
0
0 comments X

The pith

Algorithms compute distances, latencies, and shortest fastest paths in link streams efficiently.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Link streams model temporal networks with time-varying connections. The paper presents multiple algorithms to calculate distances, latencies, and lengths of shortest fastest paths in these objects. Each algorithm includes a correctness proof and a temporal complexity bound expressed in terms of link stream parameters. The work aims to support centrality calculations such as betweenness and closeness on link streams.

Core claim

We develop different algorithms to compute distances, latencies and lengths of shortest fastest paths in link streams efficiently. Proofs of correctness for those methods are presented as well as bounds on their temporal complexities as functions of link stream parameters. One purpose of this study is to help develop algorithms to compute centrality functions on link streams such as the betweenness centrality and the closeness centrality.

What carries the argument

Algorithms for efficient computation of distances and latencies, using the link stream definitions of distance, latency, and shortest fastest paths.

If this is right

  • Centrality functions such as betweenness and closeness centrality become computable on link streams.
  • The topological and temporal structure of link streams can be analyzed through these distance and latency values.
  • Runtime for the computations can be predicted from the size and parameters of the link stream.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same algorithmic approach could extend to other path-based metrics on temporal networks beyond the centralities named in the paper.
  • Practical performance could be tested by running the algorithms on real-world temporal datasets with known ground-truth distances.
  • Integration into existing temporal network libraries would allow direct comparison of speed against naive enumeration methods.

Load-bearing premise

The definitions of distance, latency, and shortest fastest paths in the link stream model are the appropriate quantities for downstream tasks such as betweenness and closeness centrality computation.

What would settle it

A small, manually solvable link stream instance on which any of the algorithms returns a distance or latency value that does not match the manually computed correct value.

Figures

Figures reproduced from arXiv: 1907.02146 by Fr\'ed\'eric Simard.

Figure 1
Figure 1. Figure 1: A simple link stream with maximal edge ([1, 2], cb). that u0 = u, vk = v, t0 ≥ α, tk ≤ ω and for all i, ti ≤ ti+1, vi = ui+1 and (ti , uivi) ∈ E. We say that such a path starts at t0, arrives at tk, has length k + 1 and duration tk − t0. We write (α, u) (ω, v) to mean that there exists a path from (α, u) to (ω, v) and say (ω, v) is reachable from (α, u). We also call t0 a starting time and tk an arrival ti… view at source ↗
Figure 2
Figure 2. Figure 2: The shortest path from (1, g) to (9, a) (both encircled ) is drawn in green . The two fastest paths are drawn in red and in blue . The sole shortest fastest path is the red one. Observe that, df ((1, g),(9, a)) = 3 > df ((1, g),(9, f)) + df ((9, f),(9, a)) = 2. well as distances and latencies, in a single pass over a dataset. Separately, Wu et al.’s fastest and shortest paths methods are insufficient to co… view at source ↗
Figure 3
Figure 3. Figure 3: Runtime comparison between Algorithms 1 (SSMD) and 2 (MSMD) [PITH_FULL_IMAGE:figures/full_fig_p014_3.png] view at source ↗
read the original abstract

Link Streams were proposed a few years ago as a model of temporal networks. We seek to understand the topological and temporal nature of those objects through efficiently computing the distances, latencies and lengths of shortest fastest paths. We develop different algorithms to compute those values efficiently. Proofs of correctness for those methods are presented as well as bounds on their temporal complexities as functions of link stream parameters. One purpose of this study is to help develop algorithms to compute centrality functions on link streams such as the betweenness centrality and the closeness centrality.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript develops algorithms to compute distances, latencies, and lengths of shortest-fastest paths in link streams (a model of temporal networks). It supplies proofs of correctness for the methods and derives temporal complexity bounds expressed in terms of link-stream parameters. The stated purpose is to enable subsequent centrality computations such as betweenness and closeness on link streams.

Significance. If the algorithms, proofs, and complexity bounds are correct, the work supplies foundational primitives for temporal-network analysis. Explicit provision of correctness proofs together with parameter-dependent complexity expressions is a clear strength that supports reproducibility and downstream use in centrality algorithms.

minor comments (3)
  1. [Abstract] Abstract: the phrase 'different algorithms' is vague; stating the number of distinct procedures and the key parameters they depend on would improve precision.
  2. The manuscript should include a short table or paragraph that explicitly lists all link-stream parameters (e.g., number of nodes, number of links, time horizon) used in the complexity statements so that the bounds can be compared at a glance.
  3. Notation for temporal distance and latency should be introduced once in a dedicated definitions section and then used consistently; scattered re-definitions risk minor confusion for readers.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive evaluation of the manuscript, the recognition of its foundational role for temporal-network centrality computations, and the recommendation of minor revision. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper presents algorithms for computing distances, latencies and shortest-fastest-path lengths in link streams, together with correctness proofs and complexity bounds expressed directly in terms of link-stream parameters. No equations, definitions or results are shown to reduce by construction to fitted inputs, self-referential definitions or load-bearing self-citations; the claimed contributions are standard algorithmic results whose validity rests on the proofs themselves rather than on any circular reduction to prior outputs of the same work.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review supplies no explicit free parameters, axioms, or invented entities; the ledger is therefore empty.

pith-pipeline@v0.9.0 · 5599 in / 1021 out tokens · 33661 ms · 2026-05-25T09:12:20.276899+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

16 extracted references · 16 canonical work pages

  1. [1]

    www.sociopatterns.org/

    Sociopatterns collaboration. www.sociopatterns.org/. Accessed: April 17, 2019

    work page 2019

  2. [2]

    Casteigts, P

    A. Casteigts, P. Flocchini, B. Mans, and N. Santoro. Shortest, fastest, and foremost broadcast in dynamic networks. International Journal of Foundations of Computer Science, 26(4):499–522, 2015

    work page 2015

  3. [3]

    Time-varying graphs and dynamic networks.International Journal of Parallel, Emergent and Distributed Systems, 27(5):387–408, 2012

    Arnaud Casteigts, Paola Flocchini, Walter Quattrociocchi, and Nicola San- toro. Time-varying graphs and dynamic networks.International Journal of Parallel, Emergent and Distributed Systems, 27(5):387–408, 2012

    work page 2012

  4. [4]

    Dynamics of person- to-person interactions from distributed rfid sensor networks

    Ciro Cattuto, Wouter Van den Broeck, Alain Barrat, Vittoria Colizza, Jean-François Pinton, and Alessandro Vespignani. Dynamics of person- to-person interactions from distributed rfid sensor networks. PloS one, 5(7):1–9, 07 2010

    work page 2010

  5. [5]

    Connectivityandinference problemsfortemporalnetworks

    DavidKempe, JonKleinberg, andAmitKumar. Connectivityandinference problemsfortemporalnetworks. Journal of Computer and System Sciences, 64(4):820–842, 2002

    work page 2002

  6. [6]

    Konect: the koblenz network collection

    Jérôme Kunegis. Konect: the koblenz network collection. InProceedings of the 22nd International Conference on World Wide Web, pages 1343–1350. ACM, 2013

    work page 2013

  7. [7]

    Stream graphs and link streams for the modeling of interactions over time.Social Network Analysis and Mining, 8(1):61, 2018

    Matthieu Latapy, Tiphaine Viard, and Clémence Magnien. Stream graphs and link streams for the modeling of interactions over time.Social Network Analysis and Mining, 8(1):61, 2018

    work page 2018

  8. [8]

    Effect of risk perception on epidemic spreading in temporal networks.Phys

    Antoine Moinet, Romualdo Pastor-Satorras, and Alain Barrat. Effect of risk perception on epidemic spreading in temporal networks.Phys. Rev. E, 97:012313, Jan 2018

    work page 2018

  9. [9]

    R Foundation for Statistical Computing, Vienna, Austria, 2013

    R Core Team.R: A Language and Environment for Statistical Computing. R Foundation for Statistical Computing, Vienna, Austria, 2013. 19

    work page 2013

  10. [10]

    SSMD and MSMD repository

    Frédéric Simard. SSMD and MSMD repository. https://bitbucket. org/simfr404/linkstreams_cpp/src/master/. Accessed: July 5, 2019

    work page 2019

  11. [11]

    On computing distances and latencies in Link Streams

    Frédéric Simard. On computing distances and latencies in Link Streams. In Proceedings of The 2019 IEEE/ACM International Conference on Ad- vances in Social Networks Analysis and Mining, Vancouver, Canada, 2019. ACM

    work page 2019

  12. [12]

    Gender homophily from spatial behavior in a primary school: A sociometric study.Social Networks, 35(4):604 – 613, 2013

    Juliette Stehlé, François Charbonnier, Tristan Picard, Ciro Cattuto, and Alain Barrat. Gender homophily from spatial behavior in a primary school: A sociometric study.Social Networks, 35(4):604 – 613, 2013

    work page 2013

  13. [13]

    Characteris- ing temporal distance and reachability in mobile and online social networks

    John Tang, Mirco Musolesi, Cecilia Mascolo, and Vito Latora. Characteris- ing temporal distance and reachability in mobile and online social networks. ACM SIGCOMM Computer Communication Review, 40(1):118, 2010

    work page 2010

  14. [14]

    Analysing Information Flows and Key Mediators through Tem- poral Centrality Metrics

    John Tang, Mirco Musolesi, Cecilia Mascolo, Vito Latora, and Vincenzo Nicosia. Analysing Information Flows and Key Mediators through Tem- poral Centrality Metrics. In Proceedings of the 3rd Workshop on Social Network Systems (SNS ’10), Paris, France, 2010. ACM

    work page 2010

  15. [15]

    Path Problems in Temporal Graphs

    Huanhuan Wu, James Cheng, Silu Huang, Yiping Ke, Yi Lu, and Yanyan Xu. Path Problems in Temporal Graphs. Proceedings of the VLDB En- dowment, 7(9):721–732, 2014

    work page 2014

  16. [16]

    Computing shortest, fastest, and foremost journeys in dynamic networks.International Journal of Foundations of Computer Science, 14(02):267–285, 2003

    B Bui Xuan, Afonso Ferreira, and Aubin Jarry. Computing shortest, fastest, and foremost journeys in dynamic networks.International Journal of Foundations of Computer Science, 14(02):267–285, 2003. 20

    work page 2003