Pierre Fraigniaud
email: pierre.fraigniaud@liafa.univ-paris-diderot.fr

George Giakkoupis
email: george.giakkoupis@inria.fr

Greedy routing in small-world networks with power-law degrees

Keywords: Small worlds, Social networks, Routing, Search, Power-law degrees

In this paper we study decentralized routing in small-world networks that combine a wide variation in node degrees with a notion of spatial embedding. Specifically, we consider a variant of J. Kleinberg's grid-based smallworld model in which (1) the number of long-range edges of each node is not fixed, but is drawn from a power-law probability distribution with exponent parameter α ≥ 0 and constant mean, and (2) the long-range edges are considered to be bidirectional for the purposes of routing. This model is motivated by empirical observations indicating that several real networks have degrees that follow a powerlaw distribution. The measured power-law exponent α for these networks is often in the range between 2 and 3. For the small-world model we consider, we show that when 2 < α < 3 the standard greedy routing algorithm, in which a node forwards the message to its neighbor that is closest to the target in the grid, finishes in an expected number of O(log α-1 n • log log n) steps, for any source-target pair. This is asymptotically smaller than the O(log 2 n) steps needed in Kleinberg's original model with the same average degree, and approaches O(log n) as α approaches 2. Further, we

Introduction

The study of small-world networks was initiated by the famous "six-degrees-of-separation" experiments conducted by Milgram in the 1960s [START_REF] Milgram | The small world problem[END_REF]. These experiments quantified the so-called "small-world phenomenon," that is, the principle that almost all people are linked by short chains of acquaintances. Milgram's findings have been subsequently confirmed by other experiments and measurements, e.g., by Dodds, Muhamad, and Watts [START_REF] Dodds | An experimental study of search in global social networks[END_REF], and Backstrom, Boldi, Rosa, Ugander, and Vigna [START_REF] Backstrom | Four degrees of separation[END_REF]. Further, it has been observed that several real networks, including social, information, technological, and biological networks, exhibit similar small-world properties; see, e.g., the surveys by Albert and Barabási [START_REF] Albert | Statistical mechanics of complex networks[END_REF] and Newman [START_REF] Newman | The structure and function of complex networks[END_REF], and the book by Dorogovtsev and Mendes [START_REF] Dorogovtsev | Evolution of networks: From biological networks to the Internet and WWW[END_REF].

A striking aspect of Milgram's experiments, pointed out by J. Kleinberg [START_REF] Kleinberg | The small-world phenomenon: An algorithmic perspective[END_REF][START_REF] Kleinberg | Navigation in a small world[END_REF], is that not only do short chains between people exist, but individuals are collectively very effective at finding them using only local information.

To study this algorithmic aspect of the small-world phenomenon Kleinberg proposed a simple random graph model, building upon a small-world model proposed by Watts and Strogatz [START_REF] Watts | Collective dynamics of 'small-world' networks[END_REF]. In Kleinberg's model, individuals are nodes at the lattice points of a two-dimensional n × n square lattice, and acquaintance relationships between individuals are represented by directed edges. Each node u has edges to all nodes whose lattice distance from u is at most r, for some constant r. Further, u has k random long-range edges, where k is another constant parameter. Each of these k edges points to a node chosen independently at random according to the 2-harmonic probability distribution, i.e., each node v is chosen with probability proportional to 1/(d u,v ) 2 2 , where d u,v is the distance between u and v in the lattice. Kleinberg showed that a simple greedy routing algorithm, in which a node forwards the message to its neighbor that is closest to the target in the lattice, routes a message in an expected number of O(log 2 n) steps, for any source-target pair. (This bound was subsequently shown to be tight for a pair chosen uniformly at random, by Barrière, Fraigniaud, Kranakis, and Krizanc [START_REF] Barrière | Efficient routing in networks with long range contacts[END_REF], and Martel and Nguyen [START_REF] Martel | Analyzing Kleinberg's (and other) small-world models[END_REF].) Note that the above greedy routing algorithm is decentralized, in the sense that it does not require knowledge of the long-range edges of nodes not yet visited. Kleinberg showed also that any decentralized routing algorithm needs an expected number of steps that is a polynomial function in n, if the long-range edges are chosen from the h-harmonic distribution for a constant h = 2. 1The above results readily extend to the analogous model based on the -dimensional lattice, for any constant ≥ 1. In this model, the O(log 2 n) expected routing time is achieved when the -harmonic distribution is used to choose the longrange edges. Further, similar results have been shown for several variants and generalizations of this model, where base structures as general as metrics of bounded doubling dimension are used in place of the lattice (cf. Related Work). The probability distribution used to choose the long-range edges in those models is similar to the harmonic distribution considered by Kleinberg [START_REF] Kleinberg | The small-world phenomenon: An algorithmic perspective[END_REF]. Specifically, it is a variant of the following natural distribution: the probability that node u has a long-range edge to node v is inversely proportional to the number of nodes contained in the smallest ball (in the underlying metric space) that is centered at u and contains v. Interestingly, empirical results by Liben-Nowell, Novak, Kumar, Raghavan, and Tomkins [START_REF] Liben-Nowell | Geographic routing in social networks[END_REF] indicate that two-thirds of friendships are geographically distributed that way, i.e., "the probability of befriending a particular person is inversely proportional to the number of closer people."

Kleinberg's model and subsequent generalizations of it do not take into account the well-established fact that social and other real networks have a highly skewed distribution of node degrees. It has been observed that the degree distribution of these networks is a power law, i.e., the probability that a node has degree k is proportional to 1/k α [START_REF] Albert | Statistical mechanics of complex networks[END_REF][START_REF] Dorogovtsev | Evolution of networks: From biological networks to the Internet and WWW[END_REF][START_REF] Newman | The structure and function of complex networks[END_REF]. Further, the value of the power-law exponent α has been measured to be between 2 and 3 for several real network, including social networks (e.g., the collaboration network of film actors, and networks of email messages), samples of the Web and the Internet, various peer-to-peer networks, and metabolic and protein interaction biological networks (see [START_REF] Newman | The structure and function of complex networks[END_REF]Table II]). A straightforward way to reconcile Kleinberg's model with a power-law degree distribution is to choose the number of long-range edges of each node independently at random from that distribution; this approach was first proposed by Kleinberg in [START_REF] Kleinberg | Complex networks and decentralized search algorithms[END_REF]. 2 It is reasonable to expect that a power-law degree distribution can reduce the network diameter or the average length of shortest paths between nodes, e.g., similar to the works of Bollobás and Riordan [START_REF] Bollobás | The diameter of a scale-free random graph[END_REF], and Chung and Lu [START_REF] Chung | The average distance in a random graph with given expected degrees[END_REF]. However, prior to our work there were no results suggesting that power-law degree distributions could improve the speed of greedy routing.

Our contribution

We consider a simple variant of Kleinberg's -dimensional small-world model [START_REF] Kleinberg | The small-world phenomenon: An algorithmic perspective[END_REF], in which nodes have a power-law degree distribution. In this model each long-range edge is drawn independently at random from the -harmonic distribution, i.e., the distribution that yields an expected routing time of O(log 2 n) in Kleinberg's model. The number of long-range edges of each node is drawn independently at random from a power-law distribution with exponent parameter α ≥ 0 and a fixed constant expected value. Further, we assume that each node has at least one long-range edge. (For a precise description of the model see Section 2.) For this network, we study the complexity of the same greedy routing algorithm considered by Kleinberg, except that we treat long-range edges as bidirectional; i.e., a node forwards the message to its out-or in-neighbor that is closest to the target in the grid. If we treat long-range edges as unidirectional, then we observe that greedy routing performs asymptotically the same as in Kleinberg's original model. 3 Having bidirectional long-range edges is qualitatively different, because in this case a node of high degree is easy to find, while if long-range edges are unidirectional then a node of high out-degree may have low in-degree and thus it may be difficult to find.

We now summarize our results (see also Table 1, and Figure 1). For the case of 2 < α < 3, which is the case for many real networks including social networks, we show that routing finishes in an expected number of O(log α-1 n • log log n) steps for any source-target pair of nodes. This is asymptotically smaller than the O(log 2 n) steps needed in Kleinberg's original model with the same average number of long-range edges per node, and it approaches O(log n) as

Power-law

Upper bound exponent α (for any pair) Lower bound

0 ≤ α < 2 O(log 2 n) Ω (log 2 n) (for worst pair) α = 2 O(log 4/3 n) Ω (log 4/3 n) (for worst pair) 2 < α < 3 O(log α-1 n • log log n) Ω (log α-1 n) (for random pair) α = 3 O(log 2 n) Ω (log 2 n/ log log n) (for random pair) α > 3 O(log 2 n) Ω (log 2 n) (for random pair)
Table 1 Our bounds on the expected routing time of greedy routing, for the small-world model with a power-law degree distribution of exponent α, and bidirectional long-range edges. The upper bounds hold for any source-target pair. The lower bounds hold for a randomly chosen pair when α > 2, and for the worst pair when α ≤ 2. The upper bounds are stated formally in Theorem 1, and the lower bounds in Theorem 2.

α approaches 2. We complement this upper bound with an almost matching lower bound of Ω (log α-1 n) steps, on the expected routing time for a uniformly random pair. For the case of α ≥ 3 or α < 2, we show that an expected number of O(log 2 n) steps suffices for any pair. Further, we show a matching lower bound of Ω (log 2 n) expected steps for a random pair when α > 3, and for the worst pair when α < 2; for α = 3 we show a lower bound that is weaker by a log log n factor. Finally, for the critical value α = 2, we show an upper bound of O(log 4/3 n) on the expected number of steps for any pair, and a matching lower bound of Ω (log 4/3 n) for the worst pair.

Related work

Several papers have extended Kleinberg's work [START_REF] Kleinberg | The small-world phenomenon: An algorithmic perspective[END_REF] to small-world models based on structures other than the lattice (or the grid graph). In a follow-up work, Kleinberg [START_REF] Kleinberg | Small-world phenomena and the dynamics of information[END_REF] extended his results to a hierarchical model, in which nodes are the leaves of a complete b-ary tree, and the distance between two nodes is the length of the path between them in the tree. Further, he proposed a model that generalizes both the lattice-based and the hierarchical models, in which the distances between nodes are induced by certain families of node sets. Small-world networks on base structures similar to the grid graph were studied by Martel and Nguyen [START_REF] Martel | Analyzing Kleinberg's (and other) small-world models[END_REF][START_REF] Martel | Analyzing and characterizing small-world graphs[END_REF], who computed the diameter of these networks. Duchon, Hanusse, Lebhar, and Schabanel [START_REF] Duchon | Could any graph be turned into a small-world?[END_REF] considered small-world networks in which the base graph has a "bounded growth rate" property. Fraigniaud [START_REF] Fraigniaud | Greedy routing in tree-decomposed graphs[END_REF] studied base graphs of bounded tree-width. Slivkins [START_REF] Slivkins | Distance estimation and object location via rings of neighbors[END_REF] considered the case in which nodes are embedded in a metric space of bounded doubling dimension. Finally, Abraham and Gavoille [START_REF] Abraham | Object location using path separators[END_REF] studied base graphs that exclude a fixed minor. In all these settings, greedy routing (with respect to distances in the base structure) finishes in a polylogarithmic expected number of steps, for suitable distributions of longrange edges similar to the -harmonic distribution on thedimensional lattice. More recently, in [START_REF] Fraigniaud | On the searchability of small-world networks with arbitrary underlying structure[END_REF] we considered the case in which the base structure is an arbitrary graph, and we showed that routing in sub-polynomial expected time can be achieved by a slight variant of greedy routing, for long-range edges drawn from an adaptation of the harmonic distribution.

