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
-
Related Work
-
Algorithm
3.1 The Structural Decomposition Phase
3.2 The Routing Phase
3.3 Variants of WormHole
-
Theoretical Analysis
4.1 Preliminaries
4.2 Sublinearity of Inner Ring
4.3 Approximation Error
4.4 Query Complexity
-
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
\ 
\ \ \ 
\ \ \ 
\ \ \
:::info Authors:
(1) Talya Eden, Bar-Ilan University (talyaa01@gmail.com);
(2) Omri Ben-Eliezer, MIT (omrib@mit.edu);
(3) C. Seshadhri, UC Santa Cruz (sesh@ucsc.edu).
:::
:::info This paper is available on arxiv under CC BY 4.0 license.
:::
\
You May Also Like
Best Crypto to Buy as Saylor & Crypto Execs Meet in US Treasury Council
Trump's border chief insists Americans support ICE – and is shut down by host: 'Come on!'
