Hal will be stopped for maintenance from friday on june 10 at 4pm until monday june 13 at 9am. More information
Skip to Main content Skip to Navigation

Recovering the Long Range Links in Augmented Graphs

Abstract : The augmented graph model, as introduced by Kleinberg (STOC 2000), is an appealing model for analyzing navigability in social networks. Informally, this model is defined by a pair (H,phi), where H is a graph in which inter-node distances are supposed to be easy to compute or at least easy to estimate. This graph is "augmented" by links, called long range links, which are selected according to the probability distribution phi. The augmented graph model enables the analysis of greedy routing in augmented graphs G in (H,phi). In greedy routing, each intermediate node handling a message for a target t selects among all its neighbors in G the one that is the closest to t in H and forwards the message to it. This paper addresses the problem of checking whether a given graph G is an augmented graph. It answers part of the questions raised by Kleinberg in his Problem 9 (Int. Congress of Math. 2006). More precisely, given G in (H,phi), we aim at extracting the base graph H and the long range links R out of G. We prove that if H has a high clustering coefficient and bounded doubling dimension, then a simple algorithm enables to partition the edges of G into two sets H' and R' such that E(H) is included in H' and the edges in H'\E(H) are of small stretch, i.e., the map H is not perturbed too greatly by undetected long range links remaining in H'. The perturbation is actually so small that we can prove that the expected performances of greedy routing in G using the distances in H' are close to the expected performances of greedy routing in (H,phi). Although this latter result may appear intuitively straightforward, since H' is included in E(H), it is not, as we also show that routing with a map more precise than H may actually damage greedy routing significantly. Finally, we show that in absence of a hypothesis regarding the high clustering coefficient, any structural attempt to extract the long range links will miss the detection of at least $\Omega(n^{5\epsilon}/\log n)$ long range links of stretch at least $\Omega(n^{1/5-\epsilon})$ for any $0<\epsilon<1/5$, and thus the map H cannot be recovered with good accuracy. To sum up, we solve Kleinberg's Problem 9 in the sense that we show that reconstructing augmented graphs is achievable if and only if the base graph has a high clustering coefficient.
Complete list of metadata

Cited literature [42 references]  Display  Hide  Download

Contributor : Emmanuelle Lebhar Connect in order to contact the contributor
Submitted on : Thursday, July 5, 2007 - 4:34:07 PM
Last modification on : Friday, January 21, 2022 - 3:14:40 AM
Long-term archiving on: : Friday, November 25, 2016 - 6:32:43 PM


Files produced by the author(s)


  • HAL Id : inria-00147536, version 4


Pierre Fraigniaud, Emmanuelle Lebhar, Zvi Lotker. Recovering the Long Range Links in Augmented Graphs. [Research Report] RR-6197, INRIA. 2007, pp.27. ⟨inria-00147536v4⟩



Record views


Files downloads