A long line of work has studied lower bounds for greedy routing on small-world networks, e.g., the works by Aspnes, Diamadi, and Shah [START_REF] Aspnes | Fault-tolerant routing in peer-to-peer systems[END_REF], Flammini, Moscardelli, Navarra, and Pérennes [START_REF] Flammini | Asymptotically optimal solutions for small world graphs[END_REF], Giakkoupis and Hadzilacos [START_REF] Giakkoupis | On the complexity of greedy routing in ring-based peer-to-peer networks[END_REF], and Dietzfelbinger and Woelfel [START_REF] Dietzfelbinger | Tight bounds for blind search on the integers[END_REF][START_REF] Dietzfelbinger | Tight lower bounds for greedy routing in uniform small world rings[END_REF]. These bounds are for an extension of Kleinberg's one-dimensional model, which assumes that the distribution used to choose the number of long-range edges per node and the length of these edges can be arbitrary, but is the same for all nodes. In the most recent of these works [START_REF] Dietzfelbinger | Tight lower bounds for greedy routing in uniform small world rings[END_REF], it was shown that for any distribution with constant expected number of long-range edges per node, greedy routing needs an expected number of Ω (log 2 n) steps for a random source-target pair of nodes. This result does not contradict our results, as it assumes unidirectional long-range edges.

Several decentralized routing algorithms, other than the standard greedy algorithm, have been proposed for Kleinberg's network. Manku, Naor, and Wieder [START_REF] Manku | Know thy neighbor's neighbor: The power of lookahead in randomized P2P networks[END_REF] considered a greedy algorithm assuming that each node knows also the neighbors of its neighbors; their results built upon the work of Coppersmith, Gamarnik, and Sviridenko [START_REF] Coppersmith | The diameter of a long range percolation graph[END_REF]. Lebhar and Schabanel [START_REF] Lebhar | Almost optimal decentralized routing in long-range contact networks[END_REF], Fraigniaud, Gavoille, and Paul [START_REF] Fraigniaud | Eclecticism shrinks even small worlds[END_REF], Martel and Nguyen [START_REF] Martel | Analyzing Kleinberg's (and other) small-world models[END_REF], and Giakkoupis and Schabanel [START_REF] Giakkoupis | Optimal path search in small worlds: Dimension matters[END_REF] proposed algorithms that construct shorter paths than greedy routing, but they visit (or "consult") an additional small number of nearby nodes before they decide the next node in the path. For more related work on decentralized routing (or search) in small-world networks, see the survey by Kleinberg [START_REF] Kleinberg | Complex networks and decentralized search algorithms[END_REF]. See also the work by Lattanzi, Panconesi, and Sivakumar [START_REF] Lattanzi | Milgramrouting in social networks[END_REF] for a different model on search in social networks.

Exploiting the degree distribution in the design of decentralized search algorithms for networks with powerlaw degree distributions has been investigated by Adamic, Lukose, Puniyani, and Huberman [START_REF] Adamic | Search in power-law networks[END_REF], Kim, Yoon, Han, and Jeong [START_REF] Kim | Path finding strategies in scale-free networks[END_REF], and Sarshar, Boykin, and Roychowdhury [START_REF] Sarshar | Percolation search in power law networks: Making unstructured peer-to-peer networks scalable[END_REF]. In these works, the search algorithm has access only to information on the degrees of neighboring nodes, and not to any type of spacial embedding of nodes as in Kleinberg's model. Simsek and Jensen [START_REF] Simsek | Decentralized search in networks using homophily and degree disparity[END_REF] proposed a heuristic routing algorithm for a variant of Kleinberg's model [START_REF] Kleinberg | The small-world phenomenon: An algorithmic perspective[END_REF] similar to ours, in which nodes have widely varying degrees. Their algorithm assumes that nodes know both the location and the degree of their neighbors, and their simulation results suggest that it is faster than decentralized algorithms that use only one of these two types of information. A main difference between this work and ours is that the greedy routing algorithm we consider does not take into account node degrees. Despite that, we show that it can benefit from powerlaw degree distributions. Further, in our work we give provable bounds as opposed to Simsek and Jensen who provide an experimental evaluation.

Model and results

Below we describe the small-world model and the routing algorithms we consider, then state our main theorems, and finally give some intuition for the results.

Small-world graph

For integers , n ≥ 1 and a real α ≥ 0, we denote by SW( , n, α) a random directed graph generated as follows.

We start with an -dimensional grid graph that wraps around (i.e., a torus), in which edges are bidirectional and every dimension has size n. Thus the total number of nodes is n . We will refer to this graph as the grid, and call the 2 neighbors of each node its grid-neighbors. Further for any two nodes u, v we define the grid-distance, or simply distance, between u and v to be their shortest-path distance in the grid, and denote it by d(u, v) or d u,v . 4 This deterministic grid is then augmented by adding random edges as follows. For each node u, we draw independently at random an integer C u from a power-law distribution with exponent α and mean 2; the details of this distribution are given below. Then, we choose C u nodes independently at random (with replacement) according to a distribution that assigns to each node v = u a probability proportional to d(u, v) -; the details are given below. The resulting multi-set of nodes is the set of outcontacts of u, and we draw an edge from u to each of these out-contacts, allowing parallel edges. These edges are the long-range edges of u. We say that node v is an in-contact of u, if u is an out-contact of v.

Next we specify the two probability distributions used in the above construction. The power-law distribution from which the number C u of the out-contacts of u is drawn is defined as follows. If α > 2 then C u is chosen from the set {1, 2, . . .} of positive integers such that

Pr(C u = k) = q k := k -α /ν, if k ≥ 2; 1 -∑ i≥2 i -α /ν, if k = 1,
where ν is the normalizing constant that yields E[C u ] = 2, i.e., ∑ k≥1 kq k = 2. It follows that

ν = ∑ i≥2 i 1-α -i -α .
For α ≤ 2 this definition does not work, as in this case the sum above is unbounded. For this reason we impose a maximum value of k max on C u , i.e., C u is now chosen from the finite set {1, . . . , k max }; other than that, the distribution we use is exactly the same as in the case of α > 2. We will assume that k max = n γ for some constant 0 < γ ≤ . We point out that our model assumptions that C u ≥ 1 with probability 1 and E[C u ] = 2 were made just to simplify exposition. The results of this paper hold as long as Pr(C u ≥ 1) = Ω (1) and E[C u ] = Θ (1). Hence, for the case of α > 2, we could use instead the more natural distribution that Pr(C u = k) = k -α /ν for any k ≥ 1 (i.e., including k = 1) for a constant ν, and k = 0 with the remaining probability. For α ≤ 2, we cannot assume that Pr(C u = k) = k -α /ν for k = 1, as then C u must be zero with probability 1o(1) (and thus Pr(

C u ≥ 1) = o(1)) in order to have E[C u ] = O(1).
The distribution from which we choose each of the C u out-contacts of u is the standard distribution proposed by Kleinberg: Each node v = u is picked with probability

p d u,v := (d u,v ) -/η,
where is the dimension of the grid and η is the normalizing factor

η = ∑ v =u (d u,v ) -= Θ (ln n).
The assumption that the out-contacts of a node are chosen with replacement is standard and is convenient for the analysis. We expect that the same asymptotic results should hold even if the out-contacts are choose without replacement. The reason is that the fraction of duplicate out-contacts is significant only for very large values of C u , and our analysis shows that the role of nodes u with such large C u is negligible, because they are so rare.

Finally, for the number of in-contacts of a node, it can be show that it follows a distribution that is close to a binomial distribution with constant mean.

Greedy routing

We consider two versions of greedy routing. The first is the standard greedy protocol: A node u that receives a message for target node t = u forwards the message to the node v among its grid-neighbors and out-contacts that is closest to t in the grid, i.e., d(v,t) is minimal. If there are more than one such v, then any of them can be used, but we assume that the choice is deterministic (e.g., we can use the first of those v in the lexicographic order of their d-dimensional vector of coordinates). We call this algorithm GreedyUniDir, as the messages can be sent through an edge only along the direction of the edge. The second algorithm we consider is called GreedyBiDir, and ignores the direction of edges: node u forwards the message to the node v among its gridneighbors, out-contacts, and in-contacts that is closest to t in the grid.

We consider two measures for the performance of the above routing algorithms. The first is the expected routing time for the worst-case source-target pair, i.e., we measure the expected routing time for each pair and then take the largest of these expected times. The second measure is the expected routing time for a source-target pair chosen uniformly at random. This is equivalent to measuring the expected routing time for each pair and then taking the average. Clearly, the first measure (for the worst pair) is always greater or equal to the second measure (for the random pair). Our upper bounds are for the worst pair, and our lower bounds for a random pair, except for the lower bounds for GreedyBiDir when α ≤ 2, which are for the worst pair.

Results

Next we state our main theorems. The asymptotic notation is for n → ∞, and we assume that and α are not functions of n.

Theorem 1 (Upper bounds) The expected routing time of GreedyUniDir for the worst pair in SW( , n, α) is O(log 2 n). For GreedyBiDir, the expected routing time for the worst pair is

     O(log 2 n), if 0 ≤ α < 2 or α ≥ 3; O(log α-1 n • log log n), if 2 < α < 3; O(log 4/3 n), if α = 2.
Theorem 2 (Lower bounds) The expected routing time of GreedyUniDir for a random pair in SW( , n, α) is Ω (log 2 n). For GreedyBiDir, the expected routing time for a random pair is

     Ω (log 2 n), if α > 3; Ω (log 2 n/ log log n), if α = 3; Ω (log α-1 n), if 2 < α < 3;
and the expected routing time for the worst pair is

Ω (log 2 n), if 0 ≤ α < 2; Ω (log 4/3 n), if α = 2.

Intuition

We give now some informal intuition for the results above.

For the O(log 2 n) bound to hold it suffices that each node has just one out-contact. Achieving smaller routing times requires that nodes with ω(1) out-contacts are encountered sufficiently often. For GreedyUniDir, the probability that the next node in the routing path has k out-contacts equals q k = Pr(C u = k). We show that this probability is not high enough to yield routing times below Ω (log 2 n). In the case of GreedyBiDir, nodes with many out-contacts are more likely to be found than in GreedyUniDir, as they can be reached through their long-range edges. The probability that a given node has an in-contact with k out-contacts is proportional to the fraction of long-range edges in the network starting from nodes with k out-contacts, and is roughly kq k .

The actual probability that the next node in the routing path has k out-contacts is smaller than that, and the main reason is that only nodes that are closer to the target than the node who has the message are relevant to routing. This reduces the above probability of kq k by roughly a factor of ln d/ ln n, where d is the current distance to the target. For the case of 2 < α < 3, the above reasoning gives that the probability of the next node in the path to have Θ (ln n) out-contacts (more concretely, say, between ln n and 2 ln n)

is roughly ln n • (ln n • q ln n ) • (ln d/ ln n) ≈ ln d/ ln α-1 n;
and from such a node, the distance to the target halves in the next step with probability Ω (1). Based on that we show the O(ln α-1 n • log log n) bound. To prove the lower bound we further observe that the contribution of nodes with either o(ln n) or ω(ln n) out-contacts is negligible compared to that of nodes with Θ (ln n) out-contacts. We point out that for α → 2 the above upper bound approaches O(ln n), which is the expected routing time in Kleinberg's model for k = Θ (ln n) out-contacts per node.

In the case of α = 2, roughly equal fractions of longrange edges start from nodes with Θ (2 i ) out-contacts for each i. When the distance d to the target is sufficiently large, the distance decreases to d 1-ε in a step with probability roughly ln 2 d/ ln 2 n, and the nodes that contribute the most to that reduction are those with a number of out-contacts roughly between d ε and d, for constants ε and ε . It follows that the distance to the target decreases quickly when d is large, but when the distance drops below roughly 2 (ln n) 1/3 , we have essentially no speedup. Then it takes

Θ (log n • log 2 (log n) 1/3 ) = Θ (log 4/3 n)
steps to reach the target from that distance.

In the case of α > 3, nodes with ω(1) out-contacts are very rare, and only a o(1) fraction of the long-range edges starts from those nodes. It follows that the O(log 2 n) bound is tight for this case. On the other hand, when α < 2, a large fraction of the long-range edges starts from nodes that have a very high number of out-contacts. However, nodes with ω(1) out-contacts are so rare that, with significant probability, no such node exists within distance Θ (n ε ) from the target, for a sufficiently small constant ε. It follows that Θ (log n • log n ε ) = Θ (log 2 n) steps are needed to cover that distance.

