pith. sign in

arxiv: 2606.09488 · v1 · pith:Y6ZTUOL2new · submitted 2026-06-08 · 🧮 math.PR

The temporal stochastic block model

Sofiya Burova , G\'abor Lugosi , Guillem Perarnau This is my paper

Pith reviewed 2026-06-27 15:21 UTC · model grok-4.3

classification 🧮 math.PR
keywords temporal stochastic block modelincreasing pathsreachable setsweighted random recursive treeinfection spreadingcommunity structureasymptotics of random graphs
0
0 comments X

The pith

In the temporal stochastic block model with log n degrees, reachable sets via increasing paths admit tight first-order size asymptotics and community proportions, and induce a weighted random recursive tree when sublinear.

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

The paper studies spreading processes on a stochastic block model in which each possible edge carries an independent random timestamp. It focuses on the set of vertices reachable from a typical starting vertex by paths whose timestamps are strictly increasing, under the regime where typical degrees are order log n. Tight asymptotic expressions are derived for both the overall size of this reachable set and the fraction of vertices reached inside each community. When the reachable set remains sublinear in n, the induced subgraph on that set contains an almost-spanning tree whose law is exactly that of a weighted random recursive tree, a well-studied object whose height, profile and degree sequence are known explicitly.

Core claim

In the temporal stochastic block model, where edge timestamps are i.i.d. continuous random variables, the reachable set S from a typical vertex via increasing paths has first-order asymptotic size and community proportions that can be determined explicitly from the model parameters; moreover, when |S| is sublinear, the subgraph induced by S contains an almost-spanning tree distributed as a weighted random recursive tree, and when |S| is much smaller than sqrt(n) the entire induced subgraph coincides with this tree.

What carries the argument

The almost-spanning tree inside the reachable set S that is distributed as a weighted random recursive tree, which encodes the height, profile and degree sequence of the induced subgraph on S.

If this is right

  • The proportions of reached vertices inside each community converge to explicit constants determined by the block probabilities and timestamp distributions.
  • The typical lengths of the shortest and longest increasing paths with one or two fixed endpoints admit explicit asymptotic descriptions.
  • When |S| << sqrt(n), every property of the induced subgraph on S (height, profile, degree sequence) is given by the corresponding property of the weighted random recursive tree.
  • The identification supplies exact limiting distributions for local statistics of the reachable component without further computation.

Where Pith is reading between the lines

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

  • The tree-like structure of reachable sets may extend to other temporal random-graph models with community structure, yielding similar explicit descriptions.
  • Empirical contact networks with timestamp data could be compared directly to the predicted reachable-set sizes to assess model fit.
  • The results suggest that imposing a temporal order on edges can reduce the geometry of dense random graphs to that of a recursive tree even in the presence of communities.
  • Relaxing the log n degree assumption to other regimes may produce different limiting objects whose identification would require new arguments.

Load-bearing premise

Edge timestamps must be i.i.d. continuous random variables and degrees must be exactly order log n; relaxing either condition can invalidate the claimed asymptotics and the identification with the weighted random recursive tree.

What would settle it

Run Monte Carlo simulations of the temporal SBM for a sequence of growing n, compute the normalized reachable-set size for a typical vertex, and test whether it converges to the paper's explicit first-order expression while the empirical degree sequence of the induced subgraph on S matches the known law of the weighted random recursive tree.

read the original abstract

