Pith. sign in

REVIEW 4 major objections 4 minor 52 references

Fast Geographic Routing in Fixed-Growth Graphs

T0 review · 4 major / 4 minor · reviewed 2026-08-09 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper extends the randomized highway model to any fixed-growth graph and proves tight greedy-routing and diameter bounds, then shows that matching the clustering exponent to the graph's dimensionality improves routing on U.S.

desk verdict The generalization to fixed-growth graphs is the right kind of step, but the shell-size cancellation at the heart of the proof does not hold as written, so the routing and diameter bounds are not established. read the letter →

arxiv 2502.03663 v2 pith:HP4XBJF2 submitted 2025-02-05 cs.DS

Ofek Gila , Michael T. Goodrich , Abraham M. Illickan , Vinesh Sridhar This is my paper · ORCID
classification cs.DS MSC 68R1068W2005C80
keywords small-worldnetworksgreedyroutingfixed-growthgraphsrandomizedhighwaymodelgraphdimensionalitydiameterboundsroadbounded-growth
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper establishes that the randomized highway model for small-world networks works on any fixed-growth graph, a bounded-growth family in which every ball of radius $\ell$ contains $\Theta(\ell^\alpha)$ nodes, rather than only on two-dimensional lattices. With highway constant $k\in\Theta(\log n)$ and the clustering exponent set to the graph's dimensionality $\alpha$, greedy routing between nodes at distance $\Theta(\alpha\sqrt{n})$ is shown to take $\Theta(\log n)$ hops with high probability when $\alpha\geq 2$, and $\Theta(\alpha\sqrt{\log^2 n})$ hops when $\alpha\leq 2$; the diameter is $\Theta(\log n/\log\log n)$ for $\alpha>2$ and $\Theta(\alpha\sqrt{\log^2 n})$ for $\alpha\leq 2$. The paper also reports experiments on all 50 U.S. state road networks and DC in which using the estimated $\alpha$ as the clustering exponent beats the lattice value $2$ for every state, and in which $\alpha$ predicts the empirically optimal exponent better than network size does. A sympathetic reader would care because it replaces a rigid geometric assumption with a measurable growth property, making the small-world routing guarantee applicable to real spatial networks.

What carries the argument

The load-bearing object is the shell partition of a fixed-growth graph. For a node $u$, the shell $S_b^{(w)}(u)$ is the annulus between balls of radii proportional to $(b+1)w$ and $bw$, with width $w\in\Theta(\alpha\sqrt{k\log n})$; shells partition the graph even though balls may overlap, which the lattice tiling used by earlier work cannot do. Lemma 2 shows that, with high probability, a shell at shell-distance $b$ contains $\Theta(b^{\alpha-1}\log n)$ highway nodes, because the ball-count difference $\Theta(((b+1)^\alpha-b^\alpha)w^\alpha)$ cancels to $\Theta(b^{\alpha-1}w^\alpha)$. Shells supply the estimates needed to bound the normalization constant $z(u)=\sum_{h\in H} d(u,h)^{-\alpha}$, and that bound gives the probability that a long-range contact improves the distance to the destination, which in turn drives the greedy-routing and diameter theorems.

What would settle it

Take a road network or a synthetic fixed-growth graph with estimated $\alpha$, set $k=c\log n$, and count highway nodes inside shells at several shell-distances $b$; if the counts do not scale as $\Theta(b^{\alpha-1}\log n)$ with high probability, the normalization-constant bounds and the theorems built on them fail. A sharper test is to construct a graph whose ball sizes satisfy $|B_\ell(u)|=\Theta(\ell^\alpha)$ but whose shell sizes oscillate so the polynomial cancellation does not hold, simulate greedy routing with $k=\Theta(\log n)$, and check whether the hop count exceeds the Theorem 2 bound with high probability.

Watch

Extended reading notes

Core claim

The paper's central claim is that the randomized highway model achieves tight greedy-routing and diameter bounds on every fixed-growth graph of dimensionality $\alpha$, not just lattices. In this model each node independently becomes a highway node with probability $1/k$, highway nodes receive $\Theta(k)$ long-range contacts to other highway nodes with probability proportional to $d(u,v)^{-\alpha}$, and each non-highway node stores a pointer to the neighbor closest to the highway. Theorem 2 states that for $k\in\Theta(\log n)$ and $d(s,t)=\Theta(\alpha\sqrt{n})$, greedy routing succeeds in $\Theta(\log n)$ hops with high probability in $\log n$ if $\alpha\geq 2$, and in $\Theta(\alpha\sqrt{\log^2 n})$ hops if $\alpha\leq 2$; Theorem 3 states the diameter is $\Theta(\log n/\log\log n)$ for $\alpha>2$ and $\Theta(\alpha\sqrt{\log^2 n})$ for $\alpha\leq 2$. The empirical half of the paper claims that modeling the U.S. road network as fixed-growth and choosing the clustering exponent equal to the estimated dimensionality gives better greedy-routing performance than the lattice exponent $2$ on every state, and that the estimated dimensionality is a better predictor of the optimal exponent than the network's size.

