# zbMATH — the first resource for mathematics

##### Examples
 Geometry Search for the term Geometry in any field. Queries are case-independent. Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact. "Topological group" Phrases (multi-words) should be set in "straight quotation marks". au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted. Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff. "Quasi* map*" py: 1989 The resulting documents have publication year 1989. so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14. "Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic. dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles. py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses). la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

##### Operators
 a & b logic and a | b logic or !ab logic not abc* right wildcard "ab c" phrase (ab c) parentheses
##### Fields
 any anywhere an internal document identifier au author, editor ai internal author identifier ti title la language so source ab review, abstract py publication year rv reviewer cc MSC code ut uncontrolled term dt document type (j: journal article; b: book; a: book article)
The diameter of a long range percolation graph. (English) Zbl 1055.60095
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 ${\left\{0,1,\cdots ,N\right\}}^{2}$. The edges $\left(𝐱,𝐲\right)$ of this graph are selected with probability $\approx {\beta /\parallel 𝐱-𝐲\parallel }^{s}$ if $\parallel 𝐱-𝐲\parallel >1$, and with probability 1 if $\parallel 𝐱-𝐲\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 ${\left\{0,1,\cdots ,N\right\}}^{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:
 60K35 Interacting random processes; statistical mechanics type models; percolation theory