Local network evolution rules driving shortest path multiplicity
Abstract
The shortest path multiplicity, here denoted by μ, is an important metric of complex networks. For real networks μ 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 and exact results, that this is indeed the case. For random graphs with arbitrary degree distributions pk, ⟨μ⟩∼ ⟨ k(k−1)⟩ / (⟨ k⟩ e), growing with the network size when pk∼ k−γ and γ≤3. For networks generated by stochastic 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.
Versions
Related
- Shortest-Path Multiplicity Heterogeneity as a Graph Diagnostic for Radial Organization in Sampled Geometries
- Multiplicity One for Unitary Ginzburg--Rallis Models over Local Fields
- Mixed local-nonlocal eigenvalue problems in the Heisenberg group: spectral theory and singular multiplicity
- Existence and multiplicity of solutions for mixed local and nonlocal Kirchhoff type problems
- Measuring consistency via ensemble margin and local prediction variability: Auditing decision systems in the presence of predictive multiplicity
BibTeX
@misc{vazquez2026local,
title = {{Local network evolution rules driving shortest path multiplicity}},
author = {Alexei Vazquez},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2605.25237},
eprint = {2605.25237},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.25237},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Local network evolution rules driving shortest path multiplicity
AU - Alexei Vazquez
PY - 2026
DA - 2026/10/13
PB - arXiv
DO - 10.48550/arxiv.2605.25237
UR - https://arxiv.org/abs/2605.25237
AB - The shortest path multiplicity, here denoted by μ, is an important metric of complex networks. For real networks μ 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 and exact results, that this is indeed the case. 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. For networks generated by stochastic 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.
ER -