Load-bearing premise

The load-bearing assumption is that every ball in every graph of the family has size $\Theta(\ell^\alpha)$ with the same hidden constants, so that the difference between consecutive ball sizes really is $\Theta(b^{\alpha-1}w^\alpha)$; the paper itself notes that on a single finite graph the constants can be chosen to make any dimensionality $\alpha$ fit, so the road-network application rests on an unvalidated heuristic.

Editorial extensions

If this is right

  • The $\Theta(\log n)$ greedy-routing guarantee no longer requires a square-lattice substrate; any fixed-growth graph with dimensionality $\alpha$ admits the same tight bound when the clustering exponent is set to $\alpha$.
  • The greedy-routing bound is tight: for $\alpha\geq 2$ the high-probability hop count is $\Theta(\log n)$, and for $\alpha\leq 2$ it is $\Theta(\alpha\sqrt{\log^2 n})$, so the earlier lattice analysis left no slack in the expected case either.
  • The diameter is $\Theta(\log n/\log\log n)$ for $\alpha>2$, meaning the highway subgraph is navigable almost as quickly as its diameter allows, while for $\alpha\leq 2$ the distance to the highway becomes the bottleneck.
  • Practitioners can set the clustering exponent by measuring a network's growth dimensionality; on the 50 U.S. state road networks and DC this choice outperforms the universal lattice value $2$.
  • The estimated dimensionality $\alpha$, not the network size, is the better predictor of the empirically optimal clustering exponent, contradicting the size-based conjecture from prior work.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • One testable extension: the shell technique should also yield bounds when dimensionality varies by radius or location, since the paper's proofs use only local shell counts; this is the paper's own stated future direction, not a result of this paper.
  • A direct validation of the empirical claim would be to measure shell highway counts at many radii on real road networks and compare them with the $\Theta(b^{\alpha-1}\log n)$ prediction, which the paper does not report.
  • If the fixed-growth model transfers to other spatial networks such as flight or neural graphs, the same recipe, estimate $\alpha$ and set the clustering exponent to $\alpha$, would give an immediate routing prescription, but that transfer is untested.
  • The threshold at $\alpha=2$ in Theorem 2 is a crisp prediction: synthetic fixed-growth graphs just above and below $\alpha=2$ should show a hop-count switch from $O(\log n)$ to $O((\log n)^{2/\alpha})$, an experiment that would separate the model's substance from its proof artifacts.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 4 minor

Summary. The paper generalizes the randomized highway model of Gila, Ozel, and Goodrich from lattices to 'fixed-growth graphs' of dimensionality alpha, in which every ball of radius ell contains Theta(ell^alpha) nodes with family-wide constants. It claims tight Theta(log n) bounds on greedy routing and diameter (Theorems 1-3) when the highway constant k = Theta(log n), including high-probability results, and it presents experiments on all 50 U.S. state road networks plus DC arguing that the optimal clustering exponent is better predicted by the estimated dimensionality alpha than by the lattice value 2 or by network size. The theoretical analysis is built on shell-size bounds (Lemma 2), normalization-constant bounds (Lemma 3), and fresh-node arguments (Lemmas 7-8).

Significance. If the theorems were established, the paper would provide a clean, tight extension of Kleinberg-style greedy routing to a broad class of growth-restricted graphs with possibly non-integral dimensionality, including high-probability routing and diameter bounds; the empirical comparison across 50 states and DC, with released code, is a valuable addition. However, the key lemma underpinning the proofs is not a consequence of the fixed-growth definition, so the theoretical contribution is not presently established; the empirical findings must then be read as a heuristic study rather than as a validation of the model.

