pith. sign in

arxiv: 2605.21459 · v1 · pith:35MMFZ3Snew · submitted 2026-05-20 · 🧮 math.PR

Network evolution with self-reinforcement

Shankar Bhamidi , Remco van der Hofstad , Frank den Hollander , Rounak Ray This is my paper

Pith reviewed 2026-05-21 02:46 UTC · model grok-4.3

classification 🧮 math.PR
keywords preferential attachmentself-reinforcementpower-law degreeslocal convergencesin-treecontinuous-time branching processnetwork growthlong memory
0
0 comments X

The pith

Self-reinforcing attachment in growing networks produces power-law degrees with explicit exponent φ depending on reinforcement strength δ.

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

This paper studies preferential attachment where each vertex weight is the cumulative sum of an affine function of its past degrees, building long memory into the growth rule and removing the Markov property of classical models. The authors still obtain an explicit exponent φ=φ(δ) that governs both global and local behavior: typical degrees at step n scale as n to the power 1 over φ, and the fraction of vertices with degree k or larger converges to a power law with tail index φ plus one. They further establish that the network viewed from a random vertex converges locally to an infinite random tree constructed from a continuous-time branching process; this limiting object is a sin-tree and differs from the Pólya-urn trees that appear without reinforcement.

Core claim

In the self-reinforcing model, an explicit exponent φ=φ(δ) controls both local and global growth: typical degrees at time n scale as n^{1/φ}, the empirical degree distribution converges to a power-law with tail exponent φ+1, and the network converges in the Benjamini-Schramm sense to a sin-tree characterized by an embedded continuous-time branching process, distinct from the Pólya-type limiting tree of the non-reinforced case.

What carries the argument

The integrated weight, defined as the cumulative sum over past times of an affine function of a vertex's degree, which destroys the Markov property yet still permits derivation of the growth exponent φ(δ) and the embedding of the local limit into a continuous-time branching process.

If this is right

  • Typical degrees grow proportionally to n raised to the power 1/φ.
  • The proportion of vertices with degree at least k behaves asymptotically like k to the power minus (φ+1).
  • The rooted neighborhood of a uniformly chosen vertex converges in distribution to an infinite random tree generated by a continuous-time branching process.
  • This limiting tree is a sin-tree and therefore structurally different from the Pólya-urn trees obtained in the absence of reinforcement.

Where Pith is reading between the lines

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

  • The same long-memory construction may yield tractable limits in other self-interacting processes such as reinforced random walks.
  • The continuous-time branching process representation opens the possibility of computing global statistics such as typical distances directly from the limit object.
  • Variations in the affine reinforcement function could produce families of models whose exponents are still explicitly computable.

Load-bearing premise

The attachment weights are formed by cumulative sums of an affine function of degree in a manner that permits explicit calculation of the scaling exponent despite eliminating the Markov property.

What would settle it

Numerical simulation of the process up to large n, followed by measurement of the empirical degree tail and local neighborhood statistics, to test whether the observed power-law exponent equals the predicted φ(δ)+1 and whether the local structure matches the sin-tree limit.

Figures

Figures reproduced from arXiv: 2605.21459 by Frank den Hollander, Remco van der Hofstad, Rounak Ray, Shankar Bhamidi.

Figure 1
Figure 1. Figure 1: Empirical degree distribution and limit probability mass function for δ = 1 and δ = 2. The above result immediately implies the following. Let An denote the adjacency matrix of Tn. Let (λ (n) i )1⩽i⩽n denote the set of eigenvalues of An, and ˆµn = n −1 Pn i=1 δ λ (n) i the empirical spectral distribution of An (where δ(·) denotes the Dirac delta-function). Corollary 2.3 (Limiting empirical spectral distrib… view at source ↗
Figure 2
Figure 2. Figure 2: Two realizations of preferential attachment trees with self-reinforcement grown to the same size (n = 40, 000), illustrating the effect of the parameter δ on network geometry. The left panel corresponds to δ = 0 and exhibits a markedly more hub-dominated structure, with attachment concentrating more strongly around a few high-degree vertices. The right panel corresponds to δ = 10, where attachment is more … view at source ↗
Figure 3
Figure 3. Figure 3: The blue drawn curve is a plot of the function δ 7→ ϕ(δ). The red dotted curve is its counterpart δ 7→ 2 + δ for standard affine preferential attachment (in the absence of self-reinforcement). Note that the asymptotic slopes of the two curves are different, and that the lower curve is close to linear but is in fact strictly concave. In particular, ϕ(δ) = 1 2 [δ + 4 + O(1/δ)] as δ → ∞. 3. Local convergence … view at source ↗
Figure 4
Figure 4. Figure 4: Fringe decomposition around vertex v of a finite tree rooted at ρ. The blue colored vertices represent the roots of the respective trees. Call the map (v, t) ❀ T∞ (i.e., infinite sequences of finite trees) with v ∈ t, defined by F(v, t) = (f0(v, t), f1(v, t), . . . , fh(v, t), ∅, ∅, . . .), the fringe decomposition of t about the vertex v. Call f0(v, t) the fringe of the tree t at v. For k ⩾ 0, call Fk(v, … view at source ↗
Figure 5
Figure 5. Figure 5: A sin-tree T∞, namely, a tree rooted at 0 with a single infinite path to infinity, and the corresponding extended fringe F3(0, T∞) up to level 3 about 0. Call this the extended fringe of the tree ω at vertex 0, until distance k, on the infinite path from 0. Call t0 = F0(0, ω) the fringe of the sin-tree ω. Suppose P is a probability measure on T∞ such that, for T∞ = (t0(T∞), t1(T∞), . . .) ∼ P, |ti(T∞)| ⩾ 1… view at source ↗
Figure 6
Figure 6. Figure 6: Left: B1(u) in the Ulam-Harris notation, with offspring u1, u2, . . . , ud(u, t) and d = d(u, t). Right: A visual representation of the vertices T r on in [n] corresponding to the vertices in B1(u), with the convention τu0 = τu and τu(d(u,t)+1) = n. Using that Wτu (τuk − 1) = Pk m=1(τum − τu(m−1)) (m + δ), we see that the last product in (5.5) can be written out as Y u∈Br−1(∅) I(u), (5.6) where I(u) = (1 +… view at source ↗
Figure 7
Figure 7. Figure 7: Times of growth of degree of vertex v1. Note that the weight used for the probability of connection when the network transitions from n ❀ n + 1 can be rewritten as θ(v1, n) (1 + 1 2 δ)n(n + 1) = (n − v + 1)n − Pn i=1 Pn j=v 1{s<ti} (1 + 1 2 δ)n(n + 1) = n(m + δ) − (t1 + t2 + · · · + tm) (1 + 1 2 δ)n(n + 1) . (5.19) Hence, for keeping track of the evolution of this vertex, it is easier to move to continuous… view at source ↗
read the original abstract

We study a new class of preferential attachment trees with \emph{self-reinforcement}. At each time, each vertex is assigned a weight equal to the cumulative sum over past times of an affine function of its degree. A new vertex attaches itself via a single edge to an already present vertex with a probability proportional to the current weight of that vertex. This ``integrated popularity'' rule builds long memory directly into the attachment mechanism, thereby destroying the Markov and partial-exchangeability features that underlie the classical analysis of affine preferential attachment models. More broadly, the model connects to applied-probability work on long-memory self-interacting processes (such as the elephant random walk), emphasizing how non-Markovian reinforcement reshapes asymptotic behaviour. Despite this loss of structure, we identify an explicit exponent $\phi=\phi(\delta)$ governing both local and global growth: typical degrees at time $n$ scale as $n^{1/\phi}$, and the empirical degree distribution converges to a power-law with a tail exponent $\phi+1$. We further prove Benjamini--Schramm local convergence to an infinite random rooted tree characterized via an embedded continuous-time branching process. The limiting tree is a \texttt{sin}-tree, and is \emph{not} the P\'olya-type limiting tree arising in the non-reinforced setting. Our results provide a tractable probabilistic description of a natural ``memoryful'' network-growth mechanism, and quantify precisely how reinforcement renormalizes the classical preferential-attachment exponents.

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

2 major / 2 minor

Summary. The manuscript introduces a preferential attachment model on trees with self-reinforcement: each vertex weight at time t is the cumulative sum over past times of an affine function of its current degree. New vertices attach proportionally to these weights, yielding a non-Markovian process. The authors derive an explicit exponent φ=φ(δ) such that typical degrees at time n scale as n^{1/φ} and the empirical degree distribution converges to a power law with tail exponent φ+1. They further establish Benjamini–Schramm local convergence to an infinite sin-tree obtained from an embedded continuous-time branching process, distinct from the Pólya urn limit of the non-reinforced case.

Significance. If the central claims hold, the work supplies the first explicit scaling and local-limit results for a natural long-memory variant of preferential attachment. The continuous-time branching-process embedding that directly encodes the integrated weight process is a technically useful device for handling reinforcement without the Markov property, and the identification of the sin-tree limit quantifies how memory renormalizes classical exponents. These results connect network growth to the broader literature on self-interacting processes and furnish falsifiable predictions for degree tails and local structure.

major comments (2)
  1. [§3] §3 (derivation of φ(δ)): the explicit exponent is obtained by solving a fixed-point equation for the mean intensity of the embedded CTBP; the manuscript should verify that the long-memory dependence does not alter the first-moment calculation or introduce an extra bias term when passing from the discrete integrated weight to the continuous intensity.
  2. [Theorem on Benjamini–Schramm convergence] Theorem on Benjamini–Schramm convergence (presumably §5): the argument shows that local neighborhoods satisfy the same branching dynamics in the limit, but it is not immediate that the cumulative-sum reinforcement preserves the required independence of offspring across generations; a short additional paragraph confirming that the embedded point processes remain Poisson with the correct intensity after conditioning on the past would remove any residual doubt.
minor comments (2)
  1. [Abstract] Abstract: the term 'sin-tree' appears without definition or reference; a parenthetical gloss or citation on first use would aid readers unfamiliar with the terminology.
  2. [Introduction] Introduction: the connection to the elephant random walk is mentioned but not referenced; adding one or two canonical citations would strengthen the contextual framing.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive evaluation and the constructive suggestions for additional clarification. We address each major comment below and have incorporated minor revisions to strengthen the exposition.

read point-by-point responses

  1. Referee: [§3] §3 (derivation of φ(δ)): the explicit exponent is obtained by solving a fixed-point equation for the mean intensity of the embedded CTBP; the manuscript should verify that the long-memory dependence does not alter the first-moment calculation or introduce an extra bias term when passing from the discrete integrated weight to the continuous intensity.

    Authors: We agree that an explicit verification is helpful. In §3 the mean intensity of the embedded CTBP is obtained by taking expectations in the integral equation that relates the continuous-time intensity to the cumulative (integrated) weight process. Because the weight at each vertex is defined as the integral of an affine function of its degree and the attachment probabilities are linear in the weights, linearity of expectation applies directly to the intensity measure. Consequently, the long-memory dependence, while affecting pathwise realizations, does not introduce an extra bias term in the first-moment calculation; the fixed-point equation for the mean intensity remains unchanged from the discrete to the continuous embedding. We have added a short clarifying paragraph at the end of §3 that records this linearity argument explicitly. revision: yes

  2. Referee: [Theorem on Benjamini–Schramm convergence] Theorem on Benjamini–Schramm convergence (presumably §5): the argument shows that local neighborhoods satisfy the same branching dynamics in the limit, but it is not immediate that the cumulative-sum reinforcement preserves the required independence of offspring across generations; a short additional paragraph confirming that the embedded point processes remain Poisson with the correct intensity after conditioning on the past would remove any residual doubt.

    Authors: We thank the referee for this observation. The construction in §5 proceeds by embedding the discrete attachment process into a continuous-time branching process whose intensity at each vertex is the integrated weight process. Conditional on the sigma-field generated by the history up to any finite generation, the future attachment events are independent Poisson point processes with intensity given by the current weight trajectory. The cumulative-sum reinforcement modifies the intensity path but does not destroy the conditional Poisson property, because the underlying attachment decisions remain independent given the realized weights. We have inserted a brief additional paragraph in §5 that states this conditional independence and Poisson character explicitly, thereby confirming that the branching dynamics are preserved in the local limit. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained

full rationale

The paper defines a non-Markovian attachment rule via integrated weights and embeds the process into a continuous-time branching process whose intensity functions directly encode the cumulative reinforcement. The exponent φ(δ) and the sin-tree limit are obtained by solving the resulting branching dynamics and verifying local convergence, without reducing any claimed prediction to a fitted parameter or to a self-citation that itself assumes the target result. The argument relies on the model definition and standard branching-process techniques rather than on any load-bearing self-referential step.

Axiom & Free-Parameter Ledger

1 free parameters · 1 axioms · 0 invented entities

The model relies on standard probabilistic constructions for random trees and branching processes; the reinforcement parameter δ appears as a model input rather than a fitted quantity.

free parameters (1)
  • δ
    Parameter controlling the affine function in the weight definition; enters the exponent φ(δ).
axioms (1)
  • standard math Standard results from probability theory on branching processes and local convergence of random graphs
    Invoked to establish the Benjamini-Schramm limit and scaling laws.

pith-pipeline@v0.9.0 · 5803 in / 1138 out tokens · 38361 ms · 2026-05-21T02:46:55.220617+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

33 extracted references · 33 canonical work pages

  1. [1]

    Albert and A.-L

    R. Albert and A.-L. Barab´ asi,Statistical mechanics of complex networks, Rev. Modern Phys.74(2002), no. 1, 47–97. MR1895096

    work page 2002

  2. [2]

    Aldous,Asymptotic fringe distributions for general families of random trees, Ann

    D. Aldous,Asymptotic fringe distributions for general families of random trees, Ann. Appl. Probab.1(1991), no. 2, 228–266. MR1102319

    work page 1991

  3. [3]

    Aldous and J

    D. Aldous and J. M. Steele,The objective method: probabilistic combinatorial optimization and local weak con- vergence, Probability on discrete structures, 2004, pp. 1–72. MR2023650

    work page 2004

  4. [4]

    Antunes, S

    N. Antunes, S. Banerjee, S. Bhamidi, and V. Pipiras,Attribute network models, stochastic approximation and network sampling, Ann. Appl. Probab.36(2026), no. 1, 652–702. MR5033584

    work page 2026

  5. [5]

    Banerjee, S

    S. Banerjee, S. Bhamidi, P. Dey, and A. Sakanaveeti,Network evolution with macroscopic delays: local weak convergence and condensation, ArXiv:2409.06048 (2024)

    work page arXiv 2024

  6. [6]

    Banerjee, S

    S. Banerjee, S. Bhamidi, P. S Dey, and A. Sakanaveeti,Network evolution with mesoscopic delays, Random Structures Algorithms67(2025), no. 2, Paper No. e70029, 28. MR4953723

    work page 2025

  7. [7]

    Barab´ asi and R

    A.-L. Barab´ asi and R. Albert,Emergence of scaling in random networks, Science286(1999), no. 5439, 509–512. MR2091634

    work page 1999

  8. [8]

    Baur and J

    E. Baur and J. Bertoin,Elephant random walks and their connection to p´ olya-type urns, Physical review E94 (2016), no. 5, 052134

    work page 2016

  9. [9]

    Benjamini and O

    I. Benjamini and O. Schramm,Recurrence of distributional limits of finite planar graphs, Electron. J. Probab.6 (2001), no. 23, 13. MR1873300

    work page 2001

  10. [10]

    Bercu,A martingale approach for the elephant random walk, J

    B. Bercu,A martingale approach for the elephant random walk, J. Phys. A51(2018), no. 1, 015201, 16. MR3741953

    work page 2018

  11. [11]

    Berger, C

    N. Berger, C. Borgs, J. T. Chayes, and A. Saberi,On the spread of viruses on the internet, Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005, pp. 301–310. MR2298278

    work page 2005

  12. [12]

    Berger, C

    N. Berger, C. Borgs, J. T. Chayes, and A. Saberi,Asymptotic behavior and distributional limits of preferential attachment graphs, Ann. Probab.42(2014), no. 1, 1–40. MR3161480

    work page 2014

  13. [13]

    Bertenghi,From the elephant random walk to step-reinforced random walks, Ph.D

    M. Bertenghi,From the elephant random walk to step-reinforced random walks, Ph.D. thesis, 2024

    work page 2024

  14. [14]

    Bhamidi, S

    S. Bhamidi, S. N. Evans, and A. Sen,Spectra of large random trees, J. Theoret. Probab.25(2012), no. 3, 613–

    work page 2012

  15. [15]

    Billingsley,Convergence of probability measures, Second, Wiley Series in Probability and Statistics: Probability and Statistics, John Wiley & Sons, Inc., New York, 1999

    P. Billingsley,Convergence of probability measures, Second, Wiley Series in Probability and Statistics: Probability and Statistics, John Wiley & Sons, Inc., New York, 1999. A Wiley-Interscience Publication. MR1700749

    work page 1999

  16. [16]

    Bollob´ as,Random graphs, Second, Cambridge Studies in Advanced Mathematics, vol

    B. Bollob´ as,Random graphs, Second, Cambridge Studies in Advanced Mathematics, vol. 73, Cambridge Univer- sity Press, Cambridge, 2001. MR1864966

    work page 2001

  17. [17]

    Bollob´ as, O

    B. Bollob´ as, O. Riordan, J. Spencer, and G. Tusn´ ady,The degree sequence of a scale-free random graph process, Random Structures Algorithms18(2001), no. 3, 279–290. MR1824277

    work page 2001

  18. [18]

    M. A. A. da Silva, J. C. Cressoni, G. M. Sch¨ utz, G. M. Viswanathan, and S. Trimper,Non-gaussian propagator for elephant random walks, Phys. Rev. E88(2013Aug), 022115

    work page

  19. [19]

    Dahiya and F

    Y. Dahiya and F. den Hollander,Self-reinforced preferential attachment, Electron. Commun. Probab.31(2026), Paper No. 8, 14. MR5022990

    work page 2026

  20. [20]

    Durrett,Random graph dynamics, Cambridge Series in Statistical and Probabilistic Mathematics, Cambridge University Press, Cambridge, 2007

    R. Durrett,Random graph dynamics, Cambridge Series in Statistical and Probabilistic Mathematics, Cambridge University Press, Cambridge, 2007. MR2271734 (2008c:05167)

    work page 2007

  21. [21]

    van der Hofstad,Random graphs and complex networks

    R. van der Hofstad,Random graphs and complex networks. Vol. 1, Cambridge Series in Statistical and Proba- bilistic Mathematics, Cambridge University Press, Cambridge, 2017. MR3617364

    work page 2017

  22. [22]

    van der Hofstad,Random graphs and complex networks

    R. van der Hofstad,Random graphs and complex networks. Vol. 2, Cambridge Series in Statistical and Proba- bilistic Mathematics, Cambridge University Press, Cambridge, 2024

    work page 2024

  23. [23]

    Holme and J

    P. Holme and J. Saram¨ aki,Temporal networks, Physics Reports519(2012), no. 3, 97–125. 28 BHAMIDI, VAN DER HOFSTAD, DEN HOLLANDER, AND RAY

    work page 2012

  24. [24]

    P. Jagers,Branching processes with biological applications, Wiley Series in Probability and Mathematical Statistics—Applied Probability and Statistics, Wiley-Interscience [John Wiley & Sons], London-New York- Sydney, 1975. MR488341

    work page 1975

  25. [25]

    Jagers and O

    P. Jagers and O. Nerman,The growth and composition of branching populations, Adv. in Appl. Probab.16 (1984), no. 2, 221–259. MR742953

    work page 1984

  26. [26]

    Jagers and O

    P. Jagers and O. Nerman,Limit theorems for sums determined by branching and other exponentially growing processes, Stochastic Process. Appl.17(1984), no. 1, 47–71. MR738768

    work page 1984

  27. [27]

    Laulin,About the elephant random walk, Theses, 2022

    L. Laulin,About the elephant random walk, Theses, 2022

    work page 2022

  28. [28]

    Masuda and R

    N. Masuda and R. Lambiotte,A guide to temporal networks, 2nd ed., WORLD SCIENTIFIC (EUROPE), 2020

    work page 2020

  29. [29]

    T. F. M´ ori and S. Rokob,Moments of general time dependent branching processes with applications, Acta Math. Hungar.159(2019), no. 1, 131–149. MR4003699

    work page 2019

  30. [30]

    M. E. J. Newman,The structure and function of complex networks, SIAM Rev.45(2003), no. 2, 167–256. MR2010377

    work page 2003

  31. [31]

    M. E. J. Newman,Networks, Oxford University Press, Oxford, 2010. An introduction. MR2676073

    work page 2010

  32. [32]

    Pemantle,A survey of random processes with reinforcement, Probab

    R. Pemantle,A survey of random processes with reinforcement, Probab. Surv.4(2007), 1–79. MR2282181

    work page 2007

  33. [33]

    G. M. Sch¨ utz and S. Trimper,Elephants can always remember: Exact long-range memory effects in a non- markovian random walk, Phys. Rev. E70(2004Oct), 045101(R)

    work page