About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
SODA 2002
Conference paper
The diameter of a long range percolation graph
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 -y||s if ||x -y|| > 1, and with probability 1 if ||x -y|| = 1, for some parameters β, α > 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 Weinberg 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].