Navigating Small-World Networks with Distance Predictions
arXiv:2609.10885v1 [cs.DC] 9 Sep 2026
Ladan Kian, Ming Ming Tan, and Dariusz Kowalski Augusta University, Augusta, GA, USA [email protected] [email protected] [email protected]
Abstract. The small-world phenomenon was given an algorithmic foundation by Kleinberg, who showed that in an augmented k-dimensional lattice a decentralized greedy algorithm delivers a message in O(log2 n) expected steps. We study predicted-greedy routing, in which a mobile agent forwarding the message moves at each step to the neighbor minimizing a noisy (ε, δ)-prediction of its distance to the target, redrawn at every step from an oracle conditioned on the full routing history. Two cases arise from what this agent can observe. An agent with the coordinate awareness can still compute lattice distance exactly, but not graph distance in the shortcut-augmented network, since that depends on the shortcuts of nodes it has not yet visited; given an (ε, δ)-prediction of graph distance, information the classical model never supplies, it achieves expected delivery time O(log n/(1 − 4kεδ)), an asymptotic improvement over Θ(log2 n). An agent with no coordinate awareness at all, the natural model for a privacy-preserving network whose nodes never disclose their coordinates, cannot compute even lattice distance; given an (ε, δ)-prediction of lattice distance instead, it still reaches the target in O(n/(1 − 4kεδ)) expected steps. Together these results show that a modest amount of predicted information, of the right kind, is enough to accelerate decentralized routing well below Kleinberg’s classical bound, and that even when nodes reveal no coordinates at all, reliable delivery remains achievable. Keywords: Small-world Networks · Greedy Routing · Distributed Algorithms · Predictions
1
Introduction
The small-world phenomenon, the empirical observation that arbitrary pairs of individuals in large social networks are connected by surprisingly short chains of acquaintances, was first documented by Milgram’s letter-forwarding experiments [31] and given a network-theoretic foundation by Watts and Strogatz [32], who showed that superimposing a small number of long-range random links, shortcuts, onto a highly clustered lattice produces graphs with both high clustering and small diameter. Kleinberg [17, 18] observed that low diameter alone does not explain Milgram’s experiment: what is striking is that individuals, using only local
2
L. Kian et al.
information, are collectively able to find these short paths. Kleinberg formalized this as a decentralized routing problem and introduced the augmented-lattice model that underlies our topology, in which each node of a k-dimensional grid keeps its local lattice links and additionally draws a single long-range shortcut with probability proportional to r(u, w)−k , the lattice distance raised to the −k power. Kleinberg showed that a simple decentralized greedy algorithm, always advancing to the neighbor of smallest known distance to the target, attains delivery time O(log2 n) precisely when the shortcut exponent is tuned to the lattice dimension, and that no decentralized algorithm can do so for any other exponent [17, 19]. Martel and Nguyen [24] subsequently showed this O(log2 n) bound is in fact tight, Θ(log2 n), and that the graph’s expected diameter is a full log n factor smaller, Θ(log n): a message exists along an O(log n)-length path, but no decentralized greedy crawler operating on exact local distances alone can find it, only a path log n times longer. Throughout this classical literature, the distance information available at each node, whether lattice distance to a query target or the identity of a node’s own shortcut, is assumed to be known exactly. This is a strong and, for many of the systems that motivate small-world models, an unrealistic assumption. A decentralized system that routes social-network queries, peer-to-peer lookups, or mobile-agent search rarely has access to ground truth: what it has is a prediction, learned from prior traffic, cached from an earlier crawl, inferred from partial signals, or supplied by an external oracle, none of which is guaranteed correct. This motivates asking a question the classical analysis of Kleinberg’s model does not answer: how much does a small-world network’s navigability degrade when the information driving greedy routing is imperfect, and whether the degradation can be controlled as a clean function of the estimate’s error. We answer this question for two natural notions of imperfect distance information available to a decentralized crawler. We answer this question inside the algorithms with predictions paradigm [25], in which a classical algorithm is augmented with an untrusted, error-parameterized oracle and analyzed as a function of the oracle’s error, interpolating between worst-case and oracle-optimal performance. Concretely, we equip the crawler with a prediction oracle that, at every step, returns for each candidate neighbor an estimate of its distance to the target, guaranteed only to be correct in order with probability at least 1 − ε between any two neighbors, and correct in magnitude up to an additive error δ. Crucially, the oracle is queried fresh at every step, conditioned on the crawler’s entire history so far, including any previous visit to the same node: a stronger, more honest requirement than assuming the predictions are fixed once before routing begins, and one that turns out to be exactly what is needed to keep the analysis well behaved. A navigation query, in our setting as in Kleinberg’s, is executed by a single mobile agent, the crawler, that moves one hop at a time and is not trusted to write to, or persistently remember information about, the nodes it visits: only to read a bounded amount of locally available information at its current position. What the crawler can read, however, is not fixed by the topology
Navigating Small-World Networks with Distance Predictions
3
alone, and this is where our two cases diverge. If the crawler has full coordinate awareness, it can already compute the exact lattice distance from any neighbor to the target; the only genuinely unknown quantity is the graph distance in the shortcut-augmented network, since that depends on shortcuts belonging to nodes the crawler has not yet visited. A prediction is therefore only informative here if it predicts graph distance (Case 1). If instead the crawler has no coordinate awareness at all, neither its own coordinate nor the target’s, then even lattice distance is unknown, and a prediction of lattice distance becomes the meaningful primitive (Case 2). This second setting models a privacy-preserving network in which a node’s position reflects unobserved latent attributes rather than disclosed coordinates, in the spirit of hidden-metric models of navigable networks [5]. Hiding coordinates from the crawler is a privacy guarantee for the nodes, not merely a modeling restriction; correspondingly, an untrusted oracle providing predicted lattice distance without ever exposing the underlying coordinates is a natural way to preserve that guarantee while still enabling navigation.
1.1
Our Contribution
Significance. We give the first analysis, to our knowledge, of decentralized greedy routing in a Kleinberg small-world network under the algorithms-with-predictions paradigm, in which an untrusted, error-parameterized oracle replaces exact distance information at every routing step. We study the two prediction primitives motivated above: predictions of graph distance under full coordinate awareness (Case 1), and predictions of lattice distance under no coordinate awareness (Case 2). For Case 1, predicted-greedy routing achieves expected delivery time O(log n/(1 − 4kεδ)): for any fixed error parameters with 4kεδ < 1, this is an asymptotic improvement over Kleinberg’s own Θ(log2 n) greedy bound, not merely a recovery of it in the noiseless limit, since even an imperfect graph-distance oracle carries more routing-relevant information than exact lattice distance alone: its predictions incorporate information about the effect of the unobserved shortcuts on shortest-path distances in the realized network, without necessarily identifying those shortcuts explicitly. As ε, δ → 0 the bound degrades gracefully to O(log n), matching the graph’s true expected diameter established by Martel and Nguyen [24] up to constants, so no accuracy is free-lunched: the bound simply shows that a good-enough oracle lets a decentralized crawler approach the performance of an agent with global knowledge of the network. For Case 2, we identify and resolve a robustness question: whether prediction error can cause the crawler to cycle indefinitely once it breaks the strict per-step progress that exact greedy routing enjoys for free. We show this cannot happen: because the oracle reissues a fresh, history-conditioned prediction at every step, plain greedy routing terminates in finite expected time, giving a delivery time bound linear rather than polylogarithmic in n. Section 4 explains precisely why our argument certifies only this weaker rate, and we return to whether a sharper analysis is possible in Section 5.
4
L. Kian et al.
Key ideas. Both results follow the same template: identify a one-step “excess distance” random variable measuring how far a single routing decision falls short of the best available neighbor, bound its tail probability using the oracle’s monotonicity guarantee and its magnitude using the oracle’s additive-accuracy guarantee, and telescope the resulting one-step drift into a bound on the expected hitting time via a direct additive-drift argument, without appealing to any independence assumption across steps that a revisit would violate. The two cases diverge exactly where the underlying metric diverges: graph distance is itself a shortest-path metric on the full network, so no neighbor, including the shortcut, can ever undercut the graph-optimal neighbor, giving a two-sided bound on the excess distance. Lattice distance is not a shortest-path metric once shortcuts are added, so the shortcut can outperform the best local lattice neighbor by an arbitrary amount, giving only a one-sided bound; this asymmetry is the precise reason Case 2’s rate is weaker, the analysis never needs, and therefore never benefits from, the shortcut’s power-law placement that drives Kleinberg’s original speedup.
2
Related Work
Our decentralized routing problem sits at the intersection of two lines of work: the classical analysis of Kleinberg’s augmented-lattice small-world model, and the recent algorithms-with-predictions paradigm. We discuss each in turn, then position our contribution against both. Classical small-world navigability. Kleinberg’s original result fixed the shortcut exponent to the lattice dimension and showed greedy routing achieves O(log2 n) expected delivery [17, 18], later shown tight, Θ(log2 n), by Martel and Nguyen [24], who also established the graph’s expected diameter as the strictly smaller Θ(log n), the gap our Case 1 result closes under a sufficiently accurate oracle. Martel and Nguyen further characterize small-world graphs more broadly, including geometries beyond the basic grid [27], and Kleinberg’s own survey consolidates the model and its decentralized search guarantees [20]. The diameter of the underlying shortcut percolation structure itself has been pinned down precisely as a function of the shortcut exponent [9], and later work gives exact asymptotic characterizations of navigability at and around Kleinberg’s critical exponent [8, 7]. Most recently, Alimohammadi et al. [1] use local weak convergence to characterize the Kleinberg model’s structure in the large-n limit and pin down the same critical exponent from a different, local-limit perspective, corroborating why navigability is so exponent-sensitive. All of this literature analyzes a single canonical process, greedy hops toward a target under exact distances; a different, complementary process on the same topology, the unbiased random walk, exhibits its own, distinctly located phase transition in mixing time as a function of the shortcut exponent [10], underscoring that the exponent-navigability relationship is a property of the network, not an artifact of the particular decentralized process studied. It has to be noted that small-world networks were not only used for point-
Navigating Small-World Networks with Distance Predictions
5
to-point navigability, but also for more complex communication and computation tasks, e.g., computing symmetric functions via aggregation, see e.g., [15]. Improving greedy with additional information. A substantial body of work improves on plain greedy by giving nodes more, but still perfectly reliable, local knowledge. Manku, Naor and Wieder [23] and Naor and Wieder [26] show that lookahead to a neighbor’s neighbors reduces delivery time to O(log1+1/k n) in expectation; Fraigniaud et al. [11] obtain a similar improvement via topological awareness of nearby shortcuts. Zeng et al. [33] augment each node with O(log n) bits of local awareness of nearby shortcuts to reach a near-optimal O(log n log log n) expected hop count, and Ruas [29] shows that combining a power-law contact distribution with one-hop lookahead can drive the expected number of hops down to O(1) in a one-dimensional variant of the model. This line of work asks how much more exact information a decentralized node needs to beat plain greedy, the opposite direction from ours: we ask how much routing degrades when the node’s information, even of the same scope as Kleinberg’s, is no longer exact. Giakkoupis and Schabanel [14] and Fraigniaud and Giakkoupis [12] sharpen the exponent-versus-dimension transition and extend navigability to broader underlying graph families; Fraigniaud et al. [13] generalize navigability to arbitrary doubling-dimension graphs. Geographic and geometric routing under imperfect location information. A separate, older literature studies greedy forwarding in physically embedded geometric networks, and is the closest prior work, outside the predictions paradigm, to asking what happens when a crawler’s position or distance information is not perfectly reliable. Karp and Kung’s GPSR [16] and Kranakis, Singh and Urrutia’s compass routing [21] both forward greedily by geographic or angular proximity to the destination, falling back to a perimeter- or face-traversal recovery rule when greedy forwarding reaches a local void, under the standing assumption that every node’s coordinates are exact. Seada, Helmy and Govindan [30] study exactly what happens when that assumption fails: they show that even small localization errors, as little as ten percent of radio range, can cause geographic face routing to fail non-recoverably, and quantify the resulting performance degradation empirically. This is, to our knowledge, the closest existing result in spirit to ours, imperfect position information degrading a greedy geometric routing rule, but the setting, guarantee, and error model all differ substantially from ours: it concerns a fixed, per-instance geometric embedding and empirically measured failure rates under deterministic perimeter recovery, rather than an (ε, δ)-accurate stochastic oracle re-queried at every step within Kleinberg’s shortcut-augmented lattice, and it does not provide an expected-delivery-time bound as a closed-form function of the error, which is the central object of our analysis. Hidden-metric and privacy-motivated models. Our Case 2 crawler, which observes node identifiers but no coordinates, is motivated by hidden-metric models of real navigable networks, in which a node’s position reflects latent, unobserved attributes rather than disclosed coordinates [5]. In that literature the hidden
6
L. Kian et al.
geometry is recovered statistically from the observed graph rather than supplied by an untrusted oracle at query time; our contribution is to ask what decentralized navigation looks like when the crawler is given only a noisy, per-query prediction of this hidden distance and nothing else, never the coordinates themselves, which is the privacy-preserving reading of the model motivated in Section 1. Algorithms with predictions. The algorithms-with-predictions paradigm augments a classical algorithm with an untrusted, error-parameterized oracle and analyzes performance as a function of the oracle’s error, interpolating between worst-case and oracle-optimal behavior [25]. It has been applied to online caching [22], nonclairvoyant and online scheduling [28], and contract scheduling [2], and has only very recently entered distributed and self-stabilizing computing. Boyar, Ellen and Larsen [6] initiate deterministic distributed graph algorithms with predictions in synchronous message passing, illustrated on Maximal Independent Set, where every node receives a prediction of its own output bit and predictions are evaluated against the same round-complexity measure used without predictions. Aradhya and Scheideler [3] study self-stabilizing graph linearization under untrusted advice, and Balliu et al. [4] study distributed computation with local advice more generally. None of these consider navigation: in all three, every node receives one prediction about a static, global property of the graph or its own final output, evaluated once, whereas in our setting a single mobile crawler receives a fresh, history-conditioned prediction at every step of a dynamic query, about a value, distance to a query-specific target, that is not fixed in advance and depends on which node has been asked. This distinction is exactly what let us dispense with the memory and cycle-avoidance machinery that a fixed, once-issued prediction would have required (Section 4): the dynamic, per-step, history-conditioned nature of the oracle is not an incidental modeling choice but the mechanism that makes plain greedy routing terminate with no auxiliary state at all. To the best of our knowledge, no prior work in the predictions literature considers decentralized navigation in a small-world topology, the setting of this paper.
3
Model and Preliminaries
3.1
Network Model
Fix an integer k ≥ 1, the dimension, and an integer n ≥ 2, the side length. The node set is the k-dimensional grid V = {1, . . . , n}k , N = |V | = nk ; each u ∈ V is a lattice point u = (u1 , . . . , uk ), and each node is additionally assigned a unique Pk identifier, independent of its coordinate. Let r(u, v) = j=1 |uj − vj | denote the lattice distance, following Kleinberg’s original grid formulation [18, 17]. Each node u has an undirected local link to every node at lattice distance 1; write N (u) for this set of lattice neighbors. Interior nodes satisfy |N (u)| = 2k; nodes within distance 1 of the grid boundary have fewer neighbors. There are O(nk−1 ) = O(N (k−1)/k ) such boundary-affected nodes, a vanishing fraction of N , and we follow the standard convention of treating this as a negligible edge
Navigating Small-World Networks with Distance Predictions
7
effect rather than modeling it explicitly [24]; statements below about "a node u" hold for interior nodes, which suffices with high probability for a uniformly random source or target. In addition, each node u independently creates one directed shortcut link (u, Wu ), whose endpoint Wu ̸= u is sampled with probability Pr[Wu = w] =
r(u, w)−k , Zu
Zu =
X
r(u, x)−k .
x∈V \{u}
These choices are independent across nodes and links. All shortcut links are sampled once before routing begins and remain fixed throughout the routing process. There exist constants Clo , Cup > 0, depending only on k, with Clo log n ≤ Zu ≤ Cup log n for every interior u ∈ V and all sufficiently large n [18, 24]. This is the p = q = 1, with the clustering exponent α = k specialization of Kleinberg’s construction [18], generalized to k dimensions as in [24]; α = k is the unique exponent for which a decentralized algorithm can achieve polylogarithmic expected delivery time [18], and under it, lattice greedy routing (forwarding, at each step, to the neighbor of smallest true lattice distance to the target) achieves expected delivery time Θ(log2 n), tight, with the graph’s expected diameter a further log n factor smaller, Θ(log n) [24]; expectations throughout are over the random shortcuts and over a source and target drawn uniformly at random from V . Let G = (V, E) be the resulting fixed directed graph, each undirected local adjacency represented by two opposite directed links, together with every node’s shortcut link. For u ∈ V , write N + (u) := N (u) ∪ {Wu } for its set of outgoing neighbors. We use two distinct notions of distance on G throughout the paper. The lattice distance r(u, v), defined above, ignores all shortcuts and depends only on the underlying grid; its maximum value is L = O(n) = O(N 1/k ). The graph distance ℓG (u, v) = length of a shortest directed path from u to v in G is the shortest-path distance in the full network, shortcuts included, and is finite for every u, v ∈ V since the local lattice edges alone connect the grid. Since every lattice path is in particular a path in G, ℓG (u, v) ≤ r(u, v) ≤ L for all u, v ∈ V ; the two notions coincide only when no shortcut shortens the route. Section 3.2 studies predictions of ℓG , and Section 3.3 studies predictions of r. A navigation query is an ordered pair (s, t) ∈ V × V , the source and target, executed by a single mobile agent, the crawler, initially located at s. When located at a node u = ̸ t, a routing step consists of selecting an outgoing neighbor v ∈ N + (u) and traversing the edge (u, v); we call the selection of v the routing decision of that step. The query is delivered the first time the crawler reaches t, and the delivery time T is the number of routing steps taken. What the crawler observes at each node, in particular, whether coordinates are visible, and whether the available predictions concern graph distance or lattice
8
L. Kian et al.
distance, differs between the two settings studied in this paper, and is specified separately in Section 3.2 and Section 3.3. 3.2
Case 1: Graph-Distance Predictions
In this setting the crawler has full coordinate awareness: it is given the coordinate of the target t, and, when located at a node u, it knows the coordinate of u and the identities and coordinates of every node in N + (u), including the endpoint of its shortcut link. It can therefore compute the exact lattice distance r(v, t) for every v ∈ N + (u). However, it is not given the shortcut links of nodes it has not yet visited; since these unobserved links can shorten paths to the target, the crawler does not in general know ℓG (v, t) for v ∈ N + (u). For the fixed target t of a given navigation query, write for every u ∈ V,
ht (u) := ℓG (u, t)
the true shortest directed graph distance from u to t in the realized network G. Prediction oracle. We adopt the algorithms with predictions paradigm [25]; the oracle returns an error-parameterized prediction vector at each step, formalized as follows. Index routing steps i = 0, 1, . . ., let Ui denote the crawler’s location at the start of step i (U0 = s), and let Fi denote the pre-step history, the source, the target, all nodes visited up to and including Ui , all previously issued predictions, and all previous routing decisions, excluding the prediction issued at step i itself. Definition 1 ((ε, δ)-graph-distance prediction oracle). Fix 0 ≤ ε ≤ 1 and 0 ≤ δ. A prediction oracle is an (ε, δ)-graph-distance prediction oracle if, for every realized network G, every target t, and every feasible pre-step history Fi with Ui = u = ̸ t, the oracle returns a prediction vector ĥi = (ĥi (v) : v ∈ N + (u)) satisfying: (i) Conditional pairwise monotonicity. For every v, w ∈ N + (u) with ht (v) < ht (w), Pr ĥi (w) ≤ ĥi (v) | Fi ≤ ε. (ii) Additive approximation. Conditional on Fi , with probability 1, ĥi (v) − ht (v) ≤ δ
for every v ∈ N + (u).
A new prediction vector is generated at every routing step, including a step at which Ui is a node the crawler has already visited. The oracle may choose the distribution of ĥi depending on the complete history Fi ; in particular, prediction vectors generated at different routing steps need not be independent. Definition 2 (Predicted-greedy routing). At every routing step i with Ui ̸= t, the crawler receives the prediction vector ĥi and selects an outgoing neighbor that minimizes the predicted graph distance to the target, Ui+1 ∈ arg
min
v∈N + (Ui )
ĥi (v),
Navigating Small-World Networks with Distance Predictions
9
with a fixed, arbitrary tie-breaking rule when the minimum is attained by more than one neighbor. Algorithm 1 in Appendix A gives pseudocode for this update rule, covering both Case 1 and Case 2 (Definition 4). 3.3
Case 2: Lattice-Distance Predictions
In this setting the crawler has no coordinate awareness whatsoever. Nodes are distinguished only by identifier, and, by construction (Section 3.1), an identifier reveals nothing about a node’s coordinate. When located at a node u, the crawler observes the identifier of u, the identifiers of the nodes in N + (u), which of them is the shortcut neighbor, and, for every v ∈ N + (u), a prediction of the lattice distance r(v, t); it observes neither its own coordinate, nor t’s, nor that of any neighbor. This restriction is essential to the model, not incidental to it: were coordinates observable, as in Case 1, the crawler could compute r(v, t) exactly for every v ∈ N + (u) without consulting any oracle, and a lattice-distance prediction would carry no information. Hiding coordinates is therefore what makes lattice-distance prediction a meaningful primitive here, and it is also the more realistic assumption for a social network, in which a node’s position corresponds to unobserved latent attributes (interests, communities, or other features) rather than to disclosed physical coordinates, in the spirit of hidden-metric models of navigable networks [5]. For the fixed target t of a given navigation query, we write rt (u) := r(u, t)
for everyu ∈ V,
the true lattice distance from u to the target t. Definition 3 ((ε, δ)-lattice-distance prediction oracle). Fix 0 ≤ ε ≤ 1 and 0 ≤ δ. A prediction oracle is an (ε, δ)-lattice-distance prediction oracle if, for every realized network G, every target t, and every feasible pre-step history Fi with Ui = u = ̸ t, the oracle returns a prediction vector p̂i = (p̂i (v) : v ∈ N + (u)) satisfying: (i) Conditional pairwise monotonicity. For every v, w ∈ N + (u) with rt (v) < rt (w), Pr p̂i (w) ≤ p̂i (v) | Fi ≤ ε. (ii) Additive approximation. Conditional on Fi , with probability 1, p̂i (v) − rt (v) ≤ δ
for every v ∈ N + (u).
As in Case 1, a new prediction vector is generated at every routing step, including a step at which Ui is a node the crawler has already visited. The oracle may choose the distribution of p̂i depending on the complete history Fi ; in particular, prediction vectors generated at different routing steps need not be independent.
10
L. Kian et al.
Definition 4 (Predicted-greedy routing, lattice-distance case). At every routing step i with Ui ̸= t, the crawler receives the prediction vector p̂i and selects an outgoing neighbor that minimizes the predicted lattice distance to the target, Ui+1 ∈ arg
min
v∈N + (Ui )
p̂i (v),
with the same fixed, arbitrary tie-breaking rule as in Definition 2 when the minimum is attained by more than one neighbor. Unlike the graph distance ht used in Case 1, the lattice distance rt is not itself a shortest-path metric on G: a shortcut endpoint w = Wu can satisfy rt (w) ≪ rt (u) − 1, so the true minimum minv∈N + (u) rt (v) may fall strictly below rt (u) − 1, whereas at least one lattice neighbor attains rt (u) − 1 exactly, possibly several when u and t differ in more than one coordinate, and no lattice neighbor can do better than rt (u) − 1. This asymmetry between the local neighbors, which change rt by exactly one step, and the shortcut, which may change it by an arbitrary amount, is the source of the different delivery-time argument required for this case. 3.4
Model Comparison and Oracle Information
Both settings of Case 1 and Case 2 (see subsections 3.2, 3.3) use the same k-dimensional Kleinberg topology, with nearest-neighbor lattice links and one independently sampled directed shortcut per node, fixed throughout the routing [18, 24]. The distinction is the information available to the crawler. Classical latticegreedy routing in [17, 18] uses coordinates to compute exact lattice distances. Case 1 retains this coordinate access and additionally supplies predictions of the graph distance ℓG (v, t), whereas Case 2 hides coordinates and supplies predictions of the lattice distance r(v, t). Both cases use the same memoryless rule of choosing a neighbor of minimum predicted distance. Thus, Case 1 provides information beyond the classical model, while Case 2 studies imperfect access to the lattice distances used by classical greedy routing. In particular, the graph-distance prediction oracle (Definition 1) must incorporate information about the influence of shortcuts in the realized network, including those belonging to unvisited nodes; it is not sufficient to know only their sampling distribution. Indeed, consider two shortcut realizations G and G′ that are compatible with the same complete observation history of the crawler, including its current local observations. For the same queried neighbor v and target t, suppose that |ℓG (v, t) − ℓG′ (v, t)| > 2δ. An oracle whose output distribution is determined solely by that observation history must use the same distribution in both realizations. However, the intervals [ℓG (v, t) − δ, ℓG (v, t) + δ] and [ℓG′ (v, t) − δ, ℓG′ (v, t) + δ] are disjoint, so that distribution cannot satisfy the almost-sure additive guarantee in both realizations. In such situations, knowledge of the shortcut-sampling distribution and the crawler’s observation history is insufficient: the oracle requires additional instancespecific information about the effects of unobserved shortcuts, without necessarily identifying those shortcuts explicitly. In contrast, the lattice-distance prediction
Navigating Small-World Networks with Distance Predictions
11
oracle does not require information about unobserved shortcuts since r(v, t) depends only on the underlying lattice embedding. Hence, the faster delivery time in Case 1 should be interpreted as a consequence of a stronger information model, with our analysis quantifying the dependence of the delivery-time bound on prediction error. In both cases, the oracle guarantees must hold after every feasible routing history, including revisits. The construction of such an oracle and the cost of acquiring its information is outside the scope of our analysis. 3.5
Delivery Time
The delivery time is the random variable T := min{i ≥ 0 : Ui = t},
(1)
with the convention that T = ∞ if the crawler never reaches the target. Since U0 = s and each routing step traverses exactly one link, T is the number of routing steps, equivalently the number of hops, taken to reach t. This definition applies uniformly to both cases studied below: it depends only on the routingstep process (Ui )i≥0 fixed in Section 3.1, not on which distance the crawler’s predictions concern. For a fixed graph G and fixed endpoints s, t ∈ V , we write E[T | G, s, t] for the expectation of T taken over the prediction oracle’s random outputs alone. Whenever we additionally average over the random shortcut links or over the endpoints s, t, we state this explicitly.
4
Expected Delivery Time
We analyze the delivery time of predicted-greedy routing separately for each of the two prediction models introduced in Section 3. 4.1
Case 1: Graph-Distance Predictions
One-Step Progress. Fix a realization of G, a source s, a target t, and a routing step i < T . Let Hi := ht (Ui ) denote the true graph distance remaining at the beginning of step i. Since Ui ̸= t, a shortest directed path from Ui to t begins with an outgoing neighbor. Choose any such neighbor vi∗ ∈ N + (Ui ). Then ht (vi∗ ) = Hi − 1. The choice of vi∗ is used only in the analysis; the crawler does not know vi∗ . Define the one-step excess distance by Ri := ht (Ui+1 ) − (Hi − 1). (2) Thus, Ri measures the additional graph distance incurred by the selected neighbor relative to an optimal next hop. In particular, Ri = 0 when the selected link is the first link of a shortest directed path to t.
12
L. Kian et al.
Lemma 1. For every fixed graph G, target t, and feasible pre-step history Fi ending at Ui ̸= t, Pr[Ri > 0 | Fi ] ≤ 2kε,
(3)
Pr[0 ≤ Ri ≤ 2δ | Fi ] = 1,
(4)
E[Ri | Fi ] ≤ 4kεδ.
(5)
Proof. For every outgoing neighbor w ∈ N + (Ui ), the link (Ui , w) followed by a shortest directed path from w to t gives a directed path from Ui to t. Therefore, Hi ≤ 1 + ht (w), and hence ht (w) ≥ Hi − 1. Applying this inequality to the selected neighbor Ui+1 shows that Ri ≥ 0. We first bound the probability that Ri is positive. If Ri > 0, then predictedgreedy has selected an outgoing neighbor w = Ui+1 satisfying ht (vi∗ ) < ht (w). Since Ui+1 minimizes ĥi over N + (Ui ), and vi∗ ∈ N + (Ui ), this selection necessarily satisfies ĥi (w) ≤ ĥi (vi∗ ). Hence [ {Ri > 0} ⊆ ĥi (w) ≤ ĥi (vi∗ ) . w∈N + (Ui ) ht (vi∗ )<ht (w)
The node Ui has at most 2k local outgoing neighbors and one shortcut outgoing neighbor, so |N + (Ui )| ≤ 2k + 1, and there are at most 2k possible choices of w other than vi∗ . By Definition 1(i), conditional pairwise monotonicity, each such event satisfies Pr[ĥi (w) ≤ ĥi (vi∗ ) | Fi ] ≤ ε. Taking a union bound over these at most 2k events gives Pr[Ri > 0 | Fi ] ≤ 2kε. We already established Ri ≥ 0 above. It remains to show Ri ≤ 2δ almost surely conditional on Fi . Since Ui+1 minimizes ĥi over N + (Ui ) by Definition 2, and vi∗ ∈ N + (Ui ), the inequality ĥi (Ui+1 ) ≤ ĥi (vi∗ ) holds surely, it is an immediate consequence of Ui+1 being an argmin, true for every realization of ĥi . By the additive approximation guarantee, Definition 1(ii), which holds with probability 1 conditional on Fi for every v ∈ N + (Ui ), applied first to Ui+1 and then to vi∗ , ht (Ui+1 ) ≤ ĥi (Ui+1 ) + δ ≤ ĥi (vi∗ ) + δ ≤ ht (vi∗ ) + 2δ = Hi − 1 + 2δ. By (2), this is exactly Ri ≤ 2δ, and, as a combination of a sure fact (the argmin inequality) and an almost-sure fact (the additive approximation), it holds almost surely conditional on Fi . Together with Ri ≥ 0, established above, this shows Pr[0 ≤ Ri ≤ 2δ | Fi ] = 1. Since Ri ≥ 0 always, the complement of {Ri > 0} is exactly {Ri = 0}; that is, Ri = Ri · 1{Ri > 0} surely. Taking conditional expectations and using the almost-sure bound Ri ≤ 2δ from (4) on the event {Ri > 0}, E[Ri | Fi ] = E Ri · 1{Ri > 0} | Fi ≤ 2δ Pr[Ri > 0 | Fi ].
Navigating Small-World Networks with Distance Predictions
13
By (3), Pr[Ri > 0 | Fi ] ≤ 2kε, then E[Ri | Fi ] ≤ 2δ · 2kε = 4kεδ. ⊔ ⊓ Drift Toward the Target. We now prove the following theorem. Theorem 1. Fix a graph G, a source s, and a target t. Suppose that the prediction oracle satisfies Definition 1 after every feasible pre-step history. If 4kεδ < 1, then the expected delivery time of predicted-greedy routing satisfies E[T | G, s, t] ≤
ht (s) , 1 − 4kεδ
(6)
where the expectation is over the oracle’s random outputs. Consequently, if G is drawn from the k-dimensional Kleinberg model of Section 3.1 with p = q = 1 and α = k, then, for every fixed pair s, t ∈ V , log n E[T | s, t] = O , (7) 1 − 4kεδ where the expectation in (7) is over both the random shortcut links and the oracle’s random outputs. The hidden constant depends only on k. Proof. From the definition of Ri in (2), for every step i < T , Hi+1 = Hi − 1 + Ri . Taking conditional expectations and applying Lemma 1, E[Hi − Hi+1 | Fi ] = 1 − E[Ri | Fi ] ≥ 1 − 4kεδ.
(8)
The assumption 4kεδ < 1 ensures that the right-hand side of (8) is positive, so Hi drifts downward in expectation at every step before T . We turn this drift into a bound on E[T ] via a direct additive-drift argument. Fix an integer m ≥ 1 and consider the stopped process at min{T, m}. Multiplying (8) by the indicator that step i occurs before min{T, m}, summing over i = 0, . . . , m− 1, and taking expectations gives E H0 − Hmin{T,m} | G, s, t ≥ (1 − 4kεδ) E[min{T, m} | G, s, t]. Since Hmin{T,m} ≥ 0 and H0 = ht (s), rearranging gives E[min{T, m} | G, s, t] ≤
ht (s) . 1 − 4kεδ
Letting m → ∞ and applying monotone convergence to the nondecreasing sequence min{T, m} yields (6).
14
L. Kian et al.
To obtain (7), we average (6) over the random Kleinberg graph. Martel and Nguyen showed that the expected diameter of the k-dimensional Kleinberg graph with p = q = 1 and exponent k is Θ(log n) [24]. Since ht (s) = ℓG (s, t) ≤ maxx,y∈V ℓG (x, y), h i E[ht (s)] ≤ E max ℓG (x, y) = O(log n). x,y∈V
Taking expectations in (6) over the random graph therefore gives log n E[T | s, t] = O . 1 − 4kεδ This completes the proof of Theorem 1.
⊔ ⊓
Revisiting nodes. The drift bound (8) holds conditionally after every feasible pre-step history, including histories in which the crawler has revisited one or more nodes: the argument never resamples an already exposed shortcut link, nor treats a revisit as a fresh shortcut trial, only the prediction vector ĥi is regenerated at each step, and no independence between prediction vectors at different steps is required. Since Theorem 1 gives E[T | G, s, t] < ∞ for every fixed G, s, t, it follows that Pr[T < ∞ | G, s, t] = 1; the crawler reaches the target with probability one. 4.2
Case 2: Lattice-Distance Predictions
One-Step Progress. Fix a realization of G, a source s, a target t, and a routing step i < T . Let ρi := rt (Ui ) denote the true lattice distance remaining at the beginning of step i. By the triangle inequality, every v ∈ N (Ui ) satisfies rt (v) ≥ rt (Ui ) − r(Ui , v) = ρi − 1, and at least one lattice neighbor attains this bound with equality (the neighbor moving one step toward t along any coordinate on which Ui and t differ). Choose any such neighbor vi∗ ∈ N (Ui ). Then rt (vi∗ ) = ρi − 1. As in Case 1, the choice of vi∗ is used only in the analysis. Define the one-step excess distance by ∆i := rt (Ui+1 ) − (ρi − 1).
(9)
Unlike Ri in Case 1, ∆i is not guaranteed nonnegative: the shortcut endpoint WUi may satisfy rt (WUi ) < ρi − 1, since rt is not itself a shortest-path metric on G, so selecting the shortcut can give ∆i < 0, unrequired extra progress. The lemma below therefore bounds ∆i only from above. Lemma 2. For every fixed graph G, target t, and feasible pre-step history Fi ending at Ui ̸= t, Pr[∆i > 0 | Fi ] ≤ 2kε,
(10)
Pr[∆i ≤ 2δ | Fi ] = 1,
(11)
E[∆i | Fi ] ≤ 4kεδ.
(12)
Navigating Small-World Networks with Distance Predictions
15
Proof. If ∆i > 0, then predicted-greedy has selected an outgoing neighbor w = Ui+1 satisfying rt (vi∗ ) < rt (w). Since Ui+1 minimizes p̂i over N + (Ui ), and vi∗ ∈ N + (Ui ), this selection necessarily satisfies p̂i (w) ≤ p̂i (vi∗ ). Hence [ {∆i > 0} ⊆ p̂i (w) ≤ p̂i (vi∗ ) . w∈N + (Ui ) rt (vi∗ )<rt (w)
There are at most |N + (Ui )|−1 ≤ 2k choices of w other than vi∗ . By Definition 3(i), conditional pairwise monotonicity, each such event satisfies Pr[p̂i (w) ≤ p̂i (vi∗ ) | Fi ] ≤ ε. A union bound over these at most 2k events gives Pr[∆i > 0 | Fi ] ≤ 2kε. Since Ui+1 minimizes p̂i over N + (Ui ) by Definition 4, and vi∗ ∈ N + (Ui ), the inequality p̂i (Ui+1 ) ≤ p̂i (vi∗ ) holds surely, for every realization of p̂i . By the additive approximation guarantee, Definition 3(ii), which holds with probability 1 conditional on Fi for every v ∈ N + (Ui ), applied first to Ui+1 and then to vi∗ , rt (Ui+1 ) ≤ p̂i (Ui+1 ) + δ ≤ p̂i (vi∗ ) + δ ≤ rt (vi∗ ) + 2δ = ρi − 1 + 2δ. By (9), this is exactly ∆i ≤ 2δ, and, as a combination of a sure fact and an almost-sure fact, it holds almost surely conditional on Fi , proving Pr[∆i ≤ 2δ | Fi ] = 1. Because ∆i can be negative, write E[∆i | Fi ] as the sum of its contributions from the two events {∆i > 0} and {∆i ≤ 0}: E[∆i | Fi ] = E ∆i · 1{∆i > 0} | Fi + E ∆i · 1{∆i ≤ 0} | Fi . The second term is at most 0, since ∆i ≤ 0 on that event. The first term is at most 2δ Pr[∆i > 0 | Fi ] by (11), hence at most 4kεδ by (10). Adding the two bounds gives E[∆i | Fi ] ≤ 4kεδ. ⊔ ⊓ Drift Toward the Target. We now prove the following theorem. Theorem 2. Fix a graph G, a source s, and a target t. Suppose that the prediction oracle satisfies Definition 3 after every feasible pre-step history. If 4kεδ < 1, then the expected delivery time of predicted-greedy routing satisfies E[T | G, s, t] ≤
r(s, t) , 1 − 4kεδ
(13)
where the expectation is over the oracle’s random outputs. Consequently, if G is drawn from the k-dimensional Kleinberg model of Section 3.1 with p = q = 1 and α = k, then, for every fixed pair s, t ∈ V , n N 1/k E[T | s, t] = O =O , (14) 1 − 4kεδ 1 − 4kεδ
16
L. Kian et al.
where the expectation in (14) is over the random source and target only. The hidden constant depends only on k. Proof. From the definition of ∆i in (9), for every step i < T , ρi+1 = ρi − 1 + ∆i . Taking conditional expectations and applying Lemma 2, E[ρi − ρi+1 | Fi ] = 1 − E[∆i | Fi ] ≥ 1 − 4kεδ,
(15)
positive under 4kεδ < 1. Fix m ≥ 1 and consider the stopped process at min{T, m}. Multiplying (15) by the indicator that step i occurs before min{T, m}, summing over i = 0, . . . , m − 1, and taking expectations gives E ρ0 − ρmin{T,m} | G, s, t ≥ (1 − 4kεδ) E[min{T, m} | G, s, t]. Since ρmin{T,m} ≥ 0 and ρ0 = rt (s) = r(s, t), E[min{T, m} | G, s, t] ≤
r(s, t) . 1 − 4kεδ
Letting m → ∞ and applying monotone convergence proves (13). To obtain (14), average (13) over a uniformly random pair s, t ∈ V . Unlike ht (s) in Case 1, r(s, t) does not depend on the random shortcuts, only on the grid geometry: for s, t drawn uniformly and independently, each coordinate gap Pk |sj − tj | satisfies E|sj − tj | = Θ(n), so E[r(s, t)] = j=1 E|sj − tj | = Θ(n). Taking expectations in (13) over s, t gives n . E[T | s, t] = O 1 − 4kεδ ⊔ ⊓ Revisiting nodes. As in Case 1, the drift bound established in the proof of Theorem 2 holds conditionally after every feasible pre-step history, including histories with repeated visits: only the prediction vector p̂i is regenerated at a revisited node, no shortcut link is resampled, and no independence across steps is required. Since Theorem 2 gives E[T | G, s, t] < ∞ for every fixed G, s, t, it follows that Pr[T < ∞ | G, s, t] = 1. A natural concern for lattice-distance predicted-greedy is that, unlike the exact case δ = 0 where distance decreases strictly at every step, a prediction error can cause the crawler to select a neighbor with ∆i > 0, potentially revisiting a previously seen node. Theorem 2 shows that, because the oracle reissues a fresh prediction vector p̂i at every routing step, including at a revisited node, conditioned on the complete history Fi (Definition 3), the one-step guarantee of Lemma 2 holds identically whether or not Ui has been visited before. No bound on how many times a node may be revisited is needed, and no shortcut link is ever resampled, only the prediction is redrawn. The drift argument therefore gives a finite expected delivery time, and hence almost-sure termination, using only the dynamic nature of the oracle, with no auxiliary memory or cycle-avoidance rule imposed on the crawler.
Navigating Small-World Networks with Distance Predictions
17
Remark (a stabilization guarantee). Theorem 2 is best read as a stabilization guarantee for memoryless predicted-greedy routing under a dynamic, historyconditioned prediction oracle. Prediction errors may still cause revisits, or even temporary cycles; what the dynamic oracle rules out is such an error persisting indefinitely. Because a fresh prediction vector satisfying Definition 3 is issued after every feasible routing history, including immediately after a return to a previously visited node, the positive conditional drift established in Lemma 2 is restored at every revisit, exactly as if the crawler had never been there before. This gives a finite expected delivery time and, hence, almost-sure termination, with no memory of past visits. We emphasize how demanding this assumption is: at every step the oracle may choose a new prediction distribution depending on the entire routing history so far, it may return a different prediction on a repeated visit to the same node, and the guarantees of Definition 3 must hold after every feasible history, not just at the outset. Theorem 2 should be read as showing what a sufficiently adaptive oracle can buy a memoryless crawler, not as a guarantee available from an arbitrary fixed predictor. Remark (comparison with Case 1). The averaged bound (14) is linear in n, not polylogarithmic in n like Case 1’s (7). The drift in Theorem 2 is generated entirely by the guaranteed per-step decrease of 1 from a local lattice neighbor, the same guarantee plain lattice-greedy has with no shortcuts at all; the argument never invokes the shortcut’s placement Pr[Wu = w] ∝ r(u, w)−k , so Theorem 2 and its proof are unaffected if every shortcut link is deleted from G. This explains why this particular drift argument certifies only a linear rate: it simply does not use the one ingredient, the shortcut’s power-law placement, that Kleinberg’s original phase argument exploits to obtain Θ(log2 n). It does not show that no sharper analysis of the same algorithm could do better. Indeed, when δ = 0 the oracle is exact and predicted-greedy coincides with plain lattice-distance greedy augmented with Kleinberg’s shortcuts, whose expected delivery time is Θ(log2 n) [24]; our bound (14) gives only O(n) in this same limit.
5
Conclusion
We analyzed decentralized greedy routing in Kleinberg’s small-world model under the algorithms with predictions paradigm, for two natural notions of imperfect distance information. Under graph-distance predictions (Case 1), predicted-greedy routing improves asymptotically on Kleinberg’s own Θ(log2 n) bound, up to a clean, explicit degradation factor in the prediction error. Under lattice-distance predictions (Case 2), the more realistic model when coordinates are hidden, we established a stabilization guarantee: predicted-greedy routing provably terminates, with no memory of past visits, purely because of the dynamic, history-conditioned nature of the oracle. This gives a finite expected delivery time, together with a precise account of why our argument certifies a linear rather than polylogarithmic rate: the drift we exhibit uses only the guaranteed one-step progress of a local lattice neighbor and never the shortcut’s power-law placement.
18
L. Kian et al.
This leaves a natural open question: whether a stronger, polylogarithmic bound is achievable for lattice-distance predictions under plain greedy routing without auxiliary memory, by exploiting the shortcut’s power-law placement directly rather than only its guaranteed local-neighbor progress. Any such argument would need to control the independence of shortcut information across possible revisits without relying on an explicit cycle-avoidance mechanism, a genuinely different technical challenge from the one resolved here. Acknowledgments. Ladan Kian and Ming Ming Tan were supported in part by National Science Foundation (NSF) grant CCF-2348346. Disclosure of Interests. The authors have no competing interests to declare that are relevant to the content of this article.
References 1. Alimohammadi, Y., Işık, S., Saberi, A.: Local limits of small world networks. arXiv:2501.11226 (2025) 2. Angelopoulos, S., Kamali, S.: Contract scheduling with predictions. Journal of Artificial Intelligence Research 77, 395–426 (2023). https://doi.org/10.1613/jair.1.14117 3. Aradhya, V., Scheideler, C.: Towards learning-augmented peer-to-peer networks: Self-stabilizing graph linearization with untrusted advice. arXiv:2504.02448 (2025) 4. Balliu, A., Brandt, S., Kuhn, F., Nowicki, K., Olivetti, D., Rotenberg, E., Suomela, J.: Distributed computation with local advice. In: 39th International Symposium on Distributed Computing (DISC). LIPIcs, vol. 356, pp. 12:1–12:19 (2025) 5. Boguñá, M., Papadopoulos, F., Krioukov, D.: Sustaining the internet with hyperbolic mapping. Nature Communications 1, 62 (2010) 6. Boyar, J., Ellen, F., Larsen, K.S.: Brief announcement: Distributed graph algorithms with predictions. In: Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC). pp. 322–325 (2025). https://doi.org/10.1145/3732772.3733530, full version: arXiv:2501.05267 7. Carmi, S., Carter, S., Sun, J., ben Avraham, D.: Asymptotic behavior of the kleinberg model. Physical Review Letters 102(23), 238702 (2009). https://doi.org/10.1103/PhysRevLett.102.238702, companion paper to Caretta Cartozo and De Los Rios (2009), same issue 8. Cartozo, C.C., Rios, P.D.L.: Extended navigability of small world networks: Exact results and new insights. Physical Review Letters 102(23), 238703 (2009). https://doi.org/10.1103/PhysRevLett.102.238703 9. Coppersmith, D., Gamarnik, D., Sviridenko, M.: The diameter of a longrange percolation graph. Random Structures & Algorithms 21(1), 1–13 (2002). https://doi.org/10.1002/rsa.10042 10. Dyer, M.E., Galanis, A., Goldberg, L.A., Jerrum, M., Vigoda, E.: Random walks on small world networks. ACM Transactions on Algorithms 16(3), 37 (2020). https://doi.org/10.1145/3382208 11. Fraigniaud, P., Gavoille, C., Paul, C.: Eclecticism shrinks even small worlds. In: Proceedings of the 23rd Annual ACM Symposium on Principles of Distributed Computing (PODC ’04). pp. 169–178. ACM (2004). https://doi.org/10.1145/1011767.1011793
Navigating Small-World Networks with Distance Predictions
19
12. Fraigniaud, P., Giakkoupis, G.: On the searchability of small-world networks with arbitrary underlying structure. In: Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (STOC ’10). pp. 389–398. ACM (2010). https://doi.org/10.1145/1806689.1806744 13. Fraigniaud, P., Lebhar, E., Lotker, Z.: A doubling dimension threshold θ(log log n) for augmented graph navigability. In: Proceedings of the 14th Annual European Symposium on Algorithms (ESA). Lecture Notes in Computer Science, vol. 4168, pp. 376–386. Springer (2006). https://doi.org/10.1007/11841036\_35 14. Giakkoupis, G., Schabanel, N.: Optimal path search in small worlds: Dimension matters. In: Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC ’11). pp. 393–402. ACM (2011). https://doi.org/10.1145/1993636.1993689 15. Kamenev, A., Kowalski, D.R., Mosteiro, M.A.: Faster supervised average consensus in adversarial and stochastic anonymous dynamic networks. ACM Trans. Parallel Comput. 10(2), 13:1–13:35 (2023). https://doi.org/10.1145/3593426, https://doi.org/10.1145/3593426 16. Karp, B., Kung, H.T.: GPSR: Greedy perimeter stateless routing for wireless networks. In: Proceedings of the 6th Annual International Conference on Mobile Computing and Networking (MobiCom). pp. 243–254 (2000) 17. Kleinberg, J.: Navigation in a small world. Nature 406, 845 (2000). https://doi.org/10.1038/35022643 18. Kleinberg, J.: The small-world phenomenon: An algorithmic perspective. In: Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (STOC’00). pp. 163–170. ACM (2000). https://doi.org/10.1145/335305.335325 19. Kleinberg, J.: Small-world phenomena and the dynamics of information. In: Advances in Neural Information Processing Systems 14 (NIPS). pp. 431–438. MIT Press (2001) 20. Kleinberg, J.: Complex networks and decentralized search algorithms. In: Proceedings of the International Congress of Mathematicians (ICM), Madrid 2006. vol. 3, pp. 1019–1044 (2006). https://doi.org/10.4171/022-3/50, nevanlinna Prize lecture; proceedings volume published 2007 21. Kranakis, E., Singh, H., Urrutia, J.: Compass routing on geometric networks. In: Proceedings of the 11th Canadian Conference on Computational Geometry (CCCG). pp. 51–54 (1999) 22. Lykouris, T., Vassilvitskii, S.: Competitive caching with machine learned advice. Journal of the ACM 68(4), 24:1–24:25 (2021). https://doi.org/10.1145/3447579 23. Manku, G.S., Naor, M., Wieder, U.: Know thy neighbor’s neighbor: The power of lookahead in randomized P2P networks. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC ’04). pp. 54–63. ACM (2004). https://doi.org/10.1145/1007352.1007368 24. Martel, C.U., Nguyen, V.: Analyzing kleinberg’s (and other) small-world models. In: Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing (PODC ’04). pp. 179–188. ACM (2004). https://doi.org/10.1145/1011767.1011794 25. Mitzenmacher, M., Vassilvitskii, S.: Algorithms with predictions. Communications of the ACM 65(7), 33–35 (2022) 26. Naor, M., Wieder, U.: Know thy neighbor’s neighbor: Better routing for skip-graphs and small worlds. In: Peer-to-Peer Systems III (IPTPS 2004). Lecture Notes in Computer Science, vol. 3279, pp. 269–277. Springer (2005). https://doi.org/10.1007/9783-540-30183-7\_26
20
L. Kian et al.
27. Nguyen, V., Martel, C.U.: Analyzing and characterizing small-world graphs. In: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’05). pp. 311–320. Society for Industrial and Applied Mathematics (2005) 28. Purohit, M., Svitkina, Z., Kumar, R.: Improving online algorithms via ML predictions. In: Advances in Neural Information Processing Systems 31 (NeurIPS). pp. 9684–9693 (2018) 29. Ruas, O.: Neighbor-of-neighbor routing in small-world networks with power-law degree. Tech. rep., HAL open archive, Distributed, Parallel, and Cluster Computing [cs.DC] (2013), hAL Id: dumas-00854954 30. Seada, K., Helmy, A., Govindan, R.: On the effect of localization errors on geographic face routing in sensor networks. In: Proceedings of the 3rd International Symposium on Information Processing in Sensor Networks (IPSN). pp. 71–80 (2004) 31. Travers, J., Milgram, S.: An experimental study of the small world problem. Sociometry 32(4), 425–443 (1969) 32. Watts, D.J., Strogatz, S.H.: Collective dynamics of ‘small-world’ networks. Nature 393, 440–442 (1998) 33. Zeng, J., Hsu, W.J., Wang, J.: Near optimal routing in a small-world network with augmented local awareness. In: Parallel and Distributed Processing and Applications (ISPA 2005). Lecture Notes in Computer Science, vol. 3758, pp. 503–513. Springer (2005). https://doi.org/10.1007/11576235\_52
A
Pseudo-code of the Predicted-Greedy Routing Algorithm
Algorithm 1 Predicted-Greedy Routing (Cases 1 and 2) Require: source s, target t 1: U0 ← s; i ← 0 2: while Ui ̸= t do receive prediction vector ĥi (Case 1) or p̂i (Case 2) for N + (Ui ), conditioned on 3: Fi 4: Ui+1 ← arg minv∈N + (Ui ) ĥi (v) (resp. p̂i (v)), ties broken by a fixed rule 5: i←i+1 6: end while 7: return T ← i