Distances in random graphs with finite variance degrees

Abstract

In this paper we study a random graph with $N$ nodes, where node $j$ has degree $D_j$ and $\{D_j{\}}_{j=1}^N$ are i.i.d. with $\prob(D_j\leq x)=F(x)$. We assume that $1-F(x)\le c{x}^{-\tau +1}$ for some $\tau >3$ and some constant $c>0$. This graph model is a variant of the so-called configuration model, and includes heavy tail degrees with finite variance. The minimal number of edges between two arbitrary connected nodes, also known as the graph distance or the hopcount, is investigated when $N\to \infty$. We prove that the graph distance grows like ${\log }_{\nu }N$, when the base of the logarithm equals $ν=\expec[D_j(D_j -1)]/\expec[D_j]>1$. This confirms the heuristic argument of Newman, Strogatz and Watts \cite{NSW00}. In addition, the random fluctuations around this asymptotic mean ${\log }_{\nu }N$ are characterized and shown to be uniformly bounded. In particular, we show convergence in distribution of the centered graph distance along exponentially growing subsequences.

40 pages, 2 figures

References in corpus (7)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• The structure and function of complex networks
• Random graphs with arbitrary degree distributions and their applications
• Pseudofractal Scale-free Web
• Distances in random graphs with finite mean and infinite variance degrees
• Distances in random graphs with infinite mean degrees

Cited by in corpus (19)

• Diameters in preferential attachment models
• Explosion in weighted Hyperbolic Random Graphs and Geometric Inhomogeneous Random Graphs
• The distribution of shortest path lengths in subcritical Erdős-Rényi networks
• The diameter of weighted random graphs
• How to determine if a random graph with a fixed degree sequence has a giant component
• Short paths for first passage percolation on the complete graph
• The structure of typical clusters in large sparse random configurations
• Power-law relations in random networks with communities
• First Passage Percolation on Inhomogeneous Random Graphs
• Phase transitions for scaling of structural correlations in directed networks
• Ranking algorithms on directed configuration networks
• Linking the mixing times of random walks on static and dynamic random graphs
• Universality for the distance in finite variance random graphs: Extended version
• Weighted distances in scale-free preferential attachment models
• Distance Distribution in Extreme Modular Networks
• The tail does not determine the size of the giant
• A geometric preferential attachment model with fitness
• The giant in random graphs is almost local
• Extreme value theory, Poisson-Dirichlet distributions and FPP on random networks