Local network evolution rules drive shortest path multiplicity

Alexei Vazquez

arxiv: 2605.25237 · v3 · pith:QPLQGYEGnew · submitted 2026-05-24 · ⚛️ physics.soc-ph · cond-mat.dis-nn· cs.SI· math.CO

Local network evolution rules drive shortest path multiplicity

Alexei Vazquez This is my paper

Pith reviewed 2026-07-02 23:14 UTC · model grok-4.3

classification ⚛️ physics.soc-ph cond-mat.dis-nncs.SImath.CO

keywords shortest path multiplicitylocal network evolutioncomplex networkscommunity structurerandom graphsscale-free networksnetwork size

0 comments

The pith

Local network evolution rules cause shortest path multiplicity to increase faster with network size than random rewiring predicts.

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

The paper shows through simulations that networks grown by local rules exhibit an average shortest path multiplicity that rises with overall network size. This rise occurs more rapidly than in randomized networks that keep the same degree distribution but remove local structure. The multiplicity also increases together with the number of communities detected in the network. For purely random graphs with arbitrary degree distribution p_k the average multiplicity equals roughly the ratio of the second to first degree moments divided by e and grows with size only when the distribution follows a power law with exponent at most three.

Core claim

For networks generated by local rules, ⟨μ⟩ increases with the network size and it does so faster than what is observed in their randomized versions. Furthermore, the number of communities increases with the network size and the correlation with ⟨μ⟩ follows. For random graphs with arbitrary degree distributions p_k, ⟨μ⟩∼⟨k(k−1)⟩/(⟨k⟩e), growing with the network size when p_k∼k^{−γ} and γ≤3.

What carries the argument

Shortest path multiplicity μ (the average number of shortest paths between node pairs), generated by local evolution rules that also produce communities.

If this is right

⟨μ⟩ increases with network size under local evolution rules.
The increase in ⟨μ⟩ is faster than the increase seen after degree-preserving randomization.
The number of communities grows with network size.
⟨μ⟩ correlates positively with the number of communities.
For random graphs with power-law exponent γ≤3, ⟨μ⟩ itself grows with network size.

Where Pith is reading between the lines

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

If local attachment dominates real network formation then larger networks should reliably display higher multiplicity.
Interventions that break local attachment could reduce both multiplicity and community count in growing networks.
Multiplicity could function as a simple scalar indicator of emerging community structure without needing explicit community detection.
The result supplies a baseline expectation for multiplicity in any network whose growth is dominated by local rules rather than global optimization.

Load-bearing premise

The particular local evolution rules used in the simulations represent the mechanisms that operate in real complex networks, and randomizing edges while preserving the degree distribution removes exactly the effects of those local rules.

What would settle it

A real network in which average shortest path multiplicity does not increase with size or does not exceed the value found after degree-preserving randomization would falsify the claim.

Figures

Figures reproduced from arXiv: 2605.25237 by Alexei Vazquez.

**Figure 2.** Figure 2: FIG. 2. Scaling between the average shortest path multi [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗

**Figure 4.** Figure 4: FIG. 4. Scaling between the average shortest path multiplicity [PITH_FULL_IMAGE:figures/full_fig_p004_4.png] view at source ↗

read the original abstract

The shortest path multiplicity, here denoted by $\mu$, is an important metric of complex networks. For real networks $\mu$ is high and it correlates with the network community structure. Since local network evolution induces network communities, it is possible that a high shortest path multiplicity is the natural expectation of local evolution rules. Here I demonstrate, by means of numerical simulations, that this is indeed the case. For random graphs with arbitrary degree distributions $p_k$, $\langle\mu\rangle\sim \langle k(k-1)\rangle / (\langle k\rangle e)$, growing with the network size when $p_k\sim k^{-\gamma}$ and $\gamma\leq3$. For networks generated by local rules, $\langle\mu\rangle$ increases with the network size and it does so faster than what is observed in their randomized versions. Furthermore, the number of communities increases with the network size and the correlation with $\langle \mu\rangle$ follows.

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.

Desk Editor's Note private letter to a colleague

Simulations show local-rule networks grow shortest-path multiplicity faster than degree-matched random graphs, with a clean formula for the random case.

read the letter

The main result is that networks built by local evolution rules show ⟨μ⟩ rising with size more steeply than their randomized, degree-sequence-matched counterparts, and this tracks the rise in community count. The paper also supplies an explicit expression for ⟨μ⟩ in random graphs with arbitrary p_k, which is ⟨k(k-1)⟩ / (⟨k⟩ e) and grows when the degree tail is heavy enough.

That comparison is the concrete new piece: it gives a mechanistic route from local attachment to the high multiplicity seen in real data, rather than just observing the correlation. The random-graph formula is a useful benchmark that stands on its own.

The soft spot is the usual one with generative models: the specific local rules used in the simulations may or may not be representative of the mechanisms that actually produce communities in empirical networks. Degree-preserving randomization removes some but not necessarily all non-local correlations, so the attribution to “local rules” needs the implementation details and controls to be tight. If those checks are present and the scaling survives them, the claim holds; otherwise it is suggestive rather than conclusive.

This is for people working on network growth models and path-based metrics. It is worth sending to referees because the simulation result is falsifiable and the random-graph expression is independently checkable. A careful review can settle whether the local-rule attribution survives the controls.

Referee Report

2 major / 0 minor

Summary. The paper claims that shortest path multiplicity μ is naturally high in networks due to local evolution rules that also induce communities. For random graphs with arbitrary degree distribution p_k, it states ⟨μ⟩ ∼ ⟨k(k-1)⟩ / (⟨k⟩ e), which grows with network size for p_k ~ k^{-γ} when γ ≤ 3. Numerical simulations are presented to show that networks generated by local rules exhibit faster growth of ⟨μ⟩ with size than degree-preserving randomized versions, with the number of communities also increasing and correlating with ⟨μ⟩.

Significance. If the simulation results are robust, the work would establish a direct mechanistic link between local network evolution, community structure, and shortest-path multiplicity, providing a baseline expectation for μ in real networks without invoking additional global mechanisms.

major comments (2)

[Abstract] Abstract: The scaling formula ⟨μ⟩ ∼ ⟨k(k-1)⟩ / (⟨k⟩ e) for random graphs is presented as a key theoretical expectation but without derivation, proof sketch, or reference to an equation or section where it is obtained. This baseline is load-bearing for the claim that local-rule networks grow faster.
[Simulation results] Simulation results: The central claim that local-rule networks show faster ⟨μ⟩ growth than randomized counterparts rests on numerical simulations, yet no details are supplied on the specific local evolution rules, network sizes simulated, number of realizations, statistical controls, error analysis, or the precise randomization procedure (e.g., configuration model or other degree-sequence preservation method). These omissions prevent verification of the scaling statements and the attribution to local structure.

Simulated Author's Rebuttal

2 responses · 0 unresolved

Thank you for the referee's thoughtful review of our manuscript on local network evolution rules and shortest path multiplicity. We address each major comment point by point below.

read point-by-point responses

Referee: [Abstract] Abstract: The scaling formula ⟨μ⟩ ∼ ⟨k(k-1)⟩ / (⟨k⟩ e) for random graphs is presented as a key theoretical expectation but without derivation, proof sketch, or reference to an equation or section where it is obtained. This baseline is load-bearing for the claim that local-rule networks grow faster.

Authors: We agree that the abstract presents the scaling formula without a derivation, proof sketch, or reference to an equation or section. The manuscript does not include an explicit derivation of this expression. In the revised version, we will add a brief derivation or proof sketch in the main text (based on the configuration model approximation) and include a reference to the relevant section or equation in the abstract. revision: yes
Referee: [Simulation results] Simulation results: The central claim that local-rule networks show faster ⟨μ⟩ growth than randomized counterparts rests on numerical simulations, yet no details are supplied on the specific local evolution rules, network sizes simulated, number of realizations, statistical controls, error analysis, or the precise randomization procedure (e.g., configuration model or other degree-sequence preservation method). These omissions prevent verification of the scaling statements and the attribution to local structure.

Authors: We acknowledge that the simulation details are not sufficiently described in the current manuscript. In the revision, we will expand the relevant sections to specify the local evolution rules employed, the network sizes used in the simulations, the number of realizations performed, any statistical controls and error analysis applied, and the precise method for generating the randomized counterparts (such as the configuration model). revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation relies on independent theory and external benchmarks

full rationale

The paper states an independent closed-form expression for ⟨μ⟩ in random graphs with arbitrary degree distribution p_k and then reports separate numerical simulations comparing locally evolved networks against their degree-sequence randomized counterparts. The randomization step and the random-graph formula are not derived from the local-rule results; they function as external references. No load-bearing self-citations, self-definitional steps, or fitted quantities renamed as predictions appear in the provided text. The central claim therefore rests on simulation evidence that is not tautological with its inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper rests on standard domain assumptions of network science without introducing new free parameters, axioms beyond those stated, or invented entities.

axioms (2)

domain assumption Local network evolution induces network communities
Explicitly stated in the abstract as the premise linking local rules to communities.
domain assumption Random graphs with the same degree distribution form an appropriate null model for isolating local-structure effects
Used as the baseline for all comparisons in the simulations.

pith-pipeline@v0.9.1-grok · 5687 in / 1312 out tokens · 32000 ms · 2026-07-02T23:14:30.998336+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Reference graph

Works this paper leans on

18 extracted references · 2 canonical work pages

[1]

For this model⟨µ⟩ increases faster than linear with increasing logn

model: node addition, link creation to a randomly chosen existing node, local search stopping at 1 step, and link addition to the reached node. For this model⟨µ⟩ increases faster than linear with increasing logn. A fit to the log-quadratic law ⟨µ⟩S,I =a+blogn+c(logn) 2,(2) is consistent with the data points for the range of network sizes tested (Fig. 2a, ...
[2]

In contrast, the duplication rule create cycles of length 4

There is only one shortest path between the nodes in a 3-nodes cycle. In contrast, the duplication rule create cycles of length 4. Each node in a 4-cycle has two shortest paths to the opposite node two steps away. The duplication rule boosts the shortest path multiplicity. 101 102 103 n 1.0 1.5 2.0 2.5 a) L = 1 L = 3 2.5 5.0 7.5 10.0 1.0 1.5 2.0 2.5 c) L ...
[3]

Y. Deng, J. Wu, X. Lu, P. Holme, D. Li, Z. Di, G. Chen, and J. Kurths, Nature Communications17, 2283 (2026)

2026
[4]

Vazquez, Phys

A. Vazquez, Phys. Rev. E67, 056104 (2003)

2003
[5]

J. M. Kleinberg, R. Kumar, P. Raghavan, S. Ra- jagopalan, and A. S. Tomkins, inComputing and Com- binatorics, Lecture Notes in Computer Science, edited by T. Asano, H. Imai, D. T. Lee, S.-i. Nakano, and T. Tokuyama (Springer, Berlin, Heidelberg, 1999) pp. 1– 17

1999
[6]

Vazquez, Europh

A. Vazquez, Europh. Lett.54, 430 (2001)

2001
[7]

E. M. Jin, M. Girvan, and M. E. J. Newman, Phys. Rev. E64, 046132 (2001)

2001
[8]

V´ azquez, A

A. V´ azquez, A. Flammini, A. Maritan, and A. Vespig- nani, Complexus1, 38 (2003)

2003
[9]

Pastor-Satorras, E

R. Pastor-Satorras, E. Smith, and R. V. Sol´ e, J. Theor. Biol.222, 199 (2003)

2003
[10]

Vazquez, Phys

A. Vazquez, Phys. Rev. E111, 064314 (2025)

2025
[11]

Bianconi, R

G. Bianconi, R. K. Darst, J. Iacovacci, and S. Fortunato, Phys. Rev. E90, 042806 (2014)

2014
[12]

S. N. Dorogovtsev, J. F. F. Mendes, and A. N. Samukhin, Phys. Rev. E63, 062101 (2001)

2001
[13]

T. P. Peixoto, figshare (2014), 10.6084/m9.figshare.1164194

work page doi:10.6084/m9.figshare.1164194 2014
[14]

Network reconstruction via the minimum description length principle,

T. P. Peixoto, “Network reconstruction via the minimum description length principle,” (2024), arXiv:2405.01015 [stat.ML]

work page arXiv 2024
[15]

The MapE- quation software package,

