Distances in random graphs with finite variance degrees

DOI10.1002/RSA.20063MaRDI QIDQ5311913zbMATH OpenOpenAlexFDO

Authors Remco van der Hofstad, Gerard Hooghiemstra, Piet Van Mieghem

Publication date 29 August 2005

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0407092

zbMATH Keywords

couplingtypical distance

Mathematics Subject Classification ID

Distance in graphs (05C12) Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80)

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}leqx)=F(x)$. We assume that $1-F(x)leqc{x}^{-au+1}$ for some $au>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 $Noinfty$. We prove that the graph distance grows like $lo{g}_{u}N$, when the base of the logarithm equals $u=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 $lo{g}_{u}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.

Recommendations

• Distances in random graphs with finite mean and infinite variance degrees
• Distance in random graphs with infinite mean degrees
• Universality for the distance in finite variance random graphs
• Tight fluctuations of weight-distances in random graphs with infinite-variance degrees
• Diameters of random distance graphs
• On Distances in Uniformly Random Networks
• The average distances in random graphs with given expected degrees
• scientific article; zbMATH DE number 3847442
• Universality for distances in power-law random graphs
• The variance of the vertex degrees of randomly generated graphs

Cites work

• A Random Graph Model for Power Law Graphs
• Directed scale-free graphs
• scientific article; zbMATH DE number 1792101 (Why is no real title available?)
• scientific article; zbMATH DE number 1416816 (Why is no real title available?)

Cited in

(54)

• The tail does not determine the size of the giant
• Typical distances in the directed configuration model
• When is a scale-free graph ultra-small?
• Tight fluctuations of weight-distances in random graphs with infinite-variance degrees
• Weighted distances in scale-free configuration models
• First passage percolation on random graphs with finite mean degrees
• Limits of sparse configuration models and beyond: graphexes and multigraphexes
• Linking the mixing times of random walks on static and dynamic random graphs
• Average hopcount of the shortest path in tree-like components with finite size
• The average distance and the diameter of dense random regular graphs
• Optimal subgraph structures in scale-free configuration models
• Explosion in weighted hyperbolic random graphs and geometric inhomogeneous random graphs
• The diameter of weighted random graphs
• Distance distribution of nodes in star graphs
• The structure of typical clusters in large sparse random configurations
• Weak disorder asymptotics in the stochastic mean-field model of distance
• Distances in random graphs with finite mean and infinite variance degrees
• On the mean distance in scale free graphs
• On the relation between graph distance and Euclidean distance in random geometric graphs
• Joint distribution of distances in large random regular networks
• Extreme value theory, Poisson-Dirichlet distributions, and first passage percolation on random networks
• The shortest distance in random multi-type intersection graphs
• Construction of directed assortative configuration graphs
• Giant component in random multipartite graphs with given degree sequences
• Short paths for first passage percolation on the complete graph
• Universality for distances in power-law random graphs
• First passage percolation on locally treelike networks. I. Dense random graphs
• Scale-free percolation
• Tail behavior of solutions of linear recursions on trees
• The variance of the vertex degrees of randomly generated graphs
• The diameter of sparse random graphs
• Limit theorems for assortativity and clustering in null models for scale-free networks
• Analytical results for the distribution of cover times of random walks on random regular graphs
• Strong couplings for static locally tree-like random graphs
• The mean and variance of the distribution of shortest path lengths of random regular graphs
• Analytical results for the distribution of first-passage times of random walks on random regular graphs
• Resistance distance distribution in large sparse random graphs
• The idemetric property: when most distances are (almost) the same
• Directed random graphs with given degree distributions
• Degree correlations in scale-free random graph models
• First passage percolation on inhomogeneous random graphs
• Diameter in ultra-small scale-free random graphs
• On a conditionally Poissonian graph process
• Epidemics and vaccination on weighted graphs
• The winner takes it all but one
• Connectivity of random graphs after centrality-based vertex removal
• How to determine if a random graph with a fixed degree sequence has a giant component
• Analytical results for the distribution of first return times of non-backtracking random walks on configuration model networks
• Counting triangles in power-law uniform random graphs
• Distance in random graphs with infinite mean degrees
• On analytical approaches to epidemics on networks
• The largest component in a subcritical random graph with a power law degree distribution
• Universality for the distance in finite variance random graphs
• Diameters in preferential attachment models

This page was built for publication: Distances in random graphs with finite variance degrees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5311913)