Table of Links Abstract and 1. Introduction Abstract and 1. Introduction 1.1 Our Contribution 1.1 Our Contribution 1.2 Setting 1.2 Setting 1.3 The algorithm 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𝑀 Related Work Related Work Related Work Algorithm
3.1 The Structural Decomposition Phase
3.2 The Routing Phase
3.3 Variants of WormHole Algorithm 3.1 The Structural Decomposition Phase 3.1 The Structural Decomposition Phase 3.2 The Routing Phase 3.2 The Routing Phase 3.3 Variants of WormHole 3.3 Variants of WormHole Theoretical Analysis
4.1 Preliminaries
4.2 Sublinearity of Inner Ring
4.3 Approximation Error
4.4 Query Complexity Theoretical Analysis 4.1 Preliminaries 4.1 Preliminaries 4.2 Sublinearity of Inner Ring 4.2 Sublinearity of Inner Ring 4.3 Approximation Error 4.3 Approximation Error 4.4 Query Complexity 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𝑀 Experimental Results Experimental Results 5.1 WormHole𝐸, WormHole𝐻 and BiBFS 5.1 WormHole𝐸, WormHole𝐻 and BiBFS 5.2 Comparison with index-based methods 5.2 Comparison with index-based methods 5.3 WormHole as a primitive: WormHole𝑀 5.3 WormHole as a primitive: WormHole𝑀 References 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. 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 With probability at least 1−1/𝑛, for all vertices𝑣 ∈𝑉 such that𝑤(𝑣) ≥10logn and for all vertices with𝑤(𝑣) ≤10log𝑛, 𝑑 (𝑣) ≤20log𝑛. and for all vertices with𝑤(𝑣) ≤10log𝑛, 𝑑 (𝑣) ≤20log𝑛. 4.2 Sublinearity of Inner Ring 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). Authors: 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). This paper is available on arxiv under CC BY 4.0 license. This paper is available on arxiv under CC BY 4.0 license. available on arxiv available on arxiv

Part of HackerNoon's growing list of open-source research papers, promoting free access to academic material.

Understanding Power-Law Degree Distributions in Random Graphs

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

A Brief Review of Modern Shortest Path Algorithms and Graph Optimization Techniques

Bridging the Gap Between BFS and Indexing for Large Graphs

How WormHole Speeds Up Pathfinding in Billion-Edge Graphs

Finding Shortest Paths Faster With Less Data

A Brief Review of Modern Shortest Path Algorithms and Graph Optimization Techniques

A Brief Review of Modern Shortest Path Algorithms and Graph Optimization Techniques

Bridging the Gap Between BFS and Indexing for Large Graphs

How WormHole Speeds Up Pathfinding in Billion-Edge Graphs

Finding Shortest Paths Faster With Less Data

A Brief Review of Modern Shortest Path Algorithms and Graph Optimization Techniques

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps