Proceedings of the thirteenth annual ACM-SIAM symposium on discrete algorithms, San Francisco, CA, USA, January 6–8, 2002. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM) (ISBN 0-89871-513-X/pbk). 329-337 (2002).

Summary: One can model a social network as a long-range percolation model on a graph

${\{0,1,\cdots ,N\}}^{2}$. The edges

$(\mathbf{x},\mathbf{y})$ of this graph are selected with probability

$\approx {\beta /\parallel \mathbf{x}-\mathbf{y}\parallel}^{s}$ if

$\parallel \mathbf{x}-\mathbf{y}\parallel >1$, and with probability 1 if

$\parallel \mathbf{x}-\mathbf{y}\parallel =1$, for some parameters

$\beta ,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

*I. Benjamini* and

*N. Berger* [Random Struct. Algorithms 9, 102–111 (2001;

Zbl 0983.60099)] and it resembles a model considered by

*J. Kleinberg* [“The small-world phenomenon: An algorithmic perspective” (Cornell Comput. Sci. Techn. Rep. 99–1776, 1999) and Nature 406 (2000)]. We are interested in how small (probabilistically) is the diameter of this graph as a function of

$\beta $ 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,\cdots ,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 in his above, first quoted paper.