Advanced Search

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

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]