Motivated by the need to understand infection spreading in inhomogeneous populations, we consider a \emph{temporal} version of the stochastic block model, where each edge is equipped with a random label, interpreted as a timestamp. We study the size and structure of reachable sets via increasing paths (that is, paths whose edge timestamps are strictly increasing) where the connections per node are of the order of $\log n$. We prove tight results for the first order asymptotics of the size of the reachable set from a typical vertex, and the proportions of reached vertices in each community. We also determine the typical length of the shortest and longest increasing paths with one or two fixed endpoints. In the regime where the reachable set $S$ of a typical vertex is of sublinear size, we describe the structure of the subgraph induced by $S$ by identifying an almost spanning tree (i.e., spanning all but $o(|S|)$ vertices), that is distributed as a weighted random recursive tree, whose height, profile and degree sequence are known. In particular, when $|S|\ll \sqrt{n}$, the subgraph induced by $S$ is itself distributed as this well-understood weighted random recursive tree.

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 paper introduces a temporal stochastic block model in which edges carry i.i.d. continuous timestamps and studies the reachable sets reachable by strictly increasing paths when the typical degree is Θ(log n). It derives first-order asymptotics for the size of the reachable set from a typical vertex and the community proportions within it, determines the typical lengths of shortest and longest increasing paths between one or two fixed endpoints, and, in the sublinear-size regime, shows that the induced subgraph on the reachable set is distributed as a weighted random recursive tree (apart from o(|S|) vertices) whose height, profile and degree sequence are known.

Significance. If the derivations hold, the work supplies a rigorous branching-process and recursive-tree analysis of spreading on temporal block-structured graphs in the logarithmic-degree regime. The explicit identification of the induced subgraph with a weighted random recursive tree is a clear strength, because it immediately transfers known results on height, profile and degree sequence to the temporal SBM setting. The results are parameter-free once the model parameters are fixed and rest on standard probabilistic tools rather than fitted quantities.

minor comments (3)
  1. [§1] §1, paragraph following Definition 1.1: the phrase 'connections per node are of the order of log n' should be replaced by the precise statement of the degree regime (e.g., p_{ij} = (a_{ij} log n)/n) to avoid ambiguity when the reader reaches the sublinear-size threshold.
  2. [§4.2] §4.2, statement of Theorem 4.3: the error term o(|S|) in the 'almost spanning tree' claim is not quantified; an explicit rate (e.g., |S|^{-c} or exp(-c log |S|)) would make the approximation statement fully precise.
  3. The paper cites the weighted random recursive tree literature but does not restate the exact weight distribution used in the coupling; a one-sentence reminder of the weight law would improve readability for readers outside the recursive-tree community.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript, including the recognition of the branching-process analysis and the explicit identification of the induced subgraph with a weighted random recursive tree. The recommendation for minor revision is noted. No major comments were provided in the report.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper derives first-order asymptotics for reachable sets in the temporal SBM via branching-process approximations and identification with weighted random recursive trees, using only the model definition (i.i.d. continuous timestamps, log n degrees) and standard probabilistic tools. No fitted parameters are renamed as predictions, no equations reduce to self-definitions, and no load-bearing self-citations appear. The sublinear regime and tree identification are explicitly conditioned on the model assumptions, making the chain independent of its own outputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on the definition of the temporal SBM and on standard independence and continuity assumptions for edges and timestamps; no free parameters are fitted to data and no new entities are postulated beyond the model itself.

axioms (2)
  • domain assumption Edges are independent Bernoulli random variables whose success probability depends only on the community labels of the endpoints.
    Standard SBM assumption invoked to define the underlying static graph.
  • domain assumption Edge timestamps are i.i.d. continuous random variables independent of the edge indicators.
    Ensures that almost every path has strictly increasing timestamps; stated in the model definition.

pith-pipeline@v0.9.1-grok · 5739 in / 1430 out tokens · 26268 ms · 2026-06-27T15:21:01.145389+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

