Distances in random graphs with finite mean and infinite variance degrees

Details Distances in random graphs with finite mean and infinite variance degrees Distances in random graphs with finite mean and infinite variance degrees

2005-02-28

arxiv.org/abs/math/0502581v1

Mathematics

Probability

52 pages, 4 figures

Scientific paper

In this paper we study random graphs with independent and identically distributed degrees of which the tail of the distribution function is regularly varying with exponent $\tau\in (2,3)$. The number of edges between two arbitrary nodes, also called the graph distance or hopcount, in a graph with $N$ nodes is investigated when $N\to \infty$. When $\tau\in (2,3)$, this graph distance grows like $2\frac{\log\log N}{|\log(\tau-2)|}$. In different papers, the cases $\tau>3$ and $\tau\in (1,2)$ have been studied. We also study the fluctuations around these asymptotic means, and describe their distributions. The results presented here improve upon results of Reittu and Norros, who prove an upper bound only.

Affiliated with

Also associated with

No associations

Rating

Distances in random graphs with finite mean and infinite 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 mean and infinite 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 mean and infinite variance degrees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-142594