Understanding Power-Law Degree Distributions in Random Graphs

Table of Links

Abstract and 1. Introduction

1.1 Our Contribution

1.2 Setting

1.3 The algorithm

2. Related Work

3. Algorithm

   3.1 The Structural Decomposition Phase

   3.2 The Routing Phase

   3.3 Variants of WormHole

4. Theoretical Analysis

   4.1 Preliminaries

   4.2 Sublinearity of Inner Ring

   4.3 Approximation Error

   4.4 Query Complexity

5. Experimental Results

   5.1 WormHole𝐸, WormHole𝐻 and BiBFS

   5.2 Comparison with index-based methods

   5.3 WormHole as a primitive: WormHole𝑀

References

4 THEORETICAL ANALYSIS

It is a relatively standard observation that many social networks exhibit, at least approximately, a power-law degree distribution (see, e.g., [9] and the many references within). The Chung-Lu model [41] is a commonly studied random graph model which admits such degree distribution.

In this section we provide a proof-of-concept for the correctness of WormHole on Chung-Lu random graphs, aiming to explain the good performance in practice through the study of a popular theoretical model. We sometimes only include proof sketches instead of full proofs, in the interest of saving space.

4.1 Preliminaries

Theorem 4.1 (Theorem 4 in [16]). Suppose a power law random graph with exponent 2<𝛽 <3, average degree 𝑑 strictly greater than 1, and maximum degree 𝑑𝑚𝑎𝑥 > log𝑛/log log𝑛. Then almost surely the diameter is Θ(log𝑛), the diameter of the CCL core is 𝑂(loglog𝑛) and almost all vertices are within distance𝑂(loglog𝑛) to CCL.

**Claim 4.2 (**Fact 2 in [15]). With probability at least 1−1/𝑛, for all vertices𝑣 ∈𝑉 such that𝑤(𝑣) ≥10logn

and for all vertices with𝑤(𝑣) ≤10log𝑛, 𝑑 (𝑣) ≤20log𝑛.

4.2 Sublinearity of Inner Ring