2006/05/16 by Henri van den Esker, Remco van der Hofstad, Esker, Henri van den +3 · 1 citation
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR) #math.CO #math.PR
paper · pdf · doi:10.48550/arxiv.math/0605414
40 pages, 1 figure
arxiv created 2008/05/19 · arxiv updated 2009/12/01
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νN, where the νdepends on the capacities. In addition, the random fluctuations around this asymptotic mean logνN are shown to be tight. We also consider the case where the capacities are independent copies of a positive random Λwith \probΛ> x≤ cx1-τ, for some constant c and τ>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.