Distances in random graphs with infinite mean degrees

By H. Esker, Remco van der Hofstad, Gerard Hooghiemstra, D. Znamenski. 2004

62 citations recorded by the source corpus.

We study random graphs with an i.i.d. degree sequence of which the tail of the distribution function $$F$$ is regularly varying with exponent $$\tau\in [1,2]$$. In particular, the degrees have infinite mean. Such random graphs can serve as models for complex networks where degree power laws are observed. The minimal number of edges between two arbitrary nodes, also called the graph distance or the hopcount, is investigated when the size of the graph tends to infinity. The paper is part of a sequel of three papers. The other two papers study the case where $$\tau \in (2,3)$$, and $$\tau \in (3,\infty),$$, respectively. The main result of this paper is that the graph distance for $$\tau\in (1,2)$$ converges in distribution to a random variable with probability mass exclusively on the points $$2$$ and $$3$$. We also consider the case where we condition the degrees to be at most $$N^{\alpha}$$ for some $$\alpha>0$$, where $$N$$ is the size of the graph. For fixed $$k\in\left\{{0,1,2,\ldots}\right\}$$ and $$\alpha$$ such that $$(\tau+k)^{-1}<\alpha<(\tau+k-1)^{-1}$$, the hopcount converges to $$k+3$$ in probability, while for $$\alpha>(\tau-1)^{-1}$$, the hopcount converges to the same limit as for the unconditioned degrees. The proofs use extreme value theory.

Subfields: Discrete Mathematics and Combinatorics, Mathematical Physics, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/b62350fb85f9663adffb4612bacde1eaa417d99f

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Discrete Mathematics and Combinatorics

In Mathematical Physics

In Statistical and Nonlinear Physics

Citations in the corpus

Random Graphs and Complex Networks (2016, background): “Therefore, [116] considers cases where the degrees are conditioned to be at most a given power of n.”
On a conditionally Poissonian graph process (2006, background): “... model of [11] and showed that for a power-tailed degree distribution with infinite variance, these distances were in fact only of the order . Chung and Lu [5] proved a asymptotic in a model that assumed a power-law sequence of “expected degrees” and connected vertices and with probability (they ”
Distances in Random Graphs with Finite Mean and Infinite Variance Degrees (2005, methodology): “As mentioned before, full proofs of these results can be found in (10).”