The lower bounds we provide for GreedyBiDir for α ≤ 2 are shown for the worst pair only rather than a random pair. In [START_REF] Fraigniaud | The effect of power-law degrees on the navigability of small worlds[END_REF] we showed that the Ω (log 4/3 n) bound for α = 2 holds also for a random pair, but here we consider just the worst pair as the proof for the random pair is much more involved. For α < 2, we do not know whether the O(log 2 n) bounds holds for a random pair.

Preliminaries

In this section we first introduce some notation, and then prove a collection of results on the distribution of edges to be used later in the analysis.

For two sets of nodes U 1 and U 2 we write U 1 → U 2 to denote that some node from U 2 is an out-contact of a node from U 1 . If U 1 or U 2 is a singleton set, we may write its element instead of the set in this notation, e.g., we will write u → v to denote {u} → {v}. A ball B u (r) centered at node u with radius r is the set of nodes v with d(u, v) ≤ r. A sphere S u (r) is the set B u (r) \ B u (r -1).

We denote by K( , n, k) Kleinberg's model obtained in the same way as SW( , n, α) except that each node u has k out-contacts, instead of C u . It follows that SW( , n, α) can be obtained from K( , n, 1), by adding C u -1 additional long-range edges from each node u.

Next we provide some bounds on the probability that a given node in K( , n, 1) has out-contacts or in-contacts from a given set of nodes.

Observation 1 Let u,t be two distinct nodes in K( , n, 1), and U be a nonempty set of nodes.

(a) Pr(u → B t (r)) = O ln d u,t d u,t -r / ln n , for 1 ≤ r ≤ d u,t -1. (b) Pr(u → B t (r)) =      Ω r d u,t / ln n , if 1 ≤ r ≤ d u,t /2; Ω ln d u,t d u,t -r / ln n , if d u,t /2 ≤ r ≤ d u,t -1. (c) Pr(u → B t (d u,t /2)) = Θ (1/ ln n). (d) Pr(u → B t (d u,t -1)) = Θ (ln(d u,t )/ ln n). (e) Pr(u → S t (r)) = O 1 ln n•(d u,t -r) , for 0 ≤ r ≤ d u,t -1. (f) Pr(u → U) = o(1), if |U| = n o(1) . (g) Pr(U → u) ∈ Pr(u → U)/2, Pr(u → U) . (h) Pr(U → u) ≥ 1/4.
Proof We give first some useful facts. The maximum distance between any two nodes is d max = • n/2 . The number of nodes at distance r from node t is

|S t (r)| = Θ r -1 , if 1 ≤ r ≤ n/2; O r -1 , if n/2 ≤ r ≤ d max . (1)
For the case of 1 ≤ r ≤ n/2, the result follows from [START_REF] Martel | Analyzing Kleinberg's (and other) small-world models[END_REF]Fact 19(i)]. For the case of n/2 ≤ r ≤ d max , we just apply the result for the previous case to the larger grid in which every dimension has size d max (instead of n), and we observe that |S t (r)| in the original grid is bounded by the corresponding quantity in the larger grid. We can use the above bound for |S t (r)| to bound the size of ball B t (r),

|B t (r)| = r ∑ i=0 |S t (i)| = Θ (r ). ( 2
) (a): For each node v ∈ B t (r), its distance d u,v from u satisfies d u,t -r ≤ d u,v ≤ d u,t + r. It follows that B t (r) ⊆ d u,t +r i=d u,t -r S u (i), and thus Pr(u → B t (r)) ≤ d u,t +r ∑ i=d u,t -r Pr(u → S u (i)) = d u,t +r ∑ i=d u,t -r |S u (i)| • p i (1) = O d u,t +r ∑ i=d u,t -r i -1 ln n • i = O ln d u,t + r d u,t -r / ln n .
To complete the proof we argue that ln

d u,t +r d u,t -r ≤ 2 ln d u,t d u,t -r : We must show d u,t +r d u,t -r ≤ d u,t d u,t -r 2 which is equivalent to (d u,t + r) • (d u,t -r) ≤ (d u,t ) 2 , and this is equiv- alent to (d u,t ) 2 -r 2 ≤ (d u,t ) 2 , which is true. (b): First we consider the case of 1 ≤ r ≤ (1-ε)•d u,t , for an arbitrary small constant ε > 0. For each node v ∈ B t (r) we have d u,v ≤ d u,t + r ≤ 2d u,t , and thus Pr(u → B t (r)) ≥ |B t (r)| • p 2d u,t (2) = Ω r ln n • (2d u,t ) = Ω r ln n • (d u,t ) .
This proves the case of r ≤ d u,t /2, and also the case of

d u,t /2 ≤ r ≤ (1 -ε) • d u,t
, because in the latter case both quantities ln

d u,t d u,t -r and r d u,t are Θ (1). Next we consider the case of (1 -ε) • d u,t < r ≤ d u,t -1,
for a sufficiently small constant ε > 0; in particular, we will need that ε ≤ 1/(4 2 ). Further, we assume that d u,t > 1/ε, otherwise the above range for r is empty. We represent each node by its 'grid coordinates', i.e., an -vector from {n/2 , . . . , n/2 } ; we assume that u = (0, 0, . . . , 0) and t = (x 1 , . . . , x ). Since ∑ i=1 |x i | = d u,t , it follows that for some index i it holds |x i | ≥ d u,t / . We assume w.l.o.g. that x 1 ≥ d u,t / . Let t = (x 1 , 0, . . . , 0) and r = x 1λ , where λ = d u,tr. (Observe that r > 0, because λ < εd u,t as r > (1ε) • d u,t , and εd u,t ≤ d u,t /(4 2 ) < d u,t / ≤ x 1 .) If we consider a shortest path from u to t in the grid, which goes from u to t and from there to t, it is easy to see that ball B t (r ) is a subset of B t (r): for each node v ∈ B t (r ) we have

d(t, v) ≤ d(t,t ) + d(t , v) ≤ (d t,u -x 1 ) + r = r,
and thus B t (r ) ⊆ B t (r). Therefore,

Pr(u → B t (r)) ≥ Pr(u → B t (r )).
We will now lower bound the probability on the right side. Let L i , for λ ≤ i ≤ x 1 , be the set of nodes v = (y 1 , . . . , y ) from B t (r ) with y 1 = i. The size of L i is then the number of possible ways to fix y 2 , . . . , y such that d(v,t ) ≤ r , which is equivalent to

|y 2 | + • • • + |y | ≤ r -(x 1 -i) = i -λ . (3)
Thus if > 1, by counting only non-negative combinations we obtain,

|L i | ≥ i-λ ∑ s=0 s + -2 -2 = 1+ i-λ ∑ s=1 Ω (s -2 ) = Ω (i -λ ) -1 .
The above lower bound holds also when = 1, as in this case

|L i | = 1 or 2. Further, for each v = (i, y 2 , . . . , y ) ∈ L i we have d(v, u) ≤ i + |y 2 | + • • • + |y | ≤ 2i, by (3). It follows Pr(u → B t (r )) ≥ x 1 ∑ i=λ |L i | • p 2i = Ω x 1 ∑ i=λ (i -λ ) -1 ln n • (2i) = Ω x 1 ∑ i=λ (1 -λ /i) -1 ln n • i = Ω x 1 ∑ i=2λ (1/2) -1 ln n • i = Ω ln x 1 2λ / ln n .
To complete the proof we argue that ln

x 1 2λ ≥ ln d u,t d u,t -r /2: We must show that x 1 2λ 2 ≥ d u,t
d u,t -r , and since x 1 ≥ d u,t / and λ = d u,tr, it suffices to show that

d u,t / 2(d u,t -r) 2 ≥ d u,t d u,t -r , which is equivalent to d u,t -r d u,t ≤ 1 4 2 .
The last inequality holds because the left side is at most ε and we have assumed that ε ≤ 1/(4 2 ). (f): For a fixed set size |U|, the probability Pr(u → U) is maximized when U consists of the |U| nodes closest to u. From (1), the number of nodes at distance i from u is 1) .

|S u (i)| ≤ c • i -1 for some constant c. It follows Pr(u → U) ≤ (|U|/c) 1/( -1) ∑ i=1 (c • i -1 • p i ) = O   (|U|/c) 1/( -1) ∑ i=1 1 ln n • i   = O   ln (|U|/c) 1/( -1) ln n   = O ln(|U|) ln n = o(1), as |U| = n o(
(g): The upper bound follows from the union bound,

Pr(U → u) ≤ ∑ v∈U Pr(v → u) = ∑ v∈U Pr(u → v) = Pr(u → U).
For the lower bound we have

Pr(U → u) = 1 -∏ v∈U (1 -Pr(v → u)) ≥ 1 -∏ v∈U e -Pr(v→u) = 1 -e -∑ v∈U Pr(v→u) = 1 -e -∑ v∈U Pr(u→v) = 1 -e -Pr(u→U) ≥ Pr(u → U)/2,
where for the last relation we used the fact that e -x ≤ 1-x/2 for 0 ≤ x ≤ 1.

(h): For each v ∈ U we have Pr(v → u) = 1 -Pr(v → u) ≥ 4 -Pr(v→u) , because of the facts that 1 -x ≥ 4 -x for 0 ≤ x ≤ 1/2, and Pr(v → u) < 1/2. It follows that Pr(U → u) = ∏ v∈U Pr(v → u) ≥ ∏ v∈U 4 -Pr(v→u) = 4 -∑ v∈U Pr(v→u) = 4 -∑ v∈U Pr(u→v) = 4 -Pr(v→U) ≥ 4 -1 .
This completes the proof of Observation 1.

The next claim gives bounds on the probability that a given node u in SW( , n, α) has out-contacts in some set U, conditionally on the event that u has (or has not) long-range edges to nodes in another given set. The bounds are in terms of simpler probability expressions that do not involve conditioning on u having long-range edges to other sets. This type of conditioning will be very common throughout our analysis of GreedyBiDir, as, e.g., nodes that are closer to the target than the node holding the message have no edges to previous nodes in the routing path.

Observation 2 Let u be a node in SW( , n, α), and U,W,W be disjoint sets of nodes not containing u. Sets U and W are nonempty, but W may be empty. 1) ; in particular, (1) and

