Abstract
We study the number of edges in the inhomogeneous random graph when vertex weights have an infinite mean and show that the number of edges is O(n log n). Central limit theorems for the number of edges are also established.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bertoin J. Lévy Processes. Cambridge: Cambridge University Press, 1996
Bhamidi S, van der Hofstad R, van Leeuwaarden J. Novel scaling limits for critical inhomogeneous random graphs. Ann Probab, 2012, 1: 2299–2361
Billingsley P. Convergence of Probability Measures. New York: John Wiley & Sons, 1968
Bingham N H, Goldie C M, Teugels J L. Regular Variation. Cambridge: Cambridge University Press, 1987
Britton T, Deijfen M, Martin-Löf A. Generating simple random graphs with prescribed degree distribution. J Stat Phys, 2006, 1: 1377–1397
Chung F, Lu L. The average distances in random graphs with given expected degree. Proc Natl Acad Sci USA, 2002, 1: 15879–15882
Chung F, Lu L. The average distance in a random graph with given expected degrees. Internet Math, 2003, 1: 91–113
Gnedenko B V, Kolmogorov A N. Limit Distributions for Sums of Independent Random Variables. Boston: Addison-Wesley, 1968
Hu Z, Bi W, Feng Q. Limit laws in the generalized random graphs with random vertex weights. Statist Probab Lett, 2014, 1: 65–76
Janson S, Luczak T. A new approach to the giant component problem. Random Structures Algorithms, 2009, 1: 197–216
Janson S, Luczak T, Norros I. Large cliques in a power-law random graph. J Appl Probab, 2009, 1: 1124–1135
Kallenberg O. Random Measures. Berlin-London: Akademie-Verlag and Academic Press, 1986
Kallenberg O. Foundations of Modern Probability. New York: Springer-Verlag, 2002
Koroljuk V S, Borovskich Yu V. Theory of U-Statistics. Amsterdam: Kluwer, 1994
Norros I, Reittu H. On a conditionally Poissonian graph process. Adv Appl Probab, 2006, 1: 59–75
Sato K. Lévy Processes and Infinitely Divisible Distributions. Cambridge: Cambridge University Press, 1999
van den Esker H, van der Hofstad R, Hooghiemstra G. Universality for the distance in finite variance random graphs. J Stat Phys, 2008, 1: 169–202
van der Hofstad R. Critical behavior in inhomogeneous random graphs. Random Structures Algorithms, 2013, 1: 480–508
van der Hofstad R. Random Graphs and Complex Networks, Volume 1. Cambridge: Cambridge University Press, 2017
Acknowledgements
This work was supported by National Natural Science Foundation of China (Grant No. 11671373). The authors thank the anonymous referees for the helpful suggestions that greatly improved the presentation of this work.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Hu, Z., Dong, L. Number of edges in inhomogeneous random graphs. Sci. China Math. 64, 1321–1330 (2021). https://doi.org/10.1007/s11425-018-9549-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11425-018-9549-8