32 extracted references · 12 canonical work pages · 1 internal anchor

  1. [1]

    A. Kumar D. Kempe, J. Kleinberg. Connectivity and inference problems for temporal networks.Journal of Computer and System Sciences, 64(4):820–842, 2002

    2002

  2. [2]

    Angel, A

    O. Angel, A. Ferber, B. Sudakov, and V. Tassion. Long monotone trails in ran- dom edge-labellings of random graphs.Combinatorics, Probability and Computing, 29(1):22–30, 2020.doi:10.1017/S096354831900018X

    work page doi:10.1017/s096354831900018x 2020

  3. [3]

    Becker, A

    R. Becker, A. Casteigts, P. Crescenzi, B. Kodric, M. Renken, M. Raskin, and V. Zamaraev. Giant components in random temporal graphs, 2023. URL:https: //arxiv.org/abs/2205.14888,arXiv:2205.14888. 29

    work page arXiv 2023

  4. [4]

    Casteigts, M

    A. Casteigts, M. Raskin, M. Renken, and V. Zamaraev. Sharp thresholds in random simple temporal graphs.SIAM Journal on Computing, 53(2):346–388, 2024.doi: 10.1137/22M1511916

    work page doi:10.1137/22m1511916 2024

  5. [5]

    Broutin, N

    N. Broutin, N. Kamčev, and G. Lugosi. Increasing paths in random temporal graphs.The Annals of Applied Probability, 34(6):5498 – 5521, 2024.doi:10.1214/ 24-AAP2097

    2024

  6. [6]

    Atamanchuk, L

    C. Atamanchuk, L. Devroye, and G. Lugosi. On the size of temporal cliques in subcrit- ical random temporal graphs.Combinatorics, Probability and Computing, 34(5):671– 679, 2025

    2025

  7. [7]

    Atamanchuk, L

    C. Atamanchuk, L. Devroye, and G. Lugosi. Uniform temporal trees.Random Struc- tures & Algorithms, 67(4):e70040, 2025

    2025

  8. [8]

    B. G. Pittel. Note on the heights of random recursive trees and random m-ary search trees.Random Struct. Algorithms, 5:337–348, 1994. URL:https://api. semanticscholar.org/CorpusID:7638686

    1994

  9. [9]

    S. Janson. Asymptotic degree distribution in random recursive trees.Random Struc- tures & Algorithms, 26(1-2):69–83, 2005.doi:10.1002/rsa.20046

    work page doi:10.1002/rsa.20046 2005

  10. [10]

    Devroye and J

    L. Devroye and J. Lu. The strong convergence of maximal degrees in uniform random recursive trees and dags.Random Structures & Algorithms, 7(1):1–14, 1995.doi: 10.1002/rsa.3240070102

    work page doi:10.1002/rsa.3240070102 1995

  11. [11]

    Addario-Berry and L

    L. Addario-Berry and L. Eslava. High degrees in random recursive trees.Random Structures & Algorithms, 52(4):560–575, 2018.doi:10.1002/rsa.20753

    work page doi:10.1002/rsa.20753 2018

  12. [12]

    L. Devroye. Branching processes in the analysis of the heights of trees.Acta In- formatica, 24:277–298, 1987. URL:https://api.semanticscholar.org/CorpusID: 11540185

    1987

  13. [13]

    E. Abbe. Community detection and stochastic block models: Recent developments. Journal of Machine Learning Research, 18(177):1–86, 2018. URL:http://jmlr.org/ papers/v18/16-480.html

    2018

  14. [14]

    C. D. Meyer.Matrix Analysis and Applied Linear Algebra, Second Edition. Society for Industrial and Applied Mathematics, 2023. URL:https://epubs.siam.org/doi/ abs/10.1137/1.9781611977448.ch8,doi:10.1137/1.9781611977448.ch8

    work page doi:10.1137/1.9781611977448.ch8 2023

  15. [15]

    K. A. Borovkov and V. A. Vatutin. On the asymptotic behaviour of random recursive treesinrandomenvironments.Advances in Applied Probability, 38(4):1047–1070, 2006

    2006

  16. [16]

    Asymptotic results on Hoppe trees and its variations

    E. Hiesmayr and Ü. Işlak. Asymptotic results on Hoppe trees and its variations, 2017. arXiv:1712.03572. 30

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  17. [17]

    Mailler and G

    C. Mailler and G. Uribe Bravo. Random walks with preferential relocations and fading memory: a study through random recursive trees, 2018.arXiv:1810.02735

    work page arXiv 2018

  18. [18]

    Sénizergues

    D. Sénizergues. Geometry of weighted recursive and affine preferential attachment trees.Electronic Journal of Probability, 23:1–28, 2018

    2018

  19. [19]

    Eslava, B

    L. Eslava, B. Lodewijks, and M. Ortgiese. Fine asymptotics for the maximum degree in weighted recursive trees with bounded random weights.Stochastic Processes and their Applications, 158:505–569, 2023.doi:10.1016/j.spa.2023.01.012

    work page doi:10.1016/j.spa.2023.01.012 2023

  20. [20]

    R. A. Horn and C. R. Johnson.Matrix Analysis. Cambridge University Press, 1985

    1985

  21. [21]

    S. Janson. Functional limit theorems for multitype branching processes and generalized pólya urns.Stochastic Processes and their Applications, 110(2):177– 245, 2004. URL:https://www.sciencedirect.com/science/article/pii/ S0304414903001790,doi:10.1016/j.spa.2003.12.002

    work page doi:10.1016/j.spa.2003.12.002 2004

  22. [22]

    S. Janson. Tail bounds for sums of geometric and exponential variables.Statis- tics and Probability Letters, 135:1–6, 2018. URL:https://www.sciencedirect.com/ science/article/pii/S0167715217303711,doi:10.1016/j.spl.2017.11.017

    work page doi:10.1016/j.spl.2017.11.017 2018

  23. [23]

    D. W. Boyd and J. M. Steele. Random exchanges of information.Journal of Applied Probability, 16(3):657–661, 1979

    1979

  24. [24]

    Randomexchangesofinformation.Journal of Applied Probability, 18(3):743– 746, 1981

    J.Haigh. Randomexchangesofinformation.Journal of Applied Probability, 18(3):743– 746, 1981

    1981

  25. [25]

    Randomexchangesofinformation.Nieuw Archief voor Wiskunde, 20:246– 249, 1972

    J.W.Moon. Randomexchangesofinformation.Nieuw Archief voor Wiskunde, 20:246– 249, 1972

    1972

  26. [26]

    Mocquard, B

    Y. Mocquard, B. Sericola, and E. Anceaume. Probabilistic analysis of rumor-spreading time.INFORMS Journal on Computing, 32(1):172–181, 2020

    2020

  27. [27]

    Mocquard, B

    Y. Mocquard, B. Sericola, S. Robert, and E. Anceaume. Analysis of the propagation time of a rumour in large-scale distributed systems. In2016 IEEE 15th International Symposium on Network Computing and Applications (NCA), pages 264–271. IEEE, 2016

    2016

  28. [28]

    van Ditmarsch, I

    H. van Ditmarsch, I. Kokkinis, and A. Stockmarr. Reachability and expectation in gossiping. InPRIMA 2017: Principles and Practice of Multi-Agent Systems, pages 93–109. Springer, 2017

    2017

  29. [29]

    Y. J. Wang and G. Y. Wong. Stochastic blockmodels for directed graphs.Journal of the American Statistical Association, 82(397):8–19, 1987. 31

    1987

  30. [30]

    L. J. S. Allen.An Introduction to Stochastic Processes with Applications to Biology. CRC Press, 2 edition, 2015

    2015

  31. [31]

    Andersson and T

    H. Andersson and T. Britton.Stochastic Epidemic Models and Their Statistical Anal- ysis. Springer, 2000

    2000

  32. [32]

    Lindvall

    T. Lindvall. Lectures on the coupling method. 1992. URL:https://api. semanticscholar.org/CorpusID:261559571. 32 A Proof of Claim 3.6 Observe thatYis distributed as the minimum ofai.i.d. uniform random variables of distribution Unif([z,1/p]). Hence,Yhas density fY (x) =∂x(1−P[Y≥x]) =∂x ( − (1/p−x 1/p−z )a) = ap(1−px)a−1 (1−pz)a , for allx∈[z,1/p]. Meanwhil...

    1992