major comments (4)
  1. [Section 3.1, Lemma 2] The shell-size bound is not justified by the fixed-growth definition. From |B_ell(u)| = Theta(ell^alpha) with family-wide constants c1 and c2, the shell S_b^{(w)}(u) has at least c1((b+1)w)^alpha - c2(bw)^alpha nodes, which is non-positive for b = 1 whenever c2/c1 >= 2^alpha; the definition permits such constants. The proof's statement that shell widths are chosen so that 'the constants in this theta notation are the same' is not an operation the construction can perform, because c1 and c2 are fixed by the graph family and not by the choice of w. Consequently, Lemma 2's Theta(b^{alpha-1} log n) highway-node shell bound is unproven, and Lemma 3, Lemma 7, Lemma 8, and Theorems 1-3, all of which rely on this shell count, do not follow.
  2. [Section 3.3, Theorem 2 proof] The lower-bound half of Theorem 2 for alpha >= 2 assumes z(u) = Theta(1), justified in the text as 'we assume generously.' This is not supported by Lemma 3.1, which only gives z(u) = O(log n/k + log log n) = O(log log n) with high probability when k = Theta(log n). Under that bound, Corollary 1 yields Pr(x >= c) = O(z(u) c^{-alpha}) rather than O(c^{-alpha}); the integral used to bound E[log x] then evaluates to O(log log n), not O(1). The Chernoff argument therefore cannot produce the claimed Omega(log n) lower bound on the number of highway hops, and the tight high-probability bound for alpha >= 2 is not established.
  3. [Section 3.1, Lemma 4 proof] The condition stated for the limit to vanish, log ell + c'_1 ell^alpha/(k-1) = O(log n), is not sufficient. The expression to be shown to diverge is log c2 + log n - alpha log ell - c'_1 ell^alpha/(k-1); for this to tend to infinity one needs alpha log ell + c'_1 ell^alpha/(k-1) <= (1 - epsilon) log n for some epsilon > 0. For ell = c (k log n)^{1/alpha}, this requires choosing c with c_1 c^alpha < 1, a choice the proof neither states nor justifies. The lemma may be repairable, but as written the lower bound Theta(alpha-root(k log n)) on the distance to the nearest highway is not proven.
  4. [Section 4 and Appendix C] The empirical evaluation is in-sample: the dimensionality alpha is estimated from each state's road network, and the same network is used to measure greedy routing performance and to determine the empirically optimal clustering exponent s; no held-out validation or cross-validation is reported, and no statistical significance is given for the correlations in Figures 4 and 5. Because Section 4 itself notes that for finite graphs the fixed-growth constants can be chosen to make any dimensionality alpha work, the estimated alpha is a heuristic curve-fit rather than an established intrinsic parameter, so the causal claim that dimensionality predicts the optimal clustering exponent is not supported.
minor comments (4)
  1. [Section 3.1, Shells paragraph] The text reads 'we have have no guarantees'; this is a typo for 'we have no guarantees.'
  2. [Section 3.1, Lemma 4 proof] The sentence 'The probability that all balls contain at least one highway node is at most 1 - e^{-...} by a union bound' is not a union bound; it should be a product bound over independent balls, and the leading '1 -' is inconsistent with the subsequent paragraph, which correctly works with e^{-...}.
  3. [Theorem 2 statement] The notation Theta(alpha-root(log^2 n)) is ambiguous; it should be written as (log n)^{2/alpha} or as Theta((log n)^{2/alpha}) to avoid confusion about the order of the root and the logarithm.
  4. [Appendix C, Dimensionality estimation] The description of the estimator would benefit from specifying exactly how the ratio c2/c1 is computed from the sampled balls and how the per-node alpha values are aggregated into the reported median; the current description is underspecified regarding the number of samples and the minimization procedure.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: theoretical results derive from inputs, and the in-sample empirical alpha comparison is a validation limitation, not a circular reduction.

full rationale

The central theoretical derivation is self-contained: Theorems 1-3 take alpha and k as inputs and derive ball sizes, shell counts, normalization constants, highway distance, and routing/diameter bounds from the fixed-growth definition and Chernoff bounds. No equation in the derivation chain is defined in terms of the quantity it purports to prove, and the target hop counts are not used as assumptions. The self-citations to [21] and [22] import the highway model, the canonical k = Theta(log n) setting, and experimental methodology from prior work by overlapping authors; these are external results rather than definitions of the present paper's target claims. The one point where a proof step is delegated to self-citation, Lemma 7's statement that "This probability is identical to that used in [21], and the rest of the proof follows for values of k in Omega(log n)", is an omitted proof but not a circular dependency, because [21] is an independent prior derivation and the present paper does not cite itself to define its own conclusion. The empirical section estimates alpha from road-network ball growth and then compares s = alpha with an empirically fitted optimal s on the same states; this is in-sample and, as the paper itself admits, "our definition of 'fixed-growth' graphs is not directly meaningful for finite graphs", making the finite-graph alpha a heuristic rather than a validated model parameter. However, alpha is not constructed from routing performance, and the reported advantage of s = alpha over s = 2 is an empirical outcome rather than a tautology. The invalid shell-size cancellation in Lemma 2 and the z(u) = Theta(1) assumption in Theorem 2 are correctness risks, not circularity.

Assumptions & free parameters 4 free parameters · 6 assumptions · 0 invented entities

The central results depend on the fixed-growth ball-growth assumption, the highway model, and, for the high-probability theorem, an additional closest-to-highway information assumption. The empirical claims add a heuristic dimensionality estimator whose validity is not established. No new physical or computational entities beyond the highway model from [21] are introduced.

free parameters (4)
  • dimensionality alpha = estimated per U.S. state, reported between 1 and 2
    Estimated by minimizing the ratio c2/c1 of ball-growth bounds over sampled nodes and radii; used directly as the clustering exponent s in the empirical routing comparison (Section 4, Appendix C).
  • highway constant k = Theta(log n), with k=log n used in experiments
    Choice of highway density parameter from [21], not fitted; all bounds depend on it, and the exact constant is unspecified.
  • ball-growth constants c1, c2 = unspecified; ratio c2/c1 minimized when estimating alpha
    The fixed-growth definition hides these constants; the paper admits any finite graph can fit any alpha by choosing them, so the estimated dimensionality depends on this hidden choice (Section 4).
  • empirically optimal clustering exponent s_opt = varies per state, measured with +-0.05 error
    Used as the target in Figure 4 to show correlation with alpha; fitted by hundreds of thousands of greedy routing experiments per state (Appendix C).
assumptions (6)
  • ad hoc to paper Fixed-growth ball condition: for all nodes u and all 1 <= l <= Theta(n^{1/alpha}), |B_l(u)| = Theta(l^alpha) with constants uniform over the graph family and independent of n.
    This is the paper's central modeling assumption, introduced in Section 2; it is stricter than bounded growth because of the lower bound.
  • domain assumption Each node independently becomes a highway node with probability 1/k, and each highway node adds Theta(k) directed long-range contacts chosen with probability proportional to d(u,v)^{-alpha}.
    Generalized randomized highway model from [21]; all routing and diameter results operate on this random graph model (Sections 2.1, 3).
  • domain assumption Long-range contacts point only from highway nodes to highway nodes, and edges are directed.
    Adopted from [21] to simplify independence arguments; not justified by real networks.
  • standard math The Chernoff bounds of Dillencourt and Goodrich [12] apply to highway-node counts in balls and shells.
    Used throughout Lemmas 1-4 to convert expected counts into high-probability bounds.
  • ad hoc to paper Each non-highway node knows which neighbor is closest to the highway, enabling shortest-path descent to the highway.
    Added in Section 3.3 only for the high-probability routing theorem; not part of the baseline greedy model and not implemented in the experiments.
  • ad hoc to paper The heuristic of minimizing the ratio c2/c1 over sampled balls yields a meaningful estimate of alpha for finite road networks.
    Introduced in Appendix C; the paper concedes fixed-growth dimensionality is not directly meaningful for finite graphs, so this estimator is unvalidated.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Fast Geographic Routing in Fixed-Growth Graphs." pith.science (2026). https://pith.science/paper/HP4XBJF2

@misc{pith2026250203663,
  author       = {Pith},
  title        = {Pith review of: Fast Geographic Routing in Fixed-Growth Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HP4XBJF2}},
  note         = {Machine review of arXiv:2502.03663}
}
abstract