(a) Pr(u → U) ≤ Pr(u → U | C u = 2) ≤ 2 Pr(u → U | C u = 1). (b) For any event E, Pr(E | u → W ) ≤ (1 + o(1)) • Pr(E), if |W | = n o(
Pr(u → U | u → W ) ≤ (1 + o(1)) • Pr(u → U | C u = 2), if |W | = n o(1) . (c) Pr(u → U | u → W ) ≤ Pr(u → U | C u = 3), if |W | = n o
|U| = n o(1) . (d) Pr(u → U | u → W ) ≥ Pr(u → U | C u = 1). (e) Pr(u → U | C u = k, u → W ) ≥ Pr(u → U | C u = k -1). (f) Pr(u → U | C u = k, u → W ) ≤ Pr(u → U | C u = k) Pr(u → W | C u = 1) . Proof (a): Let a := Pr(u → U | C u = 1); then Pr(u → U | C u = k) = a k . We have Pr(u → U) = ∑ k Pr(u → U | C u = k) • Pr(C u = k) = ∑ k a k • Pr(C u = k) = E a C u .
Since a x is a convex function, it follows from Jensen's Inequality that

E a C u ≥ a E[C u ] = a 2 = Pr(u → U | C u = 2).
Therefore, Pr(u → U) ≥ Pr(u → U | C u = 2), and thus Pr(u → U) ≤ Pr(u → U | C u = 2), as desired. Also, from the union bound it follows Pr(u

→ U | C u = 2) ≤ 2 Pr(u → U | C u = 1). (b): We have Pr(E | u → W ) = Pr(E ∧ u → W ) Pr(u → W ) ≤ Pr(E) Pr(u → W ) ,
and Pr(u

→ W ) = 1 -Pr(u → W ) (a) ≥ 1 -2 Pr(u → W | C u = 1) Obs.1(f) = 1 -o(1). Thus, Pr(E | u → W ) ≤ Pr(E)/(1 -o(1)) = (1 + o(1)) • Pr(E).
The second part of (b) follows from the first and (a).

(c): Let a := Pr(u → U | C u = 1), and note that a = o(1) from Observation 1(f). We have

Pr(u → U | u → W ) (b) ≤ (1 + o(1)) • Pr(u → U | C u = 2) ≤ 2a + o(a). Further, Pr(u → U | C u = 3) = 1 -(1 -a) 3 = 1 -(1 -3a + o(a)) = 3a -o(a),
where the second-to-last relation holds because a = o(1). From the two expressions above it follows Pr(u

→ U | u → W ) ≤ Pr(u → U | C u = 3).
(d): Since u has at least one out-contact, we have

Pr(u → U | u → W ) ≥ Pr(u → U | u → W, C u = 1) = Pr(u → U ∧ u → W | C u = 1) Pr(u → W | C u = 1) = Pr(u → U | C u = 1) Pr(u → W | C u = 1) ≥ Pr(u → U | C u = 1) 1 .
(e): Given that C u = k and u → W , we can assume that the out-contacts of u are chosen as follows. We start by choosing (from the right probability distribution) the smallest j such that the j-th out-contact of u is the first one that belongs to W . Then we choose the first j -1 out-contacts conditionally on the event that u → W , and the last kj out-contacts without any conditioning. We note that the first j -1 out-contacts are more likely to belong to U than if they were chosen unconditionally. The claim then follows.

(f): From Bayes' Rule we have

Pr(u → U | C u = k, u → W ) = Pr(u → W | C u = k, u → U) Pr(u → W | C u = k) • Pr(u → U | C u = k).
Also from (e) it follows Pr(u

→ W | C u = k, u → U) ≤ Pr(u → W | C u = k -1)
, and thus,

Pr(u → W | C u = k, u → U) Pr(u → W | C u = k) ≤ Pr(u → W | C u = k -1) Pr(u → W | C u = k) = Pr(u → W | C u = 1) k-1 Pr(u → W | C u = 1) k = 1 Pr(u → W | C u = 1)
.

Combining the above yields the claim. This completes the proof of Observation 2.

Proof of the upper bounds

We prove now the upper bounds of Theorem 1. In Section 4.1, we show an O(log 2 n) bound that applies to both algorithms for all exponents α. In fact, we prove a more general lemma which states that O((log d + log β -1 ) • log n) steps suffice to reach the target from a node at distance d with probability 1β . The main claim we use is that the distance to the target halves with probability Ω (1/ ln n) in each step. This claim holds even if nodes have only one outcontact each.

In Sections 4.2 and 4.3 we prove stronger bounds for GreedyBiDir for the cases of 2 < α < 3 and α = 2, respectively. For the case of 2 < α < 3, the key claim is that the distance to the target halves with probability Ω (log d/ log α-1 n) within O(1) steps, where d is the current distance. (We note that this bound is larger than Ω (1/ ln n) for d sufficiently large.) The proof of that claim lower bounds the probability of the event that the next node in the path: ( 1) is an in-contact of the previous node, (2) has Θ (log n) out-contacts, and (3) has at least one out-contact within distance d/2 from the target. For the case of α = 2, we have a similar claim saying that the distance to the target decreases to d 1-ε for some constant ε > 0, with probability Ω (log 2 d/ log 2 n) in the next O(1) steps. The proof lower bounds the probability of the event that the next node in the path ( 1) is an in-contact of the previous node, (2) has between d ε 1 and d ε 2 out-contacts, for some constants ε 1 < ε 2 < 1ε, and (3) has some out-contact within distance d ε from the target. In both cases, 2 < α < 3 and α = 2, we use the lemma from Section 4.1 to bound the number of remaining steps when the distance to the target becomes sufficiently small.

A general upper bound

In this section we prove a bound of O((log d + log β -1 ) • log n) steps for routing between two given nodes at distance d, that holds with probability 1β . This bound applies to both routing algorithms and all exponents α. Lemma 1 For either protocol and any α ≥ 0, the routing time for a pair of nodes s,t is O (log d s,t + log β -1 ) • log n with probability 1-β , for any 0 < β < 1 (which may depend on n and d s,t ). Further, for GreedyBiDir we have that if s is an intermediate node in the routing path from some node s to t, then the same probability bound holds for the time until the message reaches t from s, conditionally on the path up to s.

This result implies the O(log 2 n) bound of Theorem 1 for GreedyUniDir, and for GreedyBiDir when 0 ≤ α < 2 or α ≥ 3: by choosing β = 1/d s,t , Lemma 1 gives that the routing time is O(log d s,t • log n) with probability at least 1 -1/d s,t , and thus the expected routing time is at most

(1 -1/d s,t ) • O(log d s,t • log n) + (1/d s,t ) • d s,t = O(log d s,t • log n) = O(log 2 n).
Proof of Lemma 1 The proof structure follows that of [START_REF] Kleinberg | The small-world phenomenon: An algorithmic perspective[END_REF]Theorem 2]. Denote by d i the distance between the node that has the message after i steps and the target t. We will prove the following claim below.

Claim 1 Pr[d i+1 ≤ d i /2 | d i ] = Ω (1/ ln n).
We use Claim 1 to bound the expectation of d i+1 . We have

E[d i+1 | d i ] ≤ Pr(d i+1 ≤ d i /2 | d i ) • d i /2 + (1 -Pr(d i+1 ≤ d i /2 | d i )) • d i = (1 -Pr(d i+1 ≤ d i /2 | d i )/2) • d i ≤ (1 -c/ ln n) • d i ,
for some constant c > 0, by Claim 1. Taking now the unconditional expectation we obtain that

E[d i+1 ] ≤ (1 -c/ ln n) • E[d i ]. Applying this inequality repeatedly yields E[d i ] ≤ (1 -c/ ln n) i • d 0 , and thus for t * = (ln d 0 + ln β -1 ) • ln n/c, E[d t * ] ≤ (1 -c/ ln n) (ln d 0 +ln β -1 )•ln n/c d 0 ≤ e -(ln d 0 +ln β -1 ) d 0 = β . Markov's Inequality then gives Pr(d t * ≥ 1) ≤ E[d t * ]/1 ≤ β .
Hence, the probability that the target is reached in at most t * steps is Pr(

d t * = 0) = 1 -Pr(d t * ≥ 1) ≥ 1 -β .
It remains to prove Claim 1. Fix the i-th node u i in the routing path, and thus its distance d i from target t. For the case of GreedyUniDir, the out-contacts of u i do not depend on the routing path up to node u i . Since u i has at least one out-contact, the probability that u i → B t (d i /2) is lower bounded by the probability of the same event in K( , n, 1):

Pr(u i → B t (d i /2)) ≥ Pr K( ,n,1) (u i → B t (d i /2)) Obs.1(c) = Θ (1/ ln n),
and thus Pr(

d i+1 ≤ d i /2) = Ω (1/ ln n).
For the case of GreedyBiDir, we rely on the in-contacts of u i to prove the claim rather than its out-contacts. Fix the path u 0 . . . u i up to node u i . For each node v ∈ B t (d i /2), we have v → {u 0 , . . . , u i-1 } and thus from Observation 2(d),

Pr(v → u i ) ≥ Pr K( ,n,1) (v → u i ). It follows Pr(B t (d i /2) → u i ) ≥ Pr K( ,n,1) (B t (d i /2) → u i ) Obs.1(g) ≥ Pr K( ,n,1) (u i → B t (d i /2))/2 Obs.1(c) = Θ (1/ ln n),
and thus Pr(d i+1 ≤ d i /2) = Ω (1/ ln n). This completes the proof of Claim 1 and Lemma 1.

Upper bound for GreedyBiDir for 2 < α < 3

In this section we prove an upper bound of O(log α-1 n • log log n) on the expected routing time of GreedyBiDir, for any pair of nodes s,t in SW( , n, α), when 2 < α < 3.

For this range of values for α, the normalizing factor ν of distribution q k = Pr(C u = k) for choosing the number of out-contacts of a node is ν = ∑ i≥2 i 1-αi -α = Θ (1). Thus q k = Θ (k -α ) for k ≥ 2. Further, for k = 1 we have q 1 = Θ (1), because since the expectation is 2, it follows that q 1 ≥ q 3 = Θ (1). Therefore,

q k = Θ (k -α ), for all k ≥ 1.
We observe that as soon as the message reaches a node within distance d * = 2 log α-2 n from target t, Lemma 1 yields an upper bound of O(log d * • log n) = O(log α-1 n) on the remaining steps until t is reached with probability 1 -1/d * . From this, it follows that the expected number of remaining steps is also O(log α-1 n). Thus, we just need to bound the expected number of steps from source s until some node v with d(v,t) ≤ d * is reached.

Let d i denote the distance between the node that has the message after i steps and target t. We will prove the following key claim which lower bounds the probability that the distance to the target is halved in the next three steps.

Claim 2 For any i ≤ log 3 n, if d i ≥ d * /2 then Pr (d i+3 ≤ d i /2 | d i . . . d 0 ) = Ω log d i / log α-1 n .
Note that this bound requires that at most log 3 n steps have been taken. 5 Because of that, we will bound first an auxiliary quantity we define now. Let T be the minimum between log 3 n and the earliest step i for which

d i ≤ d * , i.e., T = min{log 3 n, min{i : d i ≤ d * }}. We bound E[T ] as follows. For 0 ≤ k ≤ log(n/d * ) , let i k = min{log 3 n, min{i : d i ≤ n/2 k }}. Then T ≤ i log(n/d * ) .
From Claim 2 it follows that

E[i k+1 -i k ] = 3/Ω log(n/2 k+1 )/ log α-1 n = O log α-1 n log n -(k + 1)
.

Applying the above result repeatedly yields

E[i k ] = O ∑ 1≤ j≤k log α-1 n log n -j = O log α-1 n • ln log n ,
and thus

E[T ] = O log α-1 n • ln log n .
If now T = min{i : d i ≤ d * }, then T and T are identical expect for when T > log 3 n. Hence, T ≥ T • 1 T ≤log 3 n , and we have

E[T ] = E[T • 1 T ≤log 3 n ] + E[T • 1 T >log 3 n ] ≤ E[T ] + n • Pr(T > log 3 n).
From Lemma 1 for β = 1/n, it follows T = O(log 2 n) < log 3 n with probability 1 -1/n, and thus Pr(T > log 3 n) < 1/n. From this and the inequality above,

E[T ] ≤ O log α-1 n • ln log n + n • (1/n) = O log α-1 n • ln log n .
It remains to prove Claim 2.

Proof of Claim 2

We fix the path u 0 . . . u i in the first i steps. Further, we reveal whether or not u i is an out-contact of u i-1 . If u i is not an out-contact of u i-1 and the two nodes are not grid-neighbors, then u i must be an in-contact of u i-1 , and this changes significantly the a priori probability distribution of C u i . As we explain later, we avoid handling this case directly; instead we reduce this case to the case we describe next by consider one extra step.

We study now the case in which either u i is an outcontact of u i-1 , or the two nodes are grid-neighbors. We describe four events such that if all of them occur, then it follows that d i+2 ≤ d i /2. Next we show that the probability of the intersection of these events is lower bounded by Ω log d i / log α-1 n , and thus, the same bound holds for Pr(d i+2 ≤ d i /2).

Roughly speaking, the events we consider say that the next node u i+1 is an in-contact of u i with approximately log n out-contacts, which is at distance between d i /2 and d i -√ d i from target t, and has an out-contact within distance d i /2 from t. Formally, let R :

= B t (d i - √ d i ) \ B t (d i /2
) and D := {ln n, . . . , 2 ln n}. We define the following events. E 1 : there is some node v ∈ R with C v ∈ D for which we have v → u i ; let z be the node that is closest to t among the nodes v that satisfy this event;

E 2 : z → B t (d i /2); E 3 : for all v ∈ R with C v / ∈ D we have v → u i ; E 4 : u i → R.
It is immediate that the intersection of the above four events implies d i+2 ≤ d i /2: If u i has some in-or out-contact in B t (d i /2) then we have d i+1 ≤ d i /2. Otherwise, from events E 1 , E 3 , and E 4 , it follows that u i will forward the message to node z. And by E 2 , node z will subsequently forward the message to a node in B t (d i /2).

We now bound the probability of

