Table of Links
-
Algorithm
-
Theoretical Analysis
-
5.1 WormHole𝐸, WormHole𝐻 and BiBFS
4.3 Approximation Error
Now that we have a sublinear inner ring that contains the Chung-Lu core, we must show that routing paths through it incurs only a small penalty. Intuitively, the larger the inner ring, the easier this is to satisfy: if the inner ring is the whole graph, the statement holds trivially. Therefore the challenge lies in showing that we can achieve a strong guarantee in terms of accuracy even with a sublinear inner ring. We prove that WormHole incurs an additive error at most 𝑂(loglog𝑛) for all pairs, which is much smaller than the diameter Θ(log𝑛).
The above result holds with high probability even in the worst case. Namely, for all pairs (𝑠,𝑡) of vertices in the graph, the length of the path returned by WormHole is at most𝑂(loglog𝑛) higher than the actual distance between 𝑠 and 𝑡. This trivially implies that the average additive error of WormHole is, with high probability, bounded by the same amount.
4.4 Query Complexity
Recall the node query model in this paper (see §1.2): starting from a single node, we are allowed to iteratively make queries, where each query retrieves the neighbor list of a node 𝑣 of our choice. We are interested in the query complexity, i.e., the number of queries required to conduct certain operations.
The first result is the upper bound on our performance.
Proof Sketch. For a given inquiry SP(𝑢, 𝑣), we give an upper bound on the query complexity of the BFS that starts at 𝑢, and similarly for𝑣; the total query complexity is the sum of these two quantities.
Authors:
(1) Talya Eden, Bar-Ilan University ([email protected]);
(2) Omri Ben-Eliezer, MIT ([email protected]);
(3) C. Seshadhri, UC Santa Cruz ([email protected]).
This paper is