Abstract
We study random graphs with an i.i.d. degree sequence of which the tail of the distribution function \(F\) is regularly varying with exponent \(\tau\in [1,2]\). In particular, the degrees have infinite mean. Such random graphs can serve as models for complex networks where degree power laws are observed. The minimal number of edges between two arbitrary nodes, also called the graph distance or the hopcount, is investigated when the size of the graph tends to infinity. The paper is part of a sequel of three papers. The other two papers study the case where \(\tau \in (2,3)\), and \(\tau \in (3,\infty),\), respectively. The main result of this paper is that the graph distance for \(\tau\in (1,2)\) converges in distribution to a random variable with probability mass exclusively on the points \(2\) and \(3\). We also consider the case where we condition the degrees to be at most \(N^{\alpha}\) for some \(\alpha>0\), where \(N\) is the size of the graph. For fixed \(k\in\left\{{0,1,2,\ldots}\right\}\) and \(\alpha\) such that \((\tau+k)^{-1}<\alpha<(\tau+k-1)^{-1}\), the hopcount converges to \(k+3\) in probability, while for \(\alpha>(\tau-1)^{-1}\), the hopcount converges to the same limit as for the unconditioned degrees. The proofs use extreme value theory.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Aiello, W., Chung, F., Lu, L.: A random graph model for power law graphs. Exp. Math. 10(1), 53–66 (2001)
Aiello, W., Chung, F., Lu, L.: Random evolution of massive graphs. In: Abello, J., Pardalos, P.M., Resende, M.G.C. (eds.) Handbook of Massive Data Sets, pp. 97–122. Kluwer, Dordrecht (2002)
Albert, R., Barabási, A.-L.: Statistical mechanics of complex networks. Rev. Mod. Phys. 74, 47–97 (2002)
Billingsley, P.: Convergence of Probability Measures. Wiley, New York (1968)
Chung, F., Lu, L.: The average distances in random graphs with given expected degrees. PNAS 99(25), 15879–15882 (2002)
Chung, F., Lu, L.: Connected components in random graphs with given expected degree sequences. Ann. Comb. 6, 125–145 (2002)
Embrechts, P., Klüppelberg, C., Mikosch, T.: Modelling Extremal Events. Springer, Berlin Heidelberg New York (1997)
Faloutsos, C., Faloutsos, P., Faloutsos, M.: On power-law relationships of the internet topology. Comput. Commun. Rev. 29, 251–262 (1999)
Feller, W.: An Introduction to Probability Theory and Its Applications Volume II, 2nd edition. Wiley, New York (1971)
Hofstad, R. van der, Hooghiemstra, G., Van Mieghem, P.: Distances in random graphs with finite variance degrees. Random Struct. Algorithms 27, 76–123 (2005a)
Hofstad, R. van der, Hooghiemstra, G., Znamenski, D.: Distances in random graphs with finite mean and infinite variance degrees. Preprint (2005b)
Hofstad, R. van der, Hooghiemstra, G., Znamenski, D.: Random graphs with arbitrary i.i.d. degrees. Preprint (2005c)
Janson, S.: On concentration of probability. In: Bollobás, B. (ed.) Contemporary Combinatorics, Bolyai Soc. Math. Stud. 10, pp. 289–301. János Bolyai Mathematical Society, Budapest (2002)
LePage, R., Woodroofe, M., Zinn, J.: Convergence to a stable distribution via order statistics. Ann. Probab. 9, 624–632 (1981)
Molloy, M., Reed, B.: A critical point for random graphs with a given degree sequence. Random Struct. Algorithms 6, 161–179 (1995)
Molloy, M., Reed, B.: The size of the giant component of a random graph with a given degree sequence. Comb. Probab. Comput. 7, 295–305 (1998)
Newman, M.E.J.: The structure and function of complex networks. SIAM Rev. 45(2), 167–256 (2003)
Newman, M.E.J., Strogatz, S.H., Watts, D.J.: Random graphs with arbitrary degree distribution and their application. Phys. Rev. E 64, 026118 (2000)
Reittu, H., Norros, I.: On large random graphs of the “Internet type”. Perform. Eval. 55(1–2), 3–23 (2004)
Strogatz, S.H.: Exploring complex networks. Nature 410(8), 268–276 (2001)
Watts, D.J.: Small Worlds, The Dynamics of Networks between Order and Randomness. Princeton University Press, Princeton, New Jersey (1999)
Author information
Authors and Affiliations
Corresponding author
Additional information
AMS 2000 Subject Classifications
Primary—60G70; Secondary—05C80
Rights and permissions
About this article
Cite this article
van den Esker, H., van der Hofstad, R., Hooghiemstra, G. et al. Distances in random graphs with infinite mean degrees. Extremes 8, 111–141 (2005). https://doi.org/10.1007/s10687-006-7963-z
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10687-006-7963-z