pith. sign in

arxiv: 2501.11226 · v2 · submitted 2025-01-20 · 🧮 math.PR · cs.DS· cs.SI· math.CO

Local Limits of Small World Networks

Yeganeh Alimohammadi , Senem I\c{s}{\i}k , Amin Saberi This is my paper

Pith reviewed 2026-05-23 05:43 UTC · model grok-4.3

classification 🧮 math.PR cs.DScs.SImath.CO
keywords small-world networkslocal convergenceWatts-Strogatz modelKleinberg modelBenjamini-Schramm convergencebond percolationnetwork measuresgiant component
0
0 comments X

The pith

The Watts-Strogatz and Kleinberg small-world models converge locally, so their clustering, PageRank, spanning-tree counts and percolation thresholds all settle to limits fixed by finite neighborhoods.

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

The paper establishes local convergence for the Watts-Strogatz and Kleinberg constructions by applying marked local convergence. Once the local neighborhood around a typical vertex stabilizes, any network statistic that depends only on small balls around vertices must converge to a value computed from the limiting object. This covers the clustering coefficient, PageRank, the size of a greedy maximal independent set, the number of spanning trees, and tree entropy. The same local information supplies estimates for the giant-component size under bond percolation and for the scale of epidemic or information cascades. In the Kleinberg model the local limit itself changes character exactly when the long-range connection parameter crosses the known threshold for efficient decentralized search.

Core claim

Applying the theory of marked local convergence to the Watts-Strogatz and Kleinberg constructions yields that these networks converge locally. Consequently, measures such as the clustering coefficient, PageRank, the size of a greedy maximal independent set, the number of spanning trees, and tree entropy all converge to limits determined solely by the local structure. The framework also permits estimation of the giant component size under bond percolation and related cascade sizes from local data. For the Kleinberg model, the limiting object exhibits a critical transition exactly at the parameter value where decentralized search efficiency changes.

What carries the argument

Marked local convergence (Benjamini-Schramm convergence) applied to the random graphs of the Watts-Strogatz and Kleinberg models; it produces a limiting rooted marked graph whose law encodes all local neighborhood statistics.

If this is right

  • Clustering coefficient and PageRank converge to explicit values read off the local limit.
  • The giant-component fraction after bond percolation is recoverable from the distribution of small neighborhoods alone.
  • The number of spanning trees and the associated tree entropy converge with network size.
  • Epidemic and information-cascade sizes are estimable from local data for both models.
  • In the Kleinberg model the local limit changes its qualitative form at the same parameter threshold that separates efficient from inefficient decentralized search.

Where Pith is reading between the lines

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

  • The same local-limit object could be used to simulate large-scale behavior of these networks without ever constructing the full graph.
  • Other small-world constructions whose local neighborhoods are easy to describe might inherit similar convergence results for global functionals.
  • The observed change in the Kleinberg local limit supplies a structural explanation for the known algorithmic threshold that does not rely on global path-length arguments.

Load-bearing premise

The marked local convergence framework applies directly to both models for every choice of their parameters without extra regularity conditions on the underlying graphs.

What would settle it

Compute the clustering coefficient on a sequence of Kleinberg networks with fixed parameters and growing size; if the values do not approach the number obtained from the local limit, the convergence claim fails.

read the original abstract

Small-world networks, known for high local clustering and short path lengths, are a fundamental structure in many real-world systems, including social, biological, and technological networks. We apply the theory of (marked) local convergence (also known as Benjamini-Schramm convergence) to derive the limiting behavior of the local structures for two commonly studied small-world network models: the Watts-Strogatz and the Kleinberg models. Establishing local convergence enables us to show that key network measures, such as clustering coefficient, PageRank, greedy maximal independent set, number of spanning trees and tree entropy, converge as network size increases, with their limits determined by the graph's local structure. Additionally, this framework facilitates the estimation of global phenomena, such as the size of the giant component under bond percolation and the closely related properties, the size of the epidemic and information cascades, using local information from small neighborhoods. Furthermore, we observe a critical change in the behavior of the limit exactly when the parameter governing long-range connections in the Kleinberg model crosses the threshold where decentralized search remains efficient, offering a new perspective on why decentralized algorithms fail in certain regimes.

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 applies the theory of marked local convergence (Benjamini-Schramm convergence) to the Watts-Strogatz and Kleinberg small-world models. It establishes the existence of local limits for the full parameter ranges (p ∈ [0,1] for Watts-Strogatz; α > 0 for Kleinberg in d dimensions) by explicit computation of the limiting rooted marked graphs, handling the normalization of long-range connection probabilities. These limits are then used to deduce convergence of several functionals (clustering coefficient, PageRank, greedy maximal independent set, number of spanning trees, tree entropy) and to analyze global properties such as the giant component size under bond percolation and related cascade sizes. A phase transition in the local limit object is identified precisely at the decentralized-search threshold α = d.

Significance. If the derivations hold, the work supplies a rigorous, unified local-limit framework for two canonical small-world models that directly transfers to convergence statements for both local and global network measures. The explicit treatment of the long-range stub normalization and the resulting phase transition at the search-efficiency threshold constitute a concrete contribution that links local structure to algorithmic behavior. The approach requires no additional regularity conditions beyond the standard model definitions.

minor comments (3)
  1. [§2.2] §2.2: the definition of the marked graph space could usefully include an explicit reference to the topology used for the convergence statement (e.g., the usual local weak topology on rooted marked graphs).
  2. [Figure 1] Figure 1: the caption does not indicate whether the depicted realizations are for finite n or already in the limit; adding this clarification would improve readability.
  3. [abstract, §1] The statement that the limits are 'determined by the graph's local structure' (abstract and §1) is correct but could be sharpened by a one-sentence reminder that the functionals are continuous with respect to the local topology.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive and detailed summary of our work, as well as their recommendation to accept the manuscript. The report contains no major comments.

Circularity Check

0 steps flagged

No significant circularity; derivation by direct computation of local limits

full rationale

The paper establishes marked local convergence for the Watts-Strogatz and Kleinberg models via explicit computation of the limiting rooted marked graphs for the full parameter ranges, with the normalization of long-range edge probabilities handled directly in the limit object. This yields the phase transition at the search-efficiency threshold without invoking fitted parameters, self-definitions, or load-bearing self-citations. Standard transfer arguments then apply to the listed functionals and percolation quantities. The central claims rest on independent verification of the local limit objects rather than reduction to inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on the applicability of marked local convergence to the two generative models; no new free parameters, invented entities, or ad-hoc axioms are introduced in the abstract.

axioms (1)
  • domain assumption Marked local convergence (Benjamini-Schramm convergence) applies to the Watts-Strogatz and Kleinberg models for the stated parameter ranges.
    The entire program of deriving limits for network functionals is predicated on this applicability.

pith-pipeline@v0.9.0 · 5741 in / 1274 out tokens · 28974 ms · 2026-05-23T05:43:56.560247+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

45 extracted references · 45 canonical work pages

  1. [1]

    Aldous and J.M

    D. Aldous and J.M. Steele. The objective method: probabilistic combinatorial optimization and local weak convergence. In Prob- ability on discrete structures, volume 110 of Encyclopaedia Math. Sci., pages 1–72. Springer, Berlin, 2004. 2

    work page 2004

  2. [2]

    Algorithms using local graph features to predict epidemics

    Yeganeh Alimohammadi, Christian Borgs, and Amin Saberi. Algorithms using local graph features to predict epidemics. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3430–3451. SIAM, 2022. 1, 9

    work page 2022

  3. [3]

    Locality of random digraphs on expanders.The Annals of Probability, 51(4):1249 – 1297, 2023

    Yeganeh Alimohammadi, Christian Borgs, and Amin Saberi. Locality of random digraphs on expanders.The Annals of Probability, 51(4):1249 – 1297, 2023. 10

    work page 2023

  4. [4]

    Epidemic forecasting on networks: Bridg- ing local samples with global outcomes

    Yeganeh Alimohammadi, Christian Borgs, Remco van der Hofstad, and Amin Saberi. Epidemic forecasting on networks: Bridg- ing local samples with global outcomes. Technical report, Technical report, Working paper, 2023. 9

    work page 2023

  5. [5]

    Discrete small world networks

    A Barbour and G Reinert. Discrete small world networks. ELECTRONIC JOURNAL OF PROBABILITY, 11, 2006. 10

    work page 2006

  6. [6]

    The physics of financial networks

    Marco Bardoscia, Paolo Barucca, Stefano Battiston, Fabio Caccioli, Giulio Cimini, Diego Garlaschelli, Fabio Saracco, Tiziano Squartini, and Guido Caldarelli. The physics of financial networks. Nature Reviews Physics, 3(7):490–507, 2021. 10

    work page 2021

  7. [7]

    On the properties of small-world network models

    Alain Barrat and Martin Weigt. On the properties of small-world network models. The European Physical Journal B-Condensed Matter and Complex Systems, 13:547–560, 2000. 9

    work page 2000

  8. [8]

    Small-world brain networks

    Danielle Smith Bassett and ED Bullmore. Small-world brain networks. The neuroscientist, 12(6):512–523, 2006. 1

    work page 2006

  9. [9]

    The diameter of long-range percolation clusters on finite cycles.Random Structures & Algorithms, 19(2):102–111, 2001

    Itai Benjamini and Noam Berger. The diameter of long-range percolation clusters on finite cycles.Random Structures & Algorithms, 19(2):102–111, 2001. 10

    work page 2001

  10. [10]

    Recurrence of distributional limits of finite planar graphs, 2001

    Itai Benjamini and Oded Schramm. Recurrence of distributional limits of finite planar graphs, 2001. 1, 2

    work page 2001

  11. [11]

    Berger, C

    N. Berger, C. Borgs, J. Chayes, and A. Saberi. Asymptotic behavior and distributional limits of preferential attachment graphs. Annals of Probability, 42(1):1–40, 2014. 10

    work page 2014

  12. [12]

    Bollob ´as, S

    B. Bollob ´as, S. Janson, and O. Riordan. The phase transition in inhomogeneous random graphs. Random Structures Algorithms , 31(1):3–122, 2007. 1, 10

    work page 2007

  13. [13]

    Sparse random graphs with clustering

    B ´ela Bollob ´as, Svante Janson, and Oliver Riordan. Sparse random graphs with clustering. Random Structures & Algorithms , 38(3):269–323, 2011. 10

    work page 2011

  14. [14]

    Matchings on infinite graphs.Probability Theory and Related Fields, 157:183–208,

    Charles Bordenave, Marc Lelarge, and Justin Salez. Matchings on infinite graphs.Probability Theory and Related Fields, 157:183–208,

    work page

  15. [15]

    Protein interaction networks from yeast to human

    Peer Bork, Lars J Jensen, Christian Von Mering, Arun K Ramani, Insuk Lee, and Edward M Marcotte. Protein interaction networks from yeast to human. Current opinion in structural biology, 14(3):292–299, 2004. 1

    work page 2004

  16. [16]

    Graph structure in the web.Computer networks, 33(1-6):309–320, 2000

    Andrei Broder, Ravi Kumar, Farzin Maghoul, Prabhakar Raghavan, Sridhar Rajagopalan, Raymie Stata, Andrew Tomkins, and Janet Wiener. Graph structure in the web.Computer networks, 33(1-6):309–320, 2000. 10

    work page 2000

  17. [17]

    The diameter of a long-range percolation graph

    Don Coppersmith, David Gamarnik, and Maxim Sviridenko. The diameter of a long-range percolation graph. Random Structures & Algorithms, 21(1):1–13, 2002. 10

    work page 2002

  18. [18]

    Dembo and A

    A. Dembo and A. Montanari. Gibbs measures and phase transitions on sparse random graphs. Braz. J. Probab. Stat., 24(2):137–211,

    work page

  19. [19]

    Tight lower bounds for greedy routing in uniform small world rings

    Martin Dietzfelbinger and Philipp Woelfel. Tight lower bounds for greedy routing in uniform small world rings. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 591–600, 2009. 10

    work page 2009

  20. [20]

    Random walks on small world networks

    Martin E Dyer, Andreas Galanis, Leslie Ann Goldberg, Mark Jerrum, and Eric Vigoda. Random walks on small world networks. ACM Transactions on Algorithms (TALG), 16(3):1–33, 2020. 10

    work page 2020

  21. [21]

    Abraham D. Flaxman. Expansion and lack thereof in randomly perturbed graphs. In William Aiello, Andrei Broder, Jeannette Janssen, and Evangelos Milios, editors, Algorithms and Models for the Web-Graph , pages 24–35, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg. 9 30 Y. ALIMOHAMMADI, S. IS ¸IK, AND A. SABERI

    work page 2008

  22. [22]

    On the searchability of small-world networks with arbitrary underlying structure

    Pierre Fraigniaud and George Giakkoupis. On the searchability of small-world networks with arbitrary underlying structure. In Proceedings of the forty-second ACM symposium on Theory of computing, pages 389–398, 2010. 10

    work page 2010

  23. [23]

    Maximum weight independent sets and matchings in sparse random graphs

    David Gamarnik, Tomasz Nowicki, and Grzegorz Swirszcz. Maximum weight independent sets and matchings in sparse random graphs. exact results using the local weak convergence method. Random Structures & Algorithms, 28(1):76–106, 2006. 1, 10

    work page 2006

  24. [24]

    Hydrodynamic limits of non-markovian interacting particle systems on sparse graphs

    Ankan Ganguly and Kavita Ramanan. Hydrodynamic limits of non-markovian interacting particle systems on sparse graphs. arXiv preprint arXiv:2205.01587, 2022. 10

    work page arXiv 2022

  25. [25]

    Garavaglia, R

    A. Garavaglia, R. Hazra, R. van der Hofstad, and R. Ray. Universality of the local limit in preferential attachment models. arXiv:2212.05551 [math.PR], 2022. 10

    work page arXiv 2022

  26. [26]

    Local weak convergence for pagerank

    Alessandro Garavaglia, Remco van der Hofstad, and Nelly Litvak. Local weak convergence for pagerank. The Annals of Applied Probability, 30(1):pp. 40–79, 2020. 1, 9, 10

    work page 2020

  27. [27]

    Optimal path search in small worlds: dimension matters

    George Giakkoupis and Nicolas Schabanel. Optimal path search in small worlds: dimension matters. In Proceedings of the forty- third annual ACM symposium on Theory of computing, pages 393–402, 2011. 10

    work page 2011

  28. [28]

    Random graphs and complex networks

    Remco van der Hofstad. Random graphs and complex networks. Cambridge Series in Statistical and Probabilistic Mathematics , 1,

    work page

  29. [29]

    The brainstem reticular formation is a small-world, not scale-free, net- work

    Mark D Humphries, Kevin Gurney, and Tony J Prescott. The brainstem reticular formation is a small-world, not scale-free, net- work. Proceedings of the Royal Society B: Biological Sciences, 273(1585):503–511, 2006. 1

    work page 2006

  30. [30]

    The small-world phenomenon: an algorithmic perspective

    Jon Kleinberg. The small-world phenomenon: an algorithmic perspective. In Proceedings of the Thirty-Second Annual ACM Sympo- sium on Theory of Computing , STOC ’00, page 163–170, New York, NY, USA, 2000. Association for Computing Machinery. 1, 5, 7, 20, 26, 35

    work page 2000

  31. [31]

    Lodewijks

    J ˙Komj´athy and B. Lodewijks. Explosion in weighted hyperbolic random graphs and geometric inhomogeneous random graphs. Stochastic Process. Appl., 130(3):1309–1367, 2020. 10

    work page 2020

  32. [32]

    Krioukov, F

    D. Krioukov, F. Papadopoulos, M. Kitsak, A. Vahdat, and M. Bogu˜n´a. Hyperbolic geometry of complex networks.Phys. Rev. E (3), 82(3):036106, 18, 2010. 10

    work page 2010

  33. [33]

    Network-on-chip: the next generation of system-on-chip integration

    Santanu Kundu and Santanu Chattopadhyay. Network-on-chip: the next generation of system-on-chip integration . Taylor & Francis,

    work page

  34. [34]

    Kurauskas

    V . Kurauskas. On local weak limit and subgraph counts for sparse random graphs. Journal of Applied Probability , 59(3):755–776,

    work page

  35. [35]

    , Ramanan, K

    Daniel Lacker, Kavita Ramanan, and Ruoyu Wu. Local weak convergence for sparse networks of interacting processes. arXiv preprint arXiv:1904.02585, 2019. 1, 10

    work page arXiv 1904

  36. [36]

    Bow-tie structures of twitter discursive communities

    Mattia Mattei, Manuel Pratelli, Guido Caldarelli, Marinella Petrocchi, and Fabio Saracco. Bow-tie structures of twitter discursive communities. Scientific Reports, 12(1):12944, 2022. 10

    work page 2022

  37. [37]

    Randomized rumor spreading in poorly connected small-world networks.Random Structures & Algorithms, 49(1):185–208, 2016

    Abbas Mehrabian and Ali Pourmiri. Randomized rumor spreading in poorly connected small-world networks.Random Structures & Algorithms, 49(1):185–208, 2016. 10

    work page 2016

  38. [38]

    M. E. J. Newman and D. J. Watts. Scaling and percolation in the small-world network model. Physical Review E, 60(6):7332–7342,

    work page

  39. [39]

    Analyzing and characterizing small-world graphs

    Van Nguyen and Chip Martel. Analyzing and characterizing small-world graphs. InProceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, pages 311–320, 2005. 10

    work page 2005

  40. [40]

    The pagerank citation ranking : Bringing order to the web

    Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The pagerank citation ranking : Bringing order to the web. In The Web Conference, 1999. 9

    work page 1999

  41. [41]

    The ubiquity of small-world networks

    Qawi K Telesford, Karen E Joyce, Satoru Hayasaka, Jonathan H Burdette, and Paul J Laurienti. The ubiquity of small-world networks. Brain Connectivity, 1(5):367–375, 2011. 1

    work page 2011

  42. [42]

    Small-world networks and management science research: A review

    Brian Uzzi, Luis AN Amaral, and Felix Reed-Tsochas. Small-world networks and management science research: A review. Euro- pean Management Review, 4(2):77–91, 2007. 1

    work page 2007

  43. [43]

    van der Hofstad, J

    R. van der Hofstad, J. Komj ´athy, and V . Vadon. Random intersection graphs with communities.Adv. in Appl. Probab., 53(4):1061– 1089, 2021. 10

    work page 2021

  44. [44]

    Local limits of spatial inhomogeneous random graphs

    Remco van der Hofstad, Pim van der Hoorn, and Neeladri Maitra. Local limits of spatial inhomogeneous random graphs. arXiv preprint arXiv:2107.08733, 2021. 1, 7, 10, 26, 27, 28, 35

    work page arXiv 2021

  45. [45]

    Watts and Steven H

    Duncan J. Watts and Steven H. Strogatz. Collective dynamics of ‘small-world’ networks.Nature, 393(6684):440–442, 1998. 1, 3 LOCAL LIMITS OF SMALL WORLD NETWORKS 31 APPENDIX A. S ECOND MOMENT : P ROOF OF LEMMA 8.3 For the second moment, we would like to show that lim n→∞ Var   1 n2 X on∈V (Gn) 1 ϵ r((Gn, on) ≃ H∗)   = E     1 n2 X on∈V (Gn) 1 ϵ r(...

    work page 1998