E 1 ∧ E 2 ∧ E 3 ∧ E 4 . Since E 4 is independent of the other events, Pr(E 1 ∧ E 2 ∧ E 3 ∧ E 4 ) = Pr(E 4 ) • Pr(E 3 ) • Pr(E 1 | E 3 ) • Pr(E 2 | E 1 , E 3 ).
We chose the order of conditioning to simplify the calculations below. We show next that each of the probabilities Pr(E 4 ), Pr(E 3 ), and Pr(E 2 | E 1 , E 3 ) is lower bounded by a positive constant, and Pr(E 1 | E 3 ) = Ω log d i / log α-1 n . It follows that Pr(E 1 ∧E 2 ∧E 3 ∧E 4 ) = Ω log d i / log α-1 n , and hence the same lower bound applies to Pr(d i+2 ≤ d i /2).

Proof that Pr(E 4 ) = Ω (1): Recall that we have fixed the path u 0 . . . u i so far. For node u i we have u i → {u 0 , . . . , u i-2 }.

We remove this conditioning using Observation 2(b),

Pr(E 4 ) = 1 -Pr(u i → R) Obs.2(b) ≥ 1 -(1 + o(1)) • Pr K( ,n,2) (u i → R) = Pr K( ,n,2) (u i → R) -o(1) = Pr K( ,n,1) (u i → R) 2 -o(1).
We will argue now that Pr K( ,n,1) (u i → R) = Ω (1), and thus Pr(E 4 ) = Ω (1), as desired. Let t be a node at distance

√ d i /2 from u i . The ball B := B t ( √ d i /2 -1) does not overlap with R, hence Pr K( ,n,1) (u i → B) + Pr K( ,n,1) (u i → R) ≤ 1. ( 4
)
We have Pr K( ,n,1) (u i → B) = Ω (ln d i / ln n) from Observation 1(d), and

Pr K( ,n,1) (u i → R) ≤ Pr K( ,n,1) (u i → B t (d i -1)) = O(ln d i / ln n),
from the same observation. Thus, Pr K( ,n,1)

(u i → B) ≥ c • Pr K( ,n,1) (u i → R),
for some constant c > 0. From this and Eq. ( 4) above, it follows Pr K( ,n,1) (u i → R) ≤ 1/(1 + c), and thus Pr K( ,n,1)

(u i → R) ≥ c/(1 + c) = Ω (1).
Proof that Pr(E 3 ) = Ω (1): We will show a stronger result instead, that Pr(U → u i ) = Ω (1) for U := B t (d u i ,t -1). For each node v ∈ U we have v → {u 0 , . . . , u i-1 }, and from Observation 2(c),

Pr(v → u i ) ≤ Pr K( ,n,3) (v → u i ).
From this it follows that Pr(U → u i ) ≤ Pr K( ,n,3) (U → u i ), and thus

Pr(U → u i ) ≥ Pr K( ,n,3) (U → u i ) = Pr K( ,n,1) (U → u i ) 3 Obs.1(h) = Ω (1).
Proof that Pr(E 2 | E 1 , E 3 ) = Ω (1): Fix z and the number C z ≥ ln n of its out-contacts. We must lower bound by Ω (1) the probability that z → B t (d i /2), given that z → u i and z → {u 0 , . . . , u i-1 }. First we observe that we can drop the assumption that z → {u 0 , . . . , u i-1 }, since it can only increase the probability for each of the C z long-range edges of u to point to a given node v ∈ {u 0 , . . . , u i-1 }, and thus to B t (d i /2). Then, from Observation 2(e) we can also drop assumption z → u i , and assume instead that z has one outcontact fewer, i.e., at least ln n-1 out-contacts. From Observation 1(c), each of these out-contacts belongs to B t (d i /2) ⊇ B t (d z,t /2) with probability at least Θ (1/ log n). Hence the probability that at least one of them belongs to B t (d i /2) is lower bounded by 1) = Ω (1).

