Distance in random graphs with infinite mean degrees (Q881401): Difference between revisions

The authors study distances on random graphs with infinite mean degrees. Let us consider an i.i.d. sequence \(D_1, D_2, \dots, D_{N}\). Assume that \(L_{N}=\sum_{j=1}^{N}D_{j}\) is even. The authors construct a graph in which node \(j\) has degree \(D_{j}\) for all \(1\leq j\leq N\). The probability mass function and the distribution function of the nodal degree are denoted by \(P(D_1=j)=f_{j}\), \(j=1,2,\dots\), and \(F(x)=\sum_{j=1}^{[x]}f_{j}\). The main assumption is that \(x^{\tau-1}(1-F(x))\) is slowly varying at infinity for some \(\tau\in (1,2)\). The graph distance \(H_{N}\) between the nodes \(1\) and \(2\) is defined as the minimum number of edges that form a path from \(1\) to \(2\). Two separate theorems for the case \(\tau\in(1,2)\) are presented in this paper. The first one is the following. Fix \(\tau\in(1,2)\) and let \(D_1,\dots,D_{N}\) be a sequence of i.i.d. copies of \(D\) with the distribution function \(F\). Then \(\lim_{N\to\infty}P(H_{N}=2)=1-\lim_{N\to\infty}P(H_{N}=3)=p_{F}\in(0,1)\). The boundary cases \(\tau=1\) and \(\tau=2\) are also considered.