Language:   Search:   Contact
Zentralblatt MATH has released its new interface!
For an improved author identification, see the new author database of ZBMATH.

Query:
Fill in the form and click »Search«...
Format:
Display: entries per page entries
Zbl 1055.60095
Coppersmith, Don; Gamarnik, David; Sviridenko, Maxim
The diameter of a long range percolation graph.
(English)
[A] 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). 329-337 (2002). ISBN 0-89871-513-X/pbk

Summary: One can model a social network as a long-range percolation model on a graph $\{0,1,\dots,N\}^2$. The edges $({\bold x}, {\bold y})$ of this graph are selected with probability $\approx\beta/ \Vert{\bold x}- {\bold y}\Vert^s$ if $\Vert{\bold x}-{\bold y}\Vert>1$, and with probability 1 if $\Vert{\bold x}-{\bold y}\Vert=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 {\it I. Benjamini} and {\it N. Berger} [Random Struct. Algorithms 9, 102--111 (2001; Zbl 0983.60099)] and it resembles a model considered by {\it 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,\dots,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.
MSC 2000:
*60K35 Interacting random processes

Citations: Zbl 0983.60099

Highlights
Master Server