D. Edler, A. Holmgren, and M. Rosvall, “The MapE- quation software package,”https://mapequation.org (2025)

2025
[16]

Park and M

J. Park and M. E. J. Newman, Phys. Rev. E70, 066117 (2004)

2004
[17]

Y. Dong, Y. Deng, and J. Wu, Chaos, Solitons & Fractals 193, 116124 (2025)

2025
[18]

S. N. Dorogovtsev, A. V. Goltsev, and J. F. F. Mendes, Phys. Rev. E65, 066122 (2002)

2002

[1] [1]

For this model⟨µ⟩ increases faster than linear with increasing logn

model: node addition, link creation to a randomly chosen existing node, local search stopping at 1 step, and link addition to the reached node. For this model⟨µ⟩ increases faster than linear with increasing logn. A fit to the log-quadratic law ⟨µ⟩S,I =a+blogn+c(logn) 2,(2) is consistent with the data points for the range of network sizes tested (Fig. 2a, ...

[2] [2]

In contrast, the duplication rule create cycles of length 4

There is only one shortest path between the nodes in a 3-nodes cycle. In contrast, the duplication rule create cycles of length 4. Each node in a 4-cycle has two shortest paths to the opposite node two steps away. The duplication rule boosts the shortest path multiplicity. 101 102 103 n 1.0 1.5 2.0 2.5 a) L = 1 L = 3 2.5 5.0 7.5 10.0 1.0 1.5 2.0 2.5 c) L ...

[3] [3]

Y. Deng, J. Wu, X. Lu, P. Holme, D. Li, Z. Di, G. Chen, and J. Kurths, Nature Communications17, 2283 (2026)

2026

[4] [4]

Vazquez, Phys

A. Vazquez, Phys. Rev. E67, 056104 (2003)

2003

[5] [5]

J. M. Kleinberg, R. Kumar, P. Raghavan, S. Ra- jagopalan, and A. S. Tomkins, inComputing and Com- binatorics, Lecture Notes in Computer Science, edited by T. Asano, H. Imai, D. T. Lee, S.-i. Nakano, and T. Tokuyama (Springer, Berlin, Heidelberg, 1999) pp. 1– 17

1999

[6] [6]

Vazquez, Europh

A. Vazquez, Europh. Lett.54, 430 (2001)

2001

[7] [7]

E. M. Jin, M. Girvan, and M. E. J. Newman, Phys. Rev. E64, 046132 (2001)

2001

[8] [8]

V´ azquez, A

A. V´ azquez, A. Flammini, A. Maritan, and A. Vespig- nani, Complexus1, 38 (2003)

2003

[9] [9]

Pastor-Satorras, E

R. Pastor-Satorras, E. Smith, and R. V. Sol´ e, J. Theor. Biol.222, 199 (2003)

2003

[10] [10]

Vazquez, Phys

A. Vazquez, Phys. Rev. E111, 064314 (2025)

2025

[11] [11]

Bianconi, R

G. Bianconi, R. K. Darst, J. Iacovacci, and S. Fortunato, Phys. Rev. E90, 042806 (2014)

2014

[12] [12]

S. N. Dorogovtsev, J. F. F. Mendes, and A. N. Samukhin, Phys. Rev. E63, 062101 (2001)

2001

[13] [13]

T. P. Peixoto, figshare (2014), 10.6084/m9.figshare.1164194

work page doi:10.6084/m9.figshare.1164194 2014

[14] [14]

Network reconstruction via the minimum description length principle,

T. P. Peixoto, “Network reconstruction via the minimum description length principle,” (2024), arXiv:2405.01015 [stat.ML]

work page arXiv 2024

[15] [15]

The MapE- quation software package,

D. Edler, A. Holmgren, and M. Rosvall, “The MapE- quation software package,”https://mapequation.org (2025)

2025

[16] [16]

Park and M

J. Park and M. E. J. Newman, Phys. Rev. E70, 066117 (2004)

2004

[17] [17]

Y. Dong, Y. Deng, and J. Wu, Chaos, Solitons & Fractals 193, 116124 (2025)

2025

[18] [18]

S. N. Dorogovtsev, A. V. Goltsev, and J. F. F. Mendes, Phys. Rev. E65, 066122 (2002)

2002