1 -1 -Ω (1/ ln n) ln n-1 ≥ 1 -e -Ω (
Proof that Pr(E 1 | E 3 ) = Ω log d i / log α-1 n : Roughly speaking, we show that for each v ∈ R, the probability of the event that v → u i ∧ C v ∈ D equals p d(v,u i ) times Ω (1/ log α-2 n), and combine this with the result that in K( , n, 1) we have R → u i with probability Ω (ln d i / ln n).

We start by observing that conditioning on event E 3 (i.e., u i has no in-contacts v ∈ R with C v / ∈ D) increases the probability of event E 1 (i.e., u i has some in-contact v ∈ R with C v ∈ D), as it increases the probability that C v ∈ D for a given v ∈ R. Thus, we have Pr(E 1 | E 3 ) ≥ Pr(E 1 ), and it suffices to lower bound Pr(E 1 ). Let H = {u 0 , . . . , u i-1 } be the set of the first i nodes in the routing path. For each v ∈ R we have v → H, and from Bayes' Rule,

Pr(v → u i ∧C v ∈ D | v → H) = Pr(v → H | v → u i , C v ∈ D) Pr(v → H) • Pr(v → u i | C v ∈ D) • Pr(C v ∈ D) ≥ Pr(v → H | v → u i , C v = 2 log n) 1 • Pr(v → u i | C v = log n) • (|D| • q 2 log n ),
where for the last relation we used that D = {ln n, . . . , 2 ln n}, and for each probability in the numerator we chose the value from D that minimizes this probability. Next we bound the two probabilities in the last two lines above. We have

Pr(v → H | v → u i , C v = 2 log n) ≤ Pr(v → H | C v = 2 log n) ≤ 2 log n • |H| • p √ d i ≤ 2 log n • |H| • p √ d * /2 = o(1),
where for the inequality in the second line we used that the distance of v from any node in H is at least

√ d i , by R's definition. Also Pr(v → u i | C v = log n) = (1 -p d(v,u i ) ) log n ≤ e -log n•p d(v,u i ) ≤ 1 -(1 -o(1)) • log n • p d(v,u i ) ,
where for the last equality we used the facts that e -x ≤ 1x + x 2 /2 and log n • p d(v,u i ) = o(1). Combining the above yields

Pr(v → u i ∧C v ∈ D | v → H) ≥ (1 -o(1)) • (1 -o(1)) • log n • p d(v,u i ) • (|D| • q 2 log n ) = ρ • p d(v,u i ) , where ρ := (1-o(1)) 2 •log n•|D|•q 2 log n = Ω 1/ log α-2 n .
From this it follows that the probability of the event ¬E 1 that

u i has no in-contacts v ∈ R with C v ∈ D is Pr(¬E 1 ) ≤ ∏ v∈R (1 -ρ • p d(v,u i ) ) ≤ ∏ v∈R e -ρ•p d(v,u i ) = e -ρ ∑ v∈R p d(v,u i ) .
We compare this with the probability in K( , n, 1) that u i has no in-contacts v ∈ R,

Pr K( ,n,1) (R → u i ) = ∏ v∈R (1 -p d(v,u i ) ) ≥ ∏ v∈R e -p d(v,u i ) /2 = e -(1/2)•∑ v∈R p d(v,u i ) ,
where for the inequality we used the fact that 1x ≥ e -x-x 2 when 0 ≤ x ≤ 1/2, and p d(v,u i ) = o(1). Further, we have

Pr K( ,n,1) (R → u i ) Obs.1(g) ≥ Pr K( ,n,1) (u i → R)/2 = Pr K( ,n,1) (u i → B t (d i -d i ))/2 -Pr K( ,n,1) (u i → B t (d i /2))/2 Obs.1(b) = &(c) Ω (ln d i / ln n) -Θ (1/ ln n) = Ω (ln d i / ln n).
Combining the last three results above yields

Pr(¬E 1 ) ≤ Pr K( ,n,1) (R → u i ) 2ρ ≤ (1 -Ω (ln d i / ln n)) 2ρ ≤ e -Ω (ρ ln d i / ln n) ,
and substituting the value of ρ gives Pr(¬E 1 ) ≤ e -Ω (ln

d i / ln α-1 n) = 1 -Ω (ln d i / ln α-1 n).
Thus, Pr(E 1 ) = Ω (ln d i / ln α-1 n), as desired.

We have now completed the proof for the case in which either u i is an out-contact of u i-1 , or the two nodes are gridneighbors. We have shown for this case that

Pr (d i+2 ≤ d i /2) = Ω log d i / log α-1 n .
We consider now the case in which u i is neither an outcontact nor a grid-neighbor of u i-1 , and thus it is an incontact of u i-1 . Fix the out-contacts of u i , and let w be the out-contact or grid-neighbor of u i that is closest to t. If d w,t ≤ d i /2 then d i+1 ≤ d i /2 as desired; so, we assume that d w,t > d i /2. The probability that u i has no in-contacts in B t (d w,t -1) is Pr(B t (d w,t -1) → u i ) = Ω (1); the proof of this result is the same as that for Pr(E 3 ) = Θ (1), described earlier. Given now that B t (d w,t -1) → u i , the next node u i+1 in the path is node w, and we can apply the results of the previous case to obtain that Pr

(d i+3 ≤ d i+1 /2) = Ω log d i+1 / log α-1 n = Ω log d i / log α-1 n , as d i+1 = d w,t > d i /2. It follows that Pr (d i+3 ≤ d i /2) ≥ Θ (1)
• Ω log d i / log α-1 n . This completes the proof of this case, and the proof of Claim 2.

Upper bound for GreedyBiDir for α = 2

In this section we prove an upper bound of O(log 4/3 n) on the expected routing time of GreedyBiDir, for any pair of nodes s,t in SW( , n, 2). The analysis is similar to that for SW( , n, α) with 2 < α < 3, in Section 4.2. Arguments that are the same in both proofs are not repeated here.

For α = 2, the normalizing factor ν of the probability distribution

q k = Pr(C u = k) is ν = ∑ 2≤i≤k max i -1 -i -2 = Θ (ln k max ) = Θ (ln n),

and thus

q k =    Θ 1 k 2 ln n , if k ≥ 2; 1 -Θ 1 ln n , if k = 1.
As in Section 4.2, we use Lemma 1 to argue that the expected number of remaining steps when the message has reached a node within distance

d * = 2 log 1/3 n of t, is bounded by O(log d * • log n) = O(log 4/3 n).
Next we bound the expected number of steps from source s until some node v with d(v,t) ≤ d * is reached.

Led d i be the distance between the node that has the message after i steps and target t. The next result is the analogue to Claim 2; we give its proof later.

Claim 3 Let ε be an arbitrary constant such that 1 -

1/(3 ) < ε < 1. If i ≤ log 3 n and d i ≥ (d * ) ε , then Pr (d i+3 ≤ d ε i | d i . . . d 0 ) = Ω log 2 d i / log 2 n .
As before we let T = min{log 3 n, min{i : , let i k = min{log 3 n, min{i :

d i ≤ d * }}
d i ≤ n ε k }}.
Hence, T ≤ i k * . From Claim 3 then it follows that

E[i k+1 -i k ] = 3/Ω log 2 n ε k+1 / log 2 n = O ε -2(k+1) .
Applying the above result repeatedly yields

E[i k ] = O ∑ 1≤ j≤k ε -2k = O ε -2k ,
and thus

E[T ] ≤ E[i k * ] = O ε -2 log 1/ε log n log d * = O log n log d * 2 = O log n log 1/3 n 2 = O log 4/3 n .
Letting now T = min{i :

d i ≤ d * }, we argue that E[T ] ≤ E[T ] + O(1)

Proof of Claim 3

The proof is very similar to that of Claim 2. As before, we fix the path u 0 . . . u i in the first i steps, and we consider first the case in which either u i is an out-contact of u i-1 , or the two nodes are grid-neighbors. We consider the same four events we used in the proof of Claim 2, but for different sets R and D. We let

R := B t (d i - √ d i ) \ B t (d ε i ) and D := {d ε 1 i , . . . , d ε 2 i },
where ε 1 and ε 2 are arbitrary constants with 1/3 < ε 1 < ε 2 < 1/2. Then, E 1 : there is some node v ∈ R with C v ∈ D for which we have v → u i ; let z be the node that is closest to t among the nodes v that satisfy this event;

E 2 : z → B t (d ε i ); E 3 : for all v ∈ R with C v / ∈ D we have v → u i ; E 4 : u i → R.
By the same reasoning as in the proof of Claim 2, we have that the probability of d i+2 ≤ d ε i is lower bounded by the probability of the intersection of the four events above, and

Pr(E 1 ∧ E 2 ∧ E 3 ∧ E 4 ) = Pr(E 4 ) • Pr(E 3 ) • Pr(E 1 | E 3 ) • Pr(E 2 | E 1 , E 3 ).
We show that Pr(E 4 ), Pr(E 3 ), and Pr(E 2 | E 1 , E 3 ) are Ω (1), as before, and that Pr(

E 1 | E 3 ) = Ω log 2 d i / log 2 n . It follows that Pr(E 1 ∧ E 2 ∧ E 3 ∧ E 4 ) = Ω log 2 d i / log 2 n ,
and hence the same bound applies to Pr(d i+2 ≤ d ε i ). Proof that Pr(E 4 ) = Ω (1) and Pr(E 3 ) = Ω (1): The derivations of these two bounds described in the proof for Claim 2 apply also in the current setting without changes.

Proof that Pr(E 2 | E 1 , E 3 ) = Ω (1): Fix z and C z ≥ d ε 1
i . From the same argument as in the proof for Claim 2, it suffices to lower bound by Ω (1) the probability that z → B t (d ε i ) assuming that z has at least C z -1 ≥ d ε 1 i -1 outcontacts (without the assumptions that z → u i and z → {u 0 , . . . , u i-1 }). From Observation 1(b) it follows that each of these out-contacts belongs to B t (d ε i ) with probability

Ω d ε i d z,t / ln n ≥ Ω d ε i d i / ln n = Ω d -(1-ε) i / ln n .
Hence the probability that at least one of the out-contacts belongs to B t (

d ε i ) is lower bounded by 1 -1 -Ω d -(1-ε) /ln n d ε 1 i -1 ≥ 1 -e -Ω d ε 1 i d -(1-ε) i /ln n = 1 -o(1),
where the last relation holds because

ε 1 > 1/3 > (1 -ε) .
Proof that Pr(E 1 | E 3 ) = Ω log 2 d i / log 2 n : As explained in the proof for Claim 2, we have Pr(E 1 | E 3 ) ≥ Pr(E 1 ) and thus it suffices to lower bound Pr(E 1 ). For each node v ∈ R and for H = {u 0 , . . . , u i-1 } we have

Pr(v → u i ∧C v ∈ D | v → H) = ∑ k∈D Pr(v → u i ∧C v = k | v → H) = ∑ k∈D Pr(v → H | v → u i , C v = k) Pr(v → H) • Pr(v → u i | C v = k) • Pr(C v = k) .
For k ∈ D,

Pr(v → H | v → u i , C v = k) ≤ Pr(v → H | C v = k) ≤ |H| • kp √ d i = O log 3 n • d ε 2 i / ln n • d i = o(1),
where the last relation holds because

ε 2 < 1/2 ≤ /2. Also Pr(v → u i | C v = k) = (1 -p d(v,u i ) ) k ≤ e -kp d(v,u i ) = 1 -(1 -o(1)) • kp d(v,u i ) ,
where for the last equality we used the facts that e -x ≤ 1

-x + x 2 /2 and kp d(v,u i ) ≤ kp √ d i = o(1). Finally, we have Pr(C v = k) = q k = Θ (1/(ln n • k 2 )). Combining the above yields Pr(v → u i ∧C v = k | v → H) ≥ ∑ k∈D (1 -o(1)) • (1 -o(1)) • kp d(v,u i ) • q k 1 = ρ • p d(v,u i ) ,
where

ρ := (1 -o(1)) ∑ k∈D kq k = Θ ∑ k∈D 1 ln n • k = Θ ln d ε 2 i -ln d ε 1 i ln n = Θ ln d i ln n .
In the proof of Claim 2, we showed that Pr(¬E 1 ) ≤ e -Ω (ρ ln d i / ln n) . Substituting ρ's value gives

Pr(¬E 1 ) ≤ e -Ω (ln 2 (d i )/ ln 2 n) = 1 -Ω (ln 2 (d i )/ ln 2 n).
Thus, Pr(E 1 ) = Ω (ln 2 (d i )/ ln 2 n).

This completes the proof for the case in which either u i is an out-contact of u i-1 , or the two nodes are grid-neighbors. The proof of the complementary case, in which u i is neither an out-contact nor a grid-neighbor of u i-1 , follows from the previous case as explained in the proof of Claim 2.

We have thus finished the proof of Claim 3.

Proof of the lower bounds

We prove now the lower bounds of Theorem 2. For GreedyUniDir we consider the logarithm of the distances d 0 , d 1 , . . . , where d i is the distance to the target after i steps.

We show that the expected decrease of this quantity in a step is µ = O(1/ log n), and then apply Wald's Theorem to obtain a lower bound of Ω (log d 0 /µ) on the expected routing time.

For GreedyBiDir we consider a slightly difference sequence of distances, in order to decrease the dependency on the past. Roughly speaking, if the node u i that has the message after i rounds is not an in-contact of u i-1 then, as before, d i is the distance between u i and the target. But if u i is an in-contact of u i-1 then d i is instead the minimum distance of u i and its out-contacts from the target. Similar to GreedyUniDir, we bound the expected decrease in the logarithm of this distance in a step, and then apply Wald's Theorem. The bound we establish on this decrease is in terms of the distribution of d i , i.e., Pr(d i ≤ r | d i-1 = δ ). To bound this probability we must bound the probability of the event that u i is an in-contact of u i-1 and has an out-contact at distance at most r from the target. Bounding this "two-hop" probability is a main component of our analysis.

In Section 5.1 we describe our proof technique. In Section 5.2 we show the lower bound for GreedyUniDir. In Section 5.3 we define the sequence of distances to be used in the analysis of GreedyBiDir, and then derive the lower bounds for GreedyBiDir in Sections 5.4-5.8.

The method

In this section we describe the steps that we follow to prove the lower bounds. These steps, or slight variations of them, are used for all the cases of the theorem, except if stated otherwise.

Let s be the source and t the target nodes, and let u i be the node that has the message after the first i steps of routing.

Step 1 We describe a sequence d 0 , d 1 , . . . of distances to target t, such that d 0 = d(s,t), and d i ≤ d(u i ,t) for each i ≥ 1. Hence, the routing time for s,t is lower bounded by min{i : d i = 0}. For the case of GreedyUniDir we define d i simply as d i = d(u i ,t). For GreedyBiDir the definition of d i is a bit more involved and is given in Section 5.3.

Step 2 We bound the distribution of d i . Specifically, we compute a function f (r, δ ) such that for any δ > ln n and 1 ≤ r ≤ δ -1 we have

Pr(d i ≤ r | d i-1 = δ ) ≤ f (r, δ ).
Step 3 We bound the expected decrease in a step, of the logarithm of distance d i . Let

l i = ln d i , if d i ≥ 1; 0, if d i = 0.
Further, for i ≥ 1, let ∂ l i be the decrease of this quantity in step i, i.e.,

∂ l i = l i-1 -l i = ln(d i-1 /d i ), if d i ≥ 1; ln(d i-1 ), if d i-1 > d i = 0.
We compute some µ > 0 such that if

d i-1 > ln n then E[∂ l i | d i-1 ] ≤ µ.
We use the next claim, which bounds

E[∂ l i | d i-1 ] in terms of function f from Step 2. Claim 4 If δ > ln n then E[∂ l i | d i-1 = δ ] ≤ ∑ 1≤r≤δ -1 f (r, δ )/r.
Proof Suppose d i-1 = δ . We have

E[∂ l i ] = ∑ 1≤r≤δ -1 Pr(d i = r) • ln(δ /r) + Pr(d i = 0) • ln(δ ) = ∑ 1≤r≤δ -1 Pr(d i ≤ r) -Pr(d i ≤ r -1) • ln(δ /r) + Pr(d i = 0) • ln(δ ) = ∑ 1≤r≤δ -1 Pr(d i ≤ r) • ln(δ /r) -∑ 1≤r≤δ -1 Pr(d i ≤ r -1) • ln(δ /r) + Pr(d i = 0) • ln(δ ) = ∑ 1≤r≤δ -1 Pr(d i ≤ r) • ln(δ /r) -∑ 2≤r≤δ -1 Pr(d i ≤ r -1) • ln(δ /r) = ∑ 1≤r≤δ -1 Pr(d i ≤ r) • ln(δ /r) -∑ 1≤r≤δ -2 Pr(d i ≤ r) • ln(δ /(r + 1)) = ∑ 1≤r≤δ -1 Pr(d i ≤ r) • ln(δ /r) -∑ 1≤r≤δ -1 Pr(d i ≤ r) • ln(δ /(r + 1)) = ∑ 1≤r≤δ -1 Pr(d i ≤ r) • ln((r + 1)/r) ≤ ∑ 1≤r≤δ -1 Pr(d i ≤ r) • (1/r).
Step 4 We lower bound the expected number of steps until we have d i ≤ ln n, by using the bound

E[∂ l i | d i-1 ] ≤ µ ob- tained in
Step 3 and Wald's Theorem. Let T s,t = min{i : d i ≤ ln n}, and consider the sum ∑ 1≤i≤T s,t ∂ l i = l 0l T s,t . By definition, d T s,t ≤ ln n. Thus l T s,t ≤ ln ln n, and

∑ 1≤i≤T s,t ∂ l i ≥ ln(d 0 / ln n). Further, since E[∂ l i | i ≤ T s,t ] = E[E[∂ l i | d i-1 ] | i ≤ T s,t ] ≤ µ from Step 3, Wald's Theorem gives E ∑ 1≤i≤T s,t ∂ l i ≤ E[T s,t ] • µ.
From the two inequalities above it follows

E[T s,t ] ≥ ln(d 0 / ln n)/µ. (5)
Step 5 We observe that for a uniformly random pair s,t, it holds that d(s,t) = n Ω (1) with probability 1o(1). Then from the result of Step 4 it follows that the expected routing time T for a random pair s,t is

E[T ] = Ω (ln(n)/µ). ( 6
)
This step is not used for the case of GreedyBiDir when α ≤ 2, as in this case we bound the expected routing time for the worst-case pair only.

Lower bound for GreedyUniDir

We prove a lower bound of Ω (log 2 n) on the expected routing time of GreedyUniDir for a random pair s,t in SW( , n, α). This bound holds for all α ≥ 0. We follow the steps listed in Section 5.1. For δ > ln n and 1 ≤ r ≤ δ -1, we define

f (r, δ ) = c • ln δ δ -r / ln n, if 1 ≤ r ≤ δ -2; 1, if r = δ -1,
for a constant c > 0. We argue now that if c is sufficiently large, then Pr(

d i ≤ r | d i-1 = δ ) ≤ f (r, δ ) as required (cf.
Step 2): Fix node u i-1 and assume that d i-1 = δ . Suppose also that r = δ -1 (because f (δ -1, δ ) = 1, and thus the desired inequality holds for r = δ -1). We have

Pr(d i ≤ r) = Pr(u i → B t (r))
Obs.2(a)

≤ 2Pr K( ,n,1) (u i → B t (r))
Obs.1(a)

= O ln δ δ -r / ln n .

Therefore, Pr(d i ≤ r) ≤ f (r, δ ) for a large enough constant c.

Next we use Claim 4 to bound

E[∂ l i | d i-1 = δ ] (cf. Step 3). E[∂ l i | d i-1 = δ ] ≤ ∑ 1≤r≤δ -1 f (r, δ )/r = ∑ 1≤r≤δ -2 c r • ln δ δ -r / ln n + 1 δ -1 .
To bound the last sum we observe that

∑ 1≤r≤δ /2 1 r • ln δ δ -r = ∑ 1≤r≤δ /2 1 r • ln 1 + r δ -r ≤ ∑ 1≤r≤δ /2 1 r • r δ -r ≤ ∑ 1≤r≤δ /2 1 δ -δ /2 = O(1); (8)
∑ δ /2<r≤δ -2 1 r • ln δ δ -r ≤ 1 δ /2 • ∑ δ /2<r≤δ -2 ln δ δ -r ≤ 1 δ /2 • ln δ δ /2 δ /2 ! ≤ 1 δ /2 • ln δ δ /2 (δ /2e) δ /2
(by Stirling's Approximation)

≤ 1 δ /2 • O(δ ) = O(1). (9)
It follows that

E[∂ l i | d i-1 = δ ] = O(c/ ln n) + 1/(δ -1) = O(1/ ln n).
We have thus shown that if

d i-1 > ln n then E[∂ l i | d i-1 ] ≤ µ for some µ = O(1/ ln n).
We can now apply Eq. ( 6) (cf. Step 5) to conclude that the expected routing time for a random pair is E[T ] = Ω (ln(n)/µ) = Ω (ln 2 n).

Distance sequence for GreedyBiDir

In the analysis of GreedyBiDir we will use a different definition for the distances d i than in the analysis of GreedyUniDir, where d i was just the distance between node u i that has the message after i steps and target t.

Below we will write d(U,t) for a node set U to denote the minimum distance between some node from U and t, i.e., d(U,t) = min v∈U d(v,t). Further, by N out (v) we denote the set of out-contacts of v. For each i ≥ 0, let

r i = d ({u i } ∪ N out (u i ), t) , if u i → u i-1 ; d (u i , t) , otherwise;
i.e., if u i is an in-contact of the previous node in the routing path, then r i is the minimum distance of u i and its outcontacts from the target; otherwise, r i is just the distance of u i from the target. Then we define d 0 = r 0 = d(s,t), and for i ≥ 1,

d i = min r i , 1 - 1 ln n • d i-1 .
The second quantity inside min{} ensures that d i ≤ d i-1 -1 when d i-1 > 0, and also that d i = 0 after at most i = O(log 2 n) steps. The latter is useful for the analysis because when the set of nodes visited grows very large it affects significantly the edge distribution of nodes not visited yet. From the definitions above it is immediate that d i ≤ r i ≤ d(u i ,t). Hence, for any node pair s,t the routing time of GreedyBiDir is lower bounded by min{i : d i = 0}. We have thus completed Step 1 of the analysis for GreedyBiDir (cf. Section 5.1). For Step 2 we must bound the distribution of d i ; we use the next result.

Claim 5 For any b ≥ δ > ln n and 1 ≤ r < 1 -1 ln n δ we have

Pr(d i ≤ r | d i-1 = δ , d(u i-1 ,t) = b) = O ln δ δ -r / ln n + f 2-hop (r, b) , where f 2-hop (r, b) := b-1 ∑ j=r+1 ∑ k≥2 min q k j -1 , kq k ln n • (b -j)
• min 1, k ln j j-r / ln n .

In the above upper bound on the probability of d i ≤ r, the O ln δ δ -r / ln n term bounds the probability that u i belongs to B t (r); this term is the same as the bound we used for the case of GreedyUniDir (cf. Eq. ( 7)). The term O( f 2-hop (r, b)) bounds the probability that u i → u i-1 and some out-contact of u i belongs to B t (r). Intuitively, in the definition of f 2-hop (r, b), the quantities q k j -1 and kq k ln n•(b-j) are upper bounds on the probability of the event that u i-1 has some in-contact v with C v = k on the sphere S t ( j). The quantity k ln j j-r / ln n then bounds the probability that a given node v ∈ S t ( j) with C v = k has an out-contact in B t (r).

In the following sections we will bound f 2-hop for the different values of α. Bounds for f 2-hop that are larger than O ln δ δ -r / ln n will yield lower bounds for the routing time that are smaller than Ω (ln 2 n).

Proof of Claim 5

We fix the path u 0 . . . u i-1 , and also the outcontacts and in-contacts of each of the nodes u 0 , . . . , u i-2 . Further, we reveal whether u i-1 → u i-2 holds, and if it does, we fix the out-contacts of u i-1 . From these we can also compute d 0 , . . . , d i-1 . Suppose that d(u i-1 ,t) = b and d i-1 = δ .

First we bound the probability that u i-1 has some outcontact in B t (r). If u i-1 → u i-2 then this probability is zero, as by definition in this case we have d(N out (u i-1 ), t) ≥ r i-1 ≥ d i-1 = δ > r. Hence, we assume that u i-1 → u i-2 (or i = 1). We have u i-1 → H := {u 0 , . . . , u i-2 }, and thus Pr(u i-1 → B t (r))

Obs.2(b) ≤ (1 + o(1)) • Pr K( ,n,2) (u i-1 → B t (r)) Obs.1(a) = O ln b b-r / ln n = O ln δ δ -r / ln n ,
where the last relation holds because δ ≤ b and the function x/(xr) is decreasing for x > r.

Next we establish the same bound for the probability that u i-1 has some in-contact in B t (r). For each v ∈ B t (r) we have v → H, and from Observation 2(c), Pr(v → u i-1 ) ≤ Pr K( ,n,3) (v → u i-1 ). From this it follows that Pr(B t (r) → u i-1 ) ≤ Pr K( ,n,3) (B t (r) → u i-1 ), and thus Pr(B t (r) → u i-1 ) ≤ 3 Pr K( ,n,1) (B t (r) → u i-1 )

Obs.1(g)

≤ 3 Pr K( ,n,1) (u i-1 → B t (r)) Obs.1(a) = O ln b b-r / ln n = O ln δ δ -r / ln n ,
as before. Last, we bound the probability that u i-1 has some incontact v for which r < d(v,t) < b and v → B t (r). For each node v with d(v,t) < b we have v → H; we make this explicit as conditioning in the probability statements below, so that we can remove this condition. We have

Pr(v → u i-1 ∧ C v = k | v → H) Obs.2(b) ≤ 2 Pr(v → u i-1 ∧ C v = k) = 2q k • Pr(v → u i-1 | C v = k) ≤ 2q k • min{1, kp d(v,u i-1 ) }.
Let O j,k , for r < j < b and k ≥ 2, be the set of nodes v ∈ S t ( j) with C v = k that are in-contacts of u i-1 , i.e., O j,k = {v ∈ S t ( j) :

C v = k, v → u i-1 }. We have E[|O j,k |] = ∑ v∈S t ( j) Pr(v → u i-1 ∧ C v = k | v → H) ≤ 2q k ∑ v∈S t ( j) min{1, kp d(v,u i-1 ) } ≤ 2q k • min |S t ( j)|, ∑ v∈S t ( j) kp d(v,u i-1 ) .
Also, |S t ( j)| = O( j -1 ) from Eq. (1) on page 7, and

∑ v∈S t ( j) p d(v,u i-1 ) = Pr K( ,n,1) u i-1 → S t ( j) Obs.1(e) = O 1 ln n•(b-j) .
Therefore,

E[|O j,k |] = O q k • min j -1 , k ln n•(b-j)
.

We now bound the probability that a given node from O j,t has an out-contact in B t (r). For each v ∈ S t ( j), we have

Pr(v → B t (r) | C v = k, v → u i , v → H) ≤ Pr(v → B t (r) | C v = k, v → H) Obs.2(f) ≤ Pr(v → B t (r) | C v = k) Pr(v → H | C v = 1) Obs.1(f) = Pr(v → B t (r) | C v = k)/(1 -o(1)) ≤ k • Pr(v → B t (r) | C v = 1)/(1 -o(1))
Obs.1(e)

= O k ln j j-r / ln n .

From the two results above it follows that the expected number of in-contacts v of u i-1 for which r

< d(v,t) < b and v → B t (r) is upper bounded by b-1 ∑ j=r+1 ∑ k≥2 E[|O j,k |] • min 1, O k ln j j-r / ln n = O b-1 ∑ j=r+1 ∑ k≥2 min q k j -1 , kq k ln n • (b -j) • min 1, k ln j j-r / ln n ;
and by Markov's Inequality the same upper bounds applies to the probability that at least one such v exists.

Combining the last bound with the bounds for Pr(B t (r) → u i-1 ) and Pr(u i-1 → B t (r)) shown earlier, and using the union bound completes the proof of Claim 5.

Lower bound for GreedyBiDir for α > 3

We prove a lower bound of Ω (log 2 n) on the expected routing time of GreedyBiDir for a random pair s,t in SW( , n, α), when α > 3.

First we bound the distribution of d i (cf.

Step 2 in Section 5.1). We will use Claim 5, and thus we must compute an upper bound for f 2-hop . From the definition of f 2-hop , it follows that for any integers δ , b, r for which ln

n < δ ≤ b ≤ d 0 = d(s,t) and 1 ≤ r < 1 -1 ln n δ , f 2-hop (r, b) ≤ b-1 ∑ j=r+1 ∑ k≥2 kq k ln n • (b -j) • k ln j j-r / ln n = 1 ν ln 2 n b-1 ∑ j=r+1 1 b -j • ln j j-r • ∑ k≥2 1 k α-2 . Since α > 3, the normalizing factor ν is Θ (1) and ∑ k≥2 1 k α-2 = Θ (1). Further, we show below that b-1 ∑ j=r+1 1 b -j • ln j j-r = O ln n • ln δ δ -r . ( 10
)
It follows

f 2-hop (r, b) = O ln δ δ -r / ln n . Claim 5 then yields that Pr(d i ≤ r | d i-1 = δ ) = O ln δ δ -r / ln n , for 1 ≤ r < 1 -1 ln n δ
, which is the same bound as the one we had for GreedyUniDir (cf. Eq. ( 7) in Section 5.2). Thus the following definition for f satisfies Step 2 for a sufficiently large constant c > 0,

f (r, δ ) = c ln δ δ -r / ln n, if 1 ≤ r < 1 -1 ln n δ ; 1, if 1 -1 ln n δ ≤ r ≤ δ -1. (11)
Next, from Claim 4 (cf.

Step 3) it follows

E[∂ l i | d i-1 = δ ] ≤ ∑ 1≤r≤δ -1 f (r, δ )/r = ∑ 1≤r< 1-1 ln n δ c r ln δ δ -r / ln n + ∑ 1-1 ln n δ ≤r≤δ -1 1 r .
Both sums in the last line are O(1/ ln n): the first one because of Eq. ( 8) and ( 9) in Section 5.2, and the second because it is

O δ ln n • 1 δ = O(1/ ln n). Thus, E[∂ l i | d i-1 ] ≤ µ for some µ = O(1/ ln n),
and from Eq. ( 6) (cf. Step 5) we conclude that the expected routing time for a random pair is E

[T ] = Ω (ln(n)/µ) = Ω (ln 2 n).
Proof of Eq. (10) We distinguish two cases.

Case r ≤ δ /2: b-1 ∑ j=r+1 1 b -j • ln j j-r = b-1 ∑ j=r+1 1 b -j • ln 1 + r j-r ≤ b-1 ∑ j=r+1 1 b -j • r j -r = 2 (b+r)/2 ∑ j=r+1 1 b -j • r j -r (by symmetry) ≤ 2 (b+r)/2 ∑ j=r+1 2 b -r • r j -r (we set j = (b + r)/2 in the first fraction) = O r b -r • ln(b -r) = O r δ -r • ln n .
Finally, to obtain [START_REF] Dietzfelbinger | Tight bounds for blind search on the integers[END_REF] we observe that r δ -r ≤ log δ δ -r : we have δ δ -r = 1 + r δ -r ≥ 2 r/(δ -r) , because 1 + x ≥ 2 x for 0 ≤ x ≤ 1, and r δ -r ≤ δ /2 δ -δ /2 = 1.

Case r > δ /2: We break the sum into two sums, for i ≤ (b + r)/2 and i > (b + r)/2.

(δ + r) • (δ -r) ≤ δ 2 , which is equivalent to δ 2 -r 2 ≤ δ 2 .
This completes the proof of Eq. (10).

Lower bound for GreedyBiDir for α = 3

We prove a lower bound of Ω (log 2 n/ log log n) on the expected routing time of GreedyBiDir for a random pair s,t in SW( , n, 3). The difference from the case of SW( , n, α) with α > 3, is that the bound we will show for f 2-hop will be larger by a factor of O(log log n), and consequently the bound on the routing time will be smaller by a factor of 1/O(log log n). To bound f 2-hop we distinguish between nodes with at most ln 2 n out-contacts, and nodes with more out-contacts. From the definition of f 2-hop in Claim 5, it follows that for ln n <

δ ≤ b ≤ d 0 and 1 ≤ r < 1 -1 ln n δ , f 2-hop (r, b) ≤ b-1 ∑ j=r+1 ∑ k≥2 kq k ln n • (b -j) • min 1, k ln j j-r / ln n ≤ b-1 ∑ j=r+1 ln 2 n ∑ k=2 kq k ln n • (b -j) • k ln j j-r / ln n + b-1 ∑ j=r+1 ∑ k>ln 2 n kq k ln n • (b -j) • 1 = 1 ν ln 2 n b-1 ∑ j=r+1 1 b -j • ln j j-r • ln 2 n ∑ k=2 1 k + 1 ν ln n b-1 ∑ j=r+1 1 b -j • ∑ k>ln 2 n 1 k 2 .
We bound the quantities in the last two lines: ν

= Θ (1); ∑ b-1 j=r+1 1 b-j ln j j-r = O ln n • ln δ δ -r , from Eq.(10); ∑ ln 2 n k=2 1 k = O(ln ln n); ∑ b-1 j=r+1 1 b-j = O(ln n); and ∑ k>ln 2 n 1 k 2 = O(1/ ln 2 n). Applying these above yields f 2-hop (r, b) = O ln ln n • ln δ δ -r / ln n .
From Claim 5 it follows that the same bound holds for Pr(d i ≤ r | d i-1 = δ ). Thus we can define f (r, δ ) as

c ln ln n • ln δ δ -r / ln n, if 1 ≤ r < 1 -1 ln n δ ; 1, if 1 -1 ln n δ ≤ r ≤ δ -1.
Applying now Claim 4 as in Section 5.4, and observing that the above definition of f (r, δ ) differs from the one in Eq. ( 11) by an O(ln ln n) factor, we obtain that E[∂ l i | d i-1 ] ≤ µ for some µ = O(ln ln n/ ln n). Finally, from Eq. ( 6) it follows that the expected routing time for a random pair is E[T ] = Ω (ln n/µ) = Ω (ln 2 n/ ln ln n).

5.6

Lower bound for GreedyBiDir for 2 < α < 3

We prove a lower bound of Ω (log α-1 n) on the expected routing time of GreedyBiDir for a random pair s,t in SW( , n, 3), when 2 < α < 3.

In this case the computations needed to bound f 2-hop are a bit more involved than in the previous two cases. From the definition of f 2-hop in Claim 5, it follows that for ln n < δ ≤ b ≤ d 0 and 1 ≤ r < 1 -1 ln n δ , and for k j := ln n/ln j j-r , .

Further, we will show similar to Eq. ( 10) that b-1

∑ j=r+1 1 b -j • ln α-2 j j-r =      O ln n • r δ α-2 , if 1 ≤ r ≤ δ /2; O ln n • ln δ δ -r , if δ /2 < r ≤ δ -1. (12)
Therefore, f 2-hop (r, b) is

     O r δ α-2 / ln α-2 n , if 1 ≤ r ≤ δ /2;
O ln δ δ -r / ln α-2 n , if δ /2 < r < 1 -1 ln n δ . ] ≤ µ for some µ = O(1/ ln α-2 n), and from Eq. ( 6) we conclude that the expected routing time for a random pair is E[T ] = Ω (ln(n)/µ) = Ω (ln α-1 n).

Proof of Eq. [START_REF] Dodds | An experimental study of search in global social networks[END_REF] The proof is similar to that of Eq. [START_REF] Dietzfelbinger | Tight bounds for blind search on the integers[END_REF]. We show that when α < 2, the expected routing time of GreedyUniDir in SW( , n, α) is Ω (log 2 n) for some pairs s,t.

The normalizing factor ν of distribution q k is a polynomial function of n in this case. Specifically, we have ν = ∑ 2≤i≤k max i 1-αi -α = Θ (k max ) 2-α , where k max = n γ and 0 < γ ≤ is a constant. It follows that the probability 1p 1 for a node v to have more than one out-contacts is polynomially small. As a result, with probability Ω (1) the message visits only nodes v with C v = 1, if d(s,t) is a sufficiently small polynomial in n.

The above intuition is captured by a simple bound on f 2-hop we show next. From the definition of f 2-hop in Claim 5, it follows that for ln n < δ ≤ b ≤ d 0 and 1 ≤ r < 1 -1 ln n δ ,

f 2-hop (r, b) ≤ d 0 -1 ∑ j=r+1 k max ∑ k=2 q k j -1 • 1 = d 0 -1 ∑ j=r+1 j -1 k max ∑ k=2 1 νk α = O d 0 (k max ) 2-α k max ∑ k=2 1 k α ,
and thus

f 2-hop (r, b) =      O d 0 /(k max ) 2-α , if 1 < α < 2; O d 0 • ln(k max )/k max , if α = 1; O d 0 /k max , if 0 ≤ α < 1.
Therefore, if 6d 0 ≤ λ := k Step 4) we conclude that the expected routing time for a pair s,t with d(s,t) = λ is Ω (ln(λ / ln n)/µ) = Ω (ln 2 n).

Lower bound for

GreedyBiDir for α = 2

We show that for some pairs s,t in SW( , n, 2) the expected routing time of GreedyBiDir is Ω (log 4/3 n).

Recall from Section 4.3 that ν = Θ (ln n) in this case, and thus the probability q 1 that a node has only one out-contact is 1 -Θ (1/ ln n).

We will prove the lower bound for a pair s,t for which d(s,t) = λ := 2 ln 1/3 n . From the definition of f 2-hop in Claim 5, it follows that for ln n < δ ≤ b ≤ d 0 and 1 ≤ r < 1 -1 ln n δ , Except for ∑ c ln 2 λ r ln 2 n , we have already seen that all the sums in the last two lines are O(1/ ln n), e.g., in the analysis of case α > 3. Further, we have Step 4) we conclude that the routing time for pair s,t is Ω (ln(λ / ln n)/µ) = Ω (ln 3/4 n).

Power-law exponent α Exponent of log n in the expected routing time 4 / 3 Fig. 1

 431 Fig. 1 Summary of our results.

  (c), (d): Both results follow from (a) and (b).(e): This result is a special case of[START_REF] Martel | Analyzing Kleinberg's (and other) small-world models[END_REF] Fact 5].

  , and we bound E[T ] as follows. For each 0 ≤ k ≤ k * := log 1/ε log n log d *

  in exactly the same way as in Section 4.2. Hence, we obtain E[T ] = O log 4/3 n . It remains to prove Claim 3.

(

  • ln b = O(ln b) = O(ln n). we set j = (b + r)/2 in the second fraction) = O(ln(br)) • ln b+r b-r = O ln n • ln b+r b-r . To obtain (10) it suffices to prove that b+r b-r ≤ δ δ -r 2 : we have b+r b-r ≤ δ +r δ -r and δ +r δ -r ≤ δ δ -r 2 , where the latter holds because is equivalent to

f 2 - 1 .

 21 hop (r, b) n • (bj) • min 1, k ln j j-r / ln n = We have ν = Θ (1), ∑ 2≤k≤k j 1 k α-2 = O(k 3-α j), and∑ k>k j 1 k α-1 = O(1/k α-2 j). Applying these above and plug-ging the value of k j = ln n/ln j j-r yields f 2-hop (r, b)

From this and Claim 5 , 2 / 1 f 1 δ

 5211 it follows Pr(d i ≤ r | d i-1 = δ ) ≤ f (r, δ ) for δ > ln n and 1 ≤ r ≤ δ -1, if f (r, δ ) is ln α-2 n, if 1 ≤ r ≤ δ /2; c • ln δ δ -r / ln α-2 n, if δ /2 < r < 1 -1 ln n δ ; 1, if 1 -1 ln n δ ≤ r ≤ δ -1. Then from Claim 4 we have E[∂ l i | d i-1 = δ ] ≤ ∑ 1≤r≤δ -All the three sums above are O(1/ ln α-2 n): the first one because∑ α-2 O(δ α-2 ) = O(1); the second one because of Eq. (8) and (9) in Section 5.2; and the third one is O δ ln n • 1 δ = O(1/ ln n). Therefore, E[∂ l i | d i-1

Case r ≤ δ / 2 : 2 ( 2 ( 2 = O ln n • r δ α- 2 .r > δ / 2 :=.

 222222 the sum of the first half terms is smaller than the other half) we set j = (b + r)/2 in the second fraction)= O ln(br) • 2r br α-Case We break the sum into two sums, for i ≤ (b + r)/2 and i > (b + r)/2. • ln α-2 b = O(ln α-2 b) = o(ln n), as α < 3. O(ln(br)) • ln α-2 b+r b-r = O ln n • ln α-2 δ δ -r = O ln n • ln δ δ -rThis completes the proof of Eq. (12). 5.7 Lower bound for GreedyBiDir for α < 2

1 / 1 f= O( 1 /

 111 = n Θ(1) , then it follows that f 2-hop (r, b) = O(1/ ln 2 n). From this bound and Claim 5 we obtain that Pr(d i ≤ r | d i-1 = δ ) ≤ f (r, δ ), for 1 ≤ r < δ ≤ d 0 ≤ λ , if f (r, δ ) is c ln δ δ -r / ln n + c/ ln 2 n, if 1 ≤ r < 1 -1 ln n δ ; 1, if (1 -1 ln n )δ ≤ r ≤ δ -1.Claim 4 then yieldsE[∂ l i | d i-1 = δ ] ≤ ∑ 1≤r≤δln n),similar to case α > 3, in Section 5.4. Thus, E[∂ l i | d i-1 ] ≤ µ for some µ = O(1/ ln n), and from Eq. (5) (cf.

f 2 - 1 νk 1 f

 211 hop (r, b) ≤ ln n • (bj) + last relation we used that ν = Θ (ln n) and b ≤ d s,t = λ . From this and Claim 5, it follows that Pr(d i ≤ r | d i-1 = δ ) ≤ f (r, δ ) for 1 ≤ r < δ ≤ d 0 ≤ λ , if f (r, δ ) is c ln δ δ -r / ln n + c ln 2 λ ln 2 n , if 1 ≤ r < 1 -1 ln n δ ; 1, if (1 -1 ln n )δ ≤ r ≤ δ -1.Claim 4 then yieldsE[∂ l i | d i-1 = δ ] ≤ ∑ 1≤r≤δ -

  because λ = 2 ln 1/3 n . Thus E[∂ l i | d i-1 ] ≤ µ := O(1/ ln n),and from Eq. (5) (cf.

Paths of polylogarithmic length exist between nodes for a wide range of values for parameter h, as shown by Martel and Nguyen[START_REF] Martel | Analyzing Kleinberg's (and other) small-world models[END_REF][START_REF] Martel | Analyzing and characterizing small-world graphs[END_REF]. However, short paths can be efficiently discovered by a decentralized algorithm only when h

= 2.

The extent to which this model resembles real social networks has yet to be evaluated empirically.

For the case of = 1, this follows also from a general lower bound by Dietzfelbinger and Woelfel[START_REF] Dietzfelbinger | Tight lower bounds for greedy routing in uniform small world rings[END_REF].

In Kleinberg's original model, a node has edges to all nodes at distance at most r; in our model we assume that r = 1. Further, in Kleinberg's model the grid does not wrap around; this assumption, however, is used in many subsequent works, e.g., by Martel and Nguyen[START_REF] Martel | Analyzing Kleinberg's (and other) small-world models[END_REF][START_REF] Martel | Analyzing and characterizing small-world graphs[END_REF]. We expect that these two assumptions are not critical for our results.

In fact, it holds for any i that is at most a polylogarithmic function of n, but for our purposes it suffices to assume that i ≤ log 3 n.

The value of λ is not optimized; it was chosen so that the same simple expression works for all three cases.

Acknowledgements We thank Vassos Hadzilacos and Philipp Woelfel for helpful discussions. We also thank the anonymous reviewers for their helpful feedback.