Abstract
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 Erdős-Rényi 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 have 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 and N denotes the size of the graph. 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 \(\mathbb{P}\left (\Lambda>x\right )\leq cx^{1-\tau}\) , 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 van der Hofstad et al. (Random Struct. Algorithms 27(2):76–123, 2005).
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Asmussen, S.: Some martingale methods in the limit theory of supercritical branching processes. In: Branching Processes. Advances in Probability and related Topics, pp. 1–26 (1978)
Bender, E.A., Canfield, E.R.: The asymptotic number of labelled graphs with given degree sequences. J. Comb. Theory A 24(3), 296–307 (1978)
Bollobás, B.: Random Graphs. Cambridge University Press, Cambridge (2001)
Bollobás, B., Borgs, C., Chayes, J.T., Riordan, O.: Directed scale-free graphs. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 132–139 (2003)
Bollobás, B., Janson, S., Riordan, O.: The phase transition in inhomogeneous random graphs. Random Struct. Algorithms 31(1), 3–122 (2007)
Britton, T., Deijfen, M., Martin-Löf, A.: Generating simple random graphs with prescribed degree distribution. J. Stat. Phys. 124(6), 1377–1397 (2006)
Chung, F., Lu, L.: The average distances in random graphs with expected degrees. Proc Natl. Acad. Sci. 99(25), 15879–15882 (2002)
Chung, F., Lu, L.: Connected components in random graphs with given expected degree sequences. Ann. Comb. 6(2), 125–145 (2002)
van den Esker, H., van der Hofstad, R., Hooghiemstra, G.: Universality for the distance in finite variance random graphs: extended version. http://arxiv.org/abs/math.PR/0605414
van den Esker, H., van der Hofstad, R., Hooghiemstra, G., Znamenski, D.: Distances in random graphs with infinite mean degrees. Extremes 8, 111–140 (2006)
Feller, W.: An Introduction to Probability Theory and Its Applications, vol. II, 2nd edn. Wiley, New York (1971)
Gut, A.: Probability: A Graduate Course. Springer, Berlin (2005)
van der Hofstad, R., Hooghiemstra, G., Van Mieghem, P.: Distances in random graphs with finite variance degrees. Random Struct. Algorithms 27(2), 76–123 (2005)
van der Hofstad, R., Hooghiemstra, G., Znamenski, D.: Distances in random graphs with finite mean and infinite variance degrees. Electron. J. Probab. 12, 703–766 (2007)
Janson, S.: Asymptotic equivalence and contiguity of some random graphs. Preprint (2008)
Janson, S., Luczak, T., Ruciński, A.: Random Graphs. Wiley, New York (2000)
Molloy, M., Reed, B.: A critical point for random graphs with a given degree sequence. In: Proceedings of the Sixth International Seminar on Random Graphs and Probabilistic Methods in Combinatorics and Computer Science, pp. 161–179 (1995)
Newman, M.E.J., Strogatz, S.H., Watts, D.J.: Random graphs with arbitrary degree distribution and their application. Phys. Rev. E 64, 026118 (2001)
Norros, I., Reittu, H.: On the power-law random graph model of massive data networks. Perform. Eval. 55(1–2), 3–23 (2004)
Norros, I., Reittu, H.: On a conditionally Poissonian graph process. Adv. Appl. Probab. 38(1), 59–75 (2006)
Thorisson, H.: Coupling, Stationarity and Regeneration. Springer, Berlin (2000)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
Open Access This is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License (https://creativecommons.org/licenses/by-nc/2.0), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
About this article
Cite this article
van den Esker, H., van der Hofstad, R. & Hooghiemstra, G. Universality for the Distance in Finite Variance Random Graphs. J Stat Phys 133, 169–202 (2008). https://doi.org/10.1007/s10955-008-9594-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10955-008-9594-z