In the 1960s, the social scientist Stanley Milgram performed his famous "small-world" experiments where he found that people in the US who are far apart geographically are nevertheless connected by remarkably short chains of acquaintances. Since then, there has been considerable work to design networks that accurately model the phenomenon that Milgram observed. One well-known approach was Barab{\'a}si and Albert's preferential attachment model, which has small diameter yet lacks an algorithm that can efficiently find those short connections between nodes. Jon Kleinberg, in contrast, proposed a small-world graph formed from an $n \times n$ lattice that guarantees that greedy routing can navigate between any two nodes in $\mathcal{O}(\log^2 n)$ time with high probability. Further work by Goodrich and Ozel and by Gila, Goodrich, and Ozel present a hybrid technique that combines elements from these previous approaches to improve greedy routing time to $\mathcal{O}(\log n)$ hops. These are important theoretical results, but we believe that their reliance on the square lattice limits their application in the real world. In this work, we generalize the model of Gila, Ozel, and Goodrich to any class of what we call fixed-growth graphs of dimensionality $\alpha$, a subset of bounded-growth graphs introduced in several prior papers. We prove tight bounds for greedy routing and diameter in these graphs, both in expectation and with high probability. We then apply our model to the U.S. road network to show that by modeling the network as a fixed-growth graph rather than as a lattice, we are able to improve greedy routing performance over all 50 states. We also show empirically that the optimal clustering exponent for the U.S. road network is much better modeled by the dimensionality of the network $\alpha$ than by the network's size, as was conjectured in a previous work.

Figures

Figures reproduced from arXiv: 2502.03663 by the authors.

Figure 1
Figure 1. In these figures we show balls of various widths surrounding some central [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. A visualization of the two sets S and T. S is the set of highway nodes that can be efficiently reached from the source s, while T is the set of highway nodes that can efficiently reach the destination t. We show that these two sets intersect with high probability, and thus s can route to t efficiently. to n η H/(nz(u)) ≥ n η−1/(kz(u)). The probability that v is not a member of ψf is therefore at most 1 − n η−1/(kz(u… view at source ↗
Figure 3
Figure 3. Here we compare the average greedy routing performance of randomized [PITH_FULL_IMAGE:figures/full_fig_p015_3.png] view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: Here we compare our estimated dimensionality [PITH_FULL_IMAGE:figures/full_fig_p016_4.png]
Figure 5
Figure 5. Figure 5: A comparison between the dimensionality α (left) and the number of nodes n (right) as indicators for the optimal clustering coefficient s. It is clear that the dimensionality α is a much better indicator than the network size [PITH_FULL_IMAGE:figures/full_fig_p026_5.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

52 extracted references · 42 canonical work pages

  1. [1]

    In: 26th IEEE International Conference on Distributed Computing Systems (ICDCS’06)

    Abraham, I., Gavoille, C., Goldberg, A., Malkhi, D.: Routing in networks with low doubling dimension. In: 26th IEEE International Conference on Distributed Computing Systems (ICDCS’06). pp. 75–75 (2006). https://doi.org/10.1109/ ICDCS.2006.72

    work page 2006

  2. [2]

    In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms

    Abraham,I.,Fiat,A.,Goldberg,A.V.,Werneck,R.F.:Highwaydimension,shortest paths, and provably efficient algorithms. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms. p. 782–793. SODA ’10, Society for Industrial and Applied Mathematics, USA (2010)

    work page 2010

  3. [3]

    In: Proceedings of the Seventeenth Annual ACM Symposium on Parallelism in Algorithms and Architectures

    Abraham, I., Malkhi, D.: Name independent routing for growth bounded networks. In: Proceedings of the Seventeenth Annual ACM Symposium on Parallelism in Algorithms and Architectures. p. 49–55. SPAA ’05, Association for Computing Machinery, New York, NY, USA (2005). https://doi.org/10.1145/1073970.1073978

    work page arXiv 2005

  4. [4]

    Science 286(5439), 509–512 (1999)

    Barabási, A.L., Albert, R.: Emergence of scaling in random networks. Science 286(5439), 509–512 (1999). https://doi.org/10.1126/science.286.5439.509

    doi:10.1126/science.286.5439.509 1999

  5. [5]

    In: Welch, J

    Barriére, L., Fraigniaud, P., Kranakis, E., Krizanc, D.: Efficient routing in networks with long range contacts. In: Welch, J. (ed.) Distributed Computing. pp. 270–284. Springer Berlin Heidelberg, Berlin, Heidelberg (2001). https://doi.org/10.1007/ 3-540-45414-4_19

    work page 2001

  6. [6]

    Journal of Algorithms 55(2), 192–202 (2005)

    Bartal, Y., Mendel, M.: Randomized k-server algorithms for growth-rate bounded graphs. Journal of Algorithms 55(2), 192–202 (2005). https://doi.org/10.1016/j. jalgor.2004.06.002

    doi:10.1016/j 2005

  7. [7]

    Physics Reports499(1), 1–101 (2011)

    Barthélemy, M.: Spatial networks. Physics Reports499(1), 1–101 (2011). https: //doi.org/10.1016/j.physrep.2010.11.002

    doi:10.1016/j.physrep.2010.11.002 2011

  8. [8]

    Blum,J.,Funke,S.,Storandt,S.:Sublinearsearchspacesforshortestpathplanning in grid and road networks. In: Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence and Thirtieth Innovative Applications of Artificial Intelligence Conference and Eighth AAAI Symposium on Educational Advances in Artificial Intelligence. AAAI’18/IAAI’18/EAAI’1...

    work page 2018

Show all 52 references
  1. [9]

    ACM Trans

    Chan, T.H.H., Gupta, A., Maggs, B.M., Zhou, S.: On hierarchical routing in doubling metrics. ACM Trans. Algorithms12(4) (Aug 2016). https://doi.org/10. 1145/2915183

    2016

  2. [10]

    In: Proceedings of the Thirty-Eighth Annual ACM Sympo- sium on Theory of Computing

    Cole, R., Gottlieb, L.A.: Searching dynamic point sets in spaces with bounded doubling dimension. In: Proceedings of the Thirty-Eighth Annual ACM Sympo- sium on Theory of Computing. p. 574–583. STOC ’06, Association for Computing Machinery, New York, NY, USA (2006). https://do...

    2006

  3. [11]

    Dibbelt, J., Strasser, B., Wagner, D.: Customizable contraction hierarchies. ACM J. Exp. Algorithmics21 (Apr 2016). https://doi.org/10.1145/2886843

    2016 doi

  4. [12]

    Information Processing Letters182, 106397 (2023)

    Dillencourt, M., Goodrich, M.T.: Simplified chernoff bounds with powers-of-two probabilities. Information Processing Letters182, 106397 (2023). https://doi.org/ 10.1016/j.ipl.2023.106397

    2023

  5. [13]

    Journal of Statistical Physics139, 72–107 (2010)

    Dommers, S., Van Der Hofstad, R., Hooghiemstra, G.: Diameters in preferential attachment models. Journal of Statistical Physics139, 72–107 (2010). https://doi. org/10.1007/s10955-010-9921-z

    2010 doi

  6. [14]

    https: //doi.org/10.1016/j.tcs.2005.12.008, complex Networks

    Duchon, P., Hanusse, N., Lebhar, E., Schabanel, N.: Could any graph be turned into a small-world? Theoretical Computer Science355(1), 96–103 (2006). https: //doi.org/10.1016/j.tcs.2005.12.008, complex Networks

    2006 doi

  7. [15]

    Mathematika 12(2), 118–122 (1965)

    Erdös, P., Harary, F., Tutte, W.T.: On the dimension of a graph. Mathematika 12(2), 118–122 (1965). https://doi.org/10.1112/S0025579300005222 Fast Geographic Routing in Fixed-Growth Graphs 17

    1965 doi

  8. [16]

    Advances in Physics 60(3), 329–412 (2011)

    da Fontoura Costa, L., Jr., O.N.O., Travieso, G., Rodrigues, F.A., Boas, P.R.V., Antiqueira, L., Viana, M.P., Rocha, L.E.C.: Analyzing and modeling real-world phenomena with complex networks: a survey of applications. Advances in Physics 60(3), 329–412 (2011). https://doi.org/...

    2011

  9. [17]

    In: Brodal, G.S., Leonardi, S

    Fraigniaud, P.: Greedy routing in tree-decomposed graphs. In: Brodal, G.S., Leonardi, S. (eds.) Algorithms – ESA 2005. pp. 791–802. Springer Berlin Heidelberg, Berlin, Heidelberg (2005). https://doi.org/10.1007/11561071_70

    2005 doi

  10. [18]

    In: Elbassioni, K., Makino, K

    Funke, S., Storandt, S.: Provable efficiency of contraction hierarchies with randomized preprocessing. In: Elbassioni, K., Makino, K. (eds.) Algorithms and Computation. pp. 479–490. Springer Berlin Heidelberg, Berlin, Heidelberg (2015)

    2015

  11. [19]

    Transportation Science 46(3), 388–404 (2012)

    Geisberger, R., Sanders, P., Schultes, D., Vetter, C.: Exact routing in large road networks using contraction hierarchies. Transportation Science 46(3), 388–404 (2012). https://doi.org/10.1287/trsc.1110.0401

    2012 arXiv

  12. [21]

    In: Combinatorial Optimization and Applications: 16th International Conference, COCOA 2023, Hawaii, HI, USA, December 15–17, 2023, Proceedings, Part II

    Gila, O., Ozel, E., Goodrich, M.: Highway preferential attachment models for geographic routing. In: Combinatorial Optimization and Applications: 16th International Conference, COCOA 2023, Hawaii, HI, USA, December 15–17, 2023, Proceedings, Part II. pp. 56–80. Springer-Verlag,...

    2023 doi

  13. [22]

    In: Proceedings of the 30th International Conference on Advances in Geographic Information Systems

    Goodrich, M.T., Ozel, E.: Modeling the small-world phenomenon with road networks. In: Proceedings of the 30th International Conference on Advances in Geographic Information Systems. SIGSPATIAL ’22, Association for Computing Machinery, New York, NY, USA (2022). https://doi.org/...

    2022

  14. [23]

    In: 44th Annual IEEE Symposium on Foundations of Computer Science, 2003

    Gupta, A., Krauthgamer, R., Lee, J.: Bounded geometries, fractals, and low- distortion embeddings. In: 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. pp. 534–543 (2003). https://doi.org/10. 1109/SFCS.2003.1238226

    2003 arXiv

  15. [24]

    In: Twelfth IEEE International Workshop on Quality of Service, 2004

    Hui, K., Lui, J., Yau, D.: Small world overlay p2p networks. In: Twelfth IEEE International Workshop on Quality of Service, 2004. IWQOS 2004. pp. 201–210 (2004). https://doi.org/10.1109/IWQOS.2004.1309383

    2004 arXiv

  16. [25]

    In: Proceedings of the Thiry-Fourth Annual ACM Symposium on Theory of Computing

    Karger, D.R., Ruhl, M.: Finding nearest neighbors in growth-restricted metrics. In: Proceedings of the Thiry-Fourth Annual ACM Symposium on Theory of Computing. pp. 741–750. STOC ’02, Association for Computing Machinery, New York, NY, USA (2002). https://doi.org/10.1145/509907.510013

    2002

  17. [26]

    In: The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002

    Kempe, D., Kleinberg, J.: Protocols and impossibility results for gossip-based com- munication mechanisms. In: The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings. pp. 471–480 (2002). https://doi.org/10. 1109/SFCS.2002.1181971

    2002 arXiv

  18. [27]

    Kempe, D., Kleinberg, J., Demers, A.: Spatial gossip and resource location protocols. J. ACM 51(6), 943–967 (Nov 2004). https://doi.org/10.1145/1039488. 1039491

    2004 doi

  19. [28]

    In: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing

    Kleinberg, J.: The small-world phenomenon: an algorithmic perspective. In: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing. pp. 163–170. STOC ’00, Association for Computing Machinery, New York, NY, USA (2000). https://doi.org/10.1145/335305.335325 ...

    2000

  20. [29]

    In: Proceedingsofthe14thInternationalConferenceonNeuralInformationProcessing Systems: Natural and Synthetic

    Kleinberg, J.: Small-world phenomena and the dynamics of information. In: Proceedingsofthe14thInternationalConferenceonNeuralInformationProcessing Systems: Natural and Synthetic. p. 431–438. NIPS’01, MIT Press, Cambridge, MA, USA (2001)

    2001

  21. [30]

    Kochen, M., Pool, I.d.S., Milgram, S., Newcomb, T.M.: The small world (1989)

    1989

  22. [31]

    In: Proceedings of the 22nd International Symposium on Distributed Computing

    Konjevod, G., Richa, A.W., Xia, D.: Dynamic routing and location services in metrics of low doubling dimension. In: Proceedings of the 22nd International Symposium on Distributed Computing. p. 379–393. DISC ’08, Springer-Verlag, Berlin, Heidelberg (2008). https://doi.org/10.10...

    2008 doi

  23. [32]

    In: Proceedings of the Twenty-Sixth Annual ACM Symposium on Principles of Distributed Computing

    Konjevod, G., Richa, A.W., Xia, D., Yu, H.: Compact routing with slack in low doubling dimension. In: Proceedings of the Twenty-Sixth Annual ACM Symposium on Principles of Distributed Computing. p. 71–80. PODC ’07, Association for Computing Machinery, New York, NY, USA (2007)....

    2007

  24. [33]

    In: Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing

    Krauthgamer, R., Lee, J.R.: The intrinsic dimensionality of graphs. In: Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing. p. 438–447. STOC ’03, Association for Computing Machinery, New York, NY, USA (2003). https://doi.org/10.1145/780542.780607

    2003

  25. [34]

    In: Proceedings of the Twenty-Fourth Annual ACM Symposium on Principles of Distributed Computing

    Kuhn, F., Moscibroda, T., Wattenhofer, R.: On the locality of bounded growth. In: Proceedings of the Twenty-Fourth Annual ACM Symposium on Principles of Distributed Computing. p. 60–68. PODC ’05, Association for Computing Machinery, New York, NY, USA (2005). https://doi.org/10...

    2005

  26. [35]

    Chaos, Solitons & Fractals 151, 111294 (2021)

    Li, H.J., Xu, W., Song, S., Wang, W.X., Perc, M.: The dynamics of epidemic spreading on signed networks. Chaos, Solitons & Fractals 151, 111294 (2021). https://doi.org/10.1016/j.chaos.2021.111294

    2021

  27. [36]

    Handbook on Theoretical and Algorithmic Aspects of Sensor, Ad Hoc Wireless, and Peer-to- Peer Networks (08 2005)

    Li, X., Wu, J.: Searching techniques in peer-to-peer networks. Handbook on Theoretical and Algorithmic Aspects of Sensor, Ad Hoc Wireless, and Peer-to- Peer Networks (08 2005). https://doi.org/10.1201/9780203323687.ch37

    2005 doi

  28. [37]

    In: Proceedings of the Twenty-First Annual Symposium on Principles of Distributed Computing

    Malkhi, D., Naor, M., Ratajczak, D.: Viceroy: a scalable and dynamic emulation of the butterfly. In: Proceedings of the Twenty-First Annual Symposium on Principles of Distributed Computing. p. 183–192. PODC ’02, Association for Computing Machinery, New York, NY, USA (2002). ht...

    2002

  29. [38]

    In: Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing

    Martel, C., Nguyen, V.: Analyzing kleinberg’s (and other) small-world models. In: Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing. p. 179–188. PODC ’04, Association for Computing Machinery, New York, NY, USA (2004). https://doi.org/1...

    2004

  30. [39]

    Psychology today2(1), 60–67 (1967)

    Milgram, S.: The small world problem. Psychology today2(1), 60–67 (1967)

    1967

  31. [40]

    Springer Publishing Company, Incorporated, 1st edn

    Rosenberg, E.: A Survey of Fractal Dimensions of Networks. Springer Publishing Company, Incorporated, 1st edn. (2018)

    2018

  32. [41]

    Physica A: Statistical Mechanics and its Applications 325(1), 1–8 (2003)

    Sander, L., Warren, C., Sokolov, I.: Epidemics, disorder, and percolation. Physica A: Statistical Mechanics and its Applications 325(1), 1–8 (2003). https://doi. org/10.1016/S0378-4371(03)00176-6, stochastic Systems: From Randomness to Complexity

    2003 doi

  33. [42]

    In: Proceedings of the 2nd ACM Symposium on Cloud Computing

    Shin, J.Y., Wong, B., Sirer, E.G.: Small-world datacenters. In: Proceedings of the 2nd ACM Symposium on Cloud Computing. SOCC ’11, Association for Computing Machinery, New York, NY, USA (2011). https://doi.org/10.1145/2038916.2038918

    2011

  34. [43]

    In: 9th USENIX Symposium on Networked Systems Design and Implementation (NSDI 12)

    Singla, A., Hong, C.Y., Popa, L., Godfrey, P.B.: Jellyfish: Networking data centers randomly. In: 9th USENIX Symposium on Networked Systems Design and Implementation (NSDI 12). pp. 225–238. USENIX Association, San Jose, CA (Apr 2012), https://www.usenix.org/conference/nsdi12/t...

    2012

  35. [44]

    Social networks1(1), 5–51 (1978)

    de Sola Pool, I., Kochen, M.: Contacts and influence. Social networks1(1), 5–51 (1978)

    1978

  36. [45]

    ACM Trans

    Sun, Q., Lin, K., Si, C., Xu, Y., Li, S., Gope, P.: A secure and anonymous communicate scheme over the internet of things. ACM Trans. Sen. Netw.18(3) (Apr 2022). https://doi.org/10.1145/3508392

    2022 doi

  37. [46]

    In: Social networks, pp

    Travers, J., Milgram, S.: An experimental study of the small world problem. In: Social networks, pp. 179–197. Elsevier (1977)

    1977

  38. [47]

    https://doi.org/10.48550/arXiv.cond-mat/0106450

    Warren, C.P., Sander, L.M., Sokolov, I.M.: Firewalls, disorder, and percolation in epidemics (2001). https://doi.org/10.48550/arXiv.cond-mat/0106450

    2001 doi arXiv

  39. [48]

    nature 393(6684), 440–442 (1998)

    Watts, D.J., Strogatz, S.H.: Collective dynamics of ‘small-world’ networks. nature 393(6684), 440–442 (1998)

    1998

  40. [49]

    local” connections to adjacent nodes as well as “long-range

    Zhang, H., Goel, A., Govindan, R.: Using the small-world model to improve freenet performance. In: Proceedings.Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies. vol. 3, pp. 1228–1237 vol.3 (2002). https: //doi.org/10.1109/INFCOM.2002.10193...

    2002 arXiv

  41. [50]

    available

    Consider all nodes inG as “available”

  42. [51]

    unavailable

    Pick an arbitrary available node u and mark all nodes in B2ℓ(u) as “unavailable”

  43. [52]

    Add u to the set of ball centers

  44. [53]

    Repeat steps 2 and 3 until all nodes are marked as unavailable. In step 2 we mark Θ(ℓα) nodes as unavailable, allowing our procedure to repeat Θ n ℓα times,pickinganewballcentereachtime.Ballsofradius ℓcentered around each center must be independent since they are at least2ℓ ap...

Pith tools

Reviewed August 9, 2026 · model on record in the stance chip above.