The diameter of a long range percolation graph

Don Coppersmith, David Gamarnik, Maxim SviridenkoRandom Struct. Algorithms 2002 · DOI · OpenReview

TL;DR

This paper investigates the "diameter" (the longest shortest path) of a specific type of random network called a "long-range percolation graph." The authors provide new upper and lower bounds for this diameter across different parameter regimes, offering a more complete understanding of how network structure emerges with varying "long-range" connection probabilities.

What Problem Does This Paper Address?

The paper tackles the problem of understanding the structural properties of random graphs with "long-range" connections. These graphs are inspired by models of social networks and the internet, where not only immediate neighbors but also distant nodes can be connected with a certain probability. Specifically, the authors focus on the diameter of these graphs, which is a crucial metric for how efficiently information or influence can spread. Previous work had established results for certain parameter ranges, but key cases, particularly in higher dimensions, remained open. This paper aims to fill these gaps by providing a comprehensive analysis of the diameter across various dimensions and connection probability parameters.

Methods

The authors employ a combination of probabilistic techniques and graph theory. Key methods include:

  • Probabilistic Bounds: Using inequalities like Markov's inequality to derive upper and lower bounds on the diameter.
  • Renormalization Techniques: For the case $d < s < 2d$, they use a recursive splitting of the graph into subcubes, analyzing how the diameter behaves at different scales. This is presented as a simpler proof than prior work.
  • Branching Theory (for lower bounds): For the $s=2d$ case, they leverage concepts from branching theory and the notion of "cut points" to establish lower bounds on the diameter.
  • Standard Graph Theory Notations: The paper uses standard notations for big-O, big-Omega, and big-Theta to describe the asymptotic behavior of the diameter.

Datasets

Not discussed in the paper. The paper deals with theoretical models of random graphs, not empirical datasets.

Key Insights and Ideas

  • Phase Transitions in Diameter: The paper strongly supports the idea that the diameter of these long-range percolation graphs exhibits "phase transitions" at specific values of the exponent $s$ (related to how quickly connection probability decays with distance). These transitions lead to qualitatively different network structures and diameter behaviors.
  • Dimensionality Matters: The analysis explicitly considers the dimension $d$ of the underlying grid, showing how the relationship between $s$ and $d$ dictates the diameter's scaling.
  • Bridging Theory and Social Networks: The work connects abstract mathematical models of random graphs to real-world phenomena like social networks, providing theoretical underpinnings for observed network properties.
  • Simpler Proofs for Known Results: The authors offer a simpler proof for an existing result concerning the $d < s < 2d$ regime, which is valuable for accessibility and understanding.

Key Results

The paper establishes several key results regarding the diameter $D(N)$ of the long-range percolation graph on an $N^d$ grid:

  • For $s = d$: The diameter is $\Theta(\log N / \log \log N)$ with high probability.
  • For $d < s < 2d$: The diameter is at most $O(\log^c N)$ for some constant $c > 1$ with high probability.
  • For $s = 2d$: The diameter is at most $N^\eta$ for some constant $0 < \eta < 1$ with high probability.
  • Lower Bounds:
    • For $s > 2d$, the diameter is at least $\Omega(N^{(s-2d)/(s-d-1)})$ with high probability.
  • For $d=1, s=2, \beta < 1$, the diameter is at least $\Omega(N^\eta)$ for some $\eta < 1$ with high probability.

The paper also supports conjectures for the $s=2$ case in 1D and disproves a conjecture for the $s=1$ case.

Limitations and Future Work

  • Unanswered Regimes: The paper explicitly points out that lower bounds are missing for several regimes: $s=2d$, $d=1, s=2, \beta > 1$, and $d < s < 2d$.
  • Conjectures: The authors conjecture that a linear lower bound $\Omega(N)$ holds for $s > 2d$ in general dimensions, which is currently only proven for $d=1$.
  • Limit Computations: They suggest that computing the exact limits of $D(N) / (\log N / \log \log N)$ for $s=d$ and $D(N) / N^\eta$ for $s=2d$ would be interesting future work, as would proving the existence of these limits.
  • General Dimensions: While the paper extends some results to higher dimensions, the precise behavior for all parameter combinations in general $d$ remains an area for further exploration.

Summary updated

Abstract

One can model a social network as a long-range percolation model on a graph {0, 1, …, N}2. The edges (x, y) of this graph are selected with probability ≈ β/||x - ys if ||x - y|| > 1, and with probability 1 if ||x - y|| = 1, for some parameters β, s > 0. That is, people are more likely to be acquainted with their neighbors than with people at large distance. This model was introduced by Benjamini and Berger [2] and it resembles a model considered by Kleinberg in [6], [7]. We are interested in how small (probabilistically) is the diameter of this graph as a function of β and s, thus relating to the famous Milgram's experiment which led to the "six degrees of separation" concept. Extending the work by Benjamini and Berger, we consider a d-dimensional version of this question on a node set {0, 1, …, N}d and obtain upper and lower bounds on the expected diameter of this graph. Specifically, we show that the expected diameter experiences phase transitions at values s = d and s = 2d. We compare the algorithmic implication of our work to the ones of Kleinberg, [6].
BibTeX
@article{coppersmith2002diameter,
  author = {Don Coppersmith and David Gamarnik and Maxim Sviridenko},
  title = {{The diameter of a long range percolation graph}},
  journal = {Random Struct. Algorithms},
  year = {2002},
  doi = {10.1002/rsa.10042},
}
Figure