×

Limit laws for self-loops and multiple edges in the configuration model. (English. French summary) Zbl 1466.60194

Summary: We consider self-loops and multiple edges in the configuration model as the size of the graph tends to infinity. The interest in these random variables is due to the fact that the configuration model, conditioned on being simple, is a uniform random graph with prescribed degrees. Simplicity corresponds to the absence of self-loops and multiple edges.
We show that the number of self-loops and multiple edges converges in distribution to two independent Poisson random variables when the second moment of the empirical degree distribution converges. We also provide estimations on the total variation distance between the numbers of self-loops and multiple edges and their limits, as well as between the sum of these values and the Poisson random variable to which this sum converges to. This revisits previous works of Bollobás, of Janson, of Wormald and others. The error estimates also imply sharp asymptotics for the number of simple graphs with prescribed degrees.
The error estimates follow from an application of the Stein-Chen method for Poisson convergence, which is a novel method for this problem. The asymptotic independence of self-loops and multiple edges follows from a Poisson version of the Cramér-Wold device using thinning, which is of independent interest.
When the degree distribution has infinite second moment, our general results break down. We can, however, prove a central limit theorem for the number of self-loops, and for the multiple edges between vertices of degrees much smaller than the square root of the size of the graph. Our results and proofs easily extend to directed and bipartite configuration models.

MSC:

60K35 Interacting random processes; statistical mechanics type models; percolation theory
60K37 Processes in random environments
82B43 Percolation
PDFBibTeX XMLCite
Full Text: DOI arXiv Euclid

References:

[1] R. Albert and A.-L. Barabási. Statistical mechanics of complex networks. Rev. Modern Phys.74 (1) (2002) 47-97. · Zbl 1205.82086
[2] N. Alon and J. Spencer. The Probabilistic Method, 2nd edition. Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley & Sons, New York, 2000. · Zbl 0996.05001
[3] A. Barbour, L. Holst and S. Janson. Poisson Approximation. Oxford Studies in Probability.2. The Clarendon Press Oxford University Press, New York, 1992. · Zbl 0746.60002
[4] E. A. Bender and E. R. Canfield. The asymptotic number of labelled graphs with given degree sequences. J. Combin. Theory Ser. A24 (1978) 296-307. · Zbl 0402.05042 · doi:10.1016/0097-3165(78)90059-6
[5] J. Blanchet and A. Stauffer. Characterizing optimal sampling of binary contingency tables via the configuration model. Random Structures Algorithms42 (2) (2013) 159-184. · Zbl 1257.62065 · doi:10.1002/rsa.20403
[6] B. Bollobás. A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. European J. Combin.1 (4) (1980) 311-316. · Zbl 0457.05038
[7] B. Bollobás. Random Graphs, 2nd edition. Cambridge Studies in Advanced Mathematics73. Cambridge University Press, Cambridge, 2001.
[8] T. Britton, M. Deijfen and A. Martin-Löf. Generating simple random graphs with prescribed degree distribution. J. Stat. Phys.124 (6) (2006) 1377-1397. · Zbl 1106.05086
[9] C. Cooper and A. Frieze. The size of the largest strongly connected component of a random digraph with a given degree sequence. Combin. Probab. Comput.13 (3) (2004) 319-337. · Zbl 1065.05085 · doi:10.1017/S096354830400611X
[10] P. Gao and N. Wormald. Enumeration of graphs with a heavy-tailed degree sequence. Adv. Math.287 (2016) 412-450. · Zbl 1327.05155 · doi:10.1016/j.aim.2015.09.002
[11] C. Holmgren and S. Janson. Using Stein’s method to show Poisson and normal limit laws for fringe subtrees. Discrete Math. Theor. Comput. Sci.BA (2014) 169-180. · Zbl 1331.60024
[12] C. Holmgren and S. Janson. Limit laws for functions of fringe trees for binary search trees and random recursive trees. Electron. J. Probab.20 (4) (2015) 1-51. · Zbl 1320.60026
[13] S. Janson. The probability that a random multigraph is simple. Combin. Probab. Comput.18 (1-2) (2009) 205-225. · Zbl 1216.05145 · doi:10.1017/S0963548308009644
[14] S. Janson. The probability that a random multigraph is simple. II. J. Appl. Probab.51A (2014) 123-137. · Zbl 1309.05162 · doi:10.1239/jap/1417528471
[15] S. Janson, M. Luczak and P. Windridge. Law of large numbers for the sir epidemic on a random graph with given degrees. Random Structures Algorithms45 (4) (2014) 724-761. · Zbl 1328.05170 · doi:10.1002/rsa.20575
[16] B. D. McKay and N. C. Wormald. Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\). Combinatorica11 (4) (1991) 369-382. · Zbl 0742.05047 · doi:10.1007/BF01275671
[17] M. Molloy and B. Reed. A critical point for random graphs with a given degree sequence. Random Structures Algorithms6 (2-3) (1995) 161-179. · Zbl 0823.05050 · doi:10.1002/rsa.3240060204
[18] M. Molloy and B. Reed. The size of the giant component of a random graph with a given degree sequence. Combin. Probab. Comput.7 (3) (1998) 295-305. · Zbl 0916.05064 · doi:10.1017/S0963548398003526
[19] M. E. J. Newman. The structure and function of complex networks. SIAM Rev.45 (2) (2003) 167-256 (electronic). · Zbl 1029.68010 · doi:10.1137/S003614450342480
[20] M. E. J. Newman. Random graphs as models of networks. In Handbook of Graphs and Networks 35-68. Wiley-VCH, Weinheim, 2003.
[21] M. E. J. Newman, S. Strogatz and D. Watts. Random graphs with arbitrary degree distribution and their application. Phys. Rev. E64 (2000) 026118.
[22] R. van der Hofstad. Random Graphs and Complex Networks. Cambridge Series in Statistical and Probabilistic Mathematics1. Cambridge University Press, Cambridge, 2017. · Zbl 1361.05002
[23] R. van der Hofstad and J. Komjáthy. When is a scale-free graph ultra-small?. Journ. Stat. Phys.169 (2017) 223-264. · Zbl 1386.60041 · doi:10.1007/s10955-017-1864-1
[24] P. van der Hoorn and N. Litvak. Upper bounds for number of removed edges in the erased configuration model. In Algorithms and Models for the Web Graph 54-65. Lecture Notes in Comput. Sci.9479. Springer, Cham, 2015. · Zbl 1342.05174
[25] N. C. Wormald. The asymptotic distribution of short cycles in random regular graphs. J. Combin. Theory Ser. B31 (2) (1981) 168-182. · Zbl 0442.05042 · doi:10.1016/S0095-8956(81)80022-6
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.