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
. The edges
of this graph are selected with probability
, and with probability 1 if
, for some parameters
. 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
, 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
-dimensional version of this question on a node set
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
. We compare the algorithmic implication of our work to the ones of Kleinberg in his above, first quoted paper.