Distances in random graphs with finite variance degrees

Details Distances in random graphs with finite variance degrees Distances in random graphs with finite variance degrees

2004-07-07

arxiv.org/abs/math/0407092v1

Mathematics

Probability

40 pages, 2 figures

Scientific paper

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)\leq 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 $\nu=\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.

Affiliated with

Also associated with

No associations

Rating

Distances in random graphs with finite variance degrees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Distances in random graphs with finite variance degrees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distances in random graphs with finite variance degrees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-729265