Universality for the distance in finite variance random graphs: Extended version

Details Universality for the distance in finite variance random graphs: Extended version Universality for the distance in finite variance random graphs: Extended version

2006-05-16

arxiv.org/abs/math/0605414v4

Mathematics

Probability

40 pages, 1 figure

Scientific paper

We generalize the asymptotic behavior of the graph distance between two uniformly chosen nodes in the configuration model to a wide class of random graphs. Among others, this class contains the Poissonian random graph, the expected degree random graph and the generalized random graph (including the classical Erdos-Renyi graph). In the paper we assign to each node a deterministic capacity and the probability that there exists an edge between a pair of nodes is equal to a function of the product of the capacities of the pair divided by the total capacity of all the nodes. We consider capacities which are such that the degrees of a node has uniformly bounded moments of order strictly larger than two, so that, in particular, the degrees have finite variance. We prove that the graph distance grows like \log_\nu N, where the \nu depends on the capacities. In addition, the random fluctuations around this asymptotic mean \log_\nu N are shown to be tight. We also consider the case where the capacities are independent copies of a positive random \Lambda with \prob{\Lambda> x}\leq cx^{1-\tau}, for some constant c and \tau>3, again resulting in graphs where the degrees have finite variance. The method of proof of these results is to couple each member of the class to the Poissonian random graph, for which we then give the complete proof by adapting the arguments of the corresponding result for the configuration model.

Affiliated with

Also associated with

No associations

Rating

Universality for the distance in finite variance random graphs: Extended version 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 Universality for the distance in finite variance random graphs: Extended version, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Universality for the distance in finite variance random graphs: Extended version will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-275954