Geodesic
Limit distributions of the number of loops in a~random configuration graph
Informatics and Automation, Branching processes, random walks, and related problems, Tome 282 (2013), pp. 212-230.

Voir la notice de l'article provenant de la source Math-Net.Ru

We consider a random graph constructed by the configuration model with the degrees of vertices distributed identically and independently according to the law $\mathbf P\{\xi\geq k\}=k^{-\tau}$, $k=1,2,\dots$, with $\tau\in(1,2)$. Connections between vertices are then equiprobably formed in compliance with their degrees. This model admits multiple edges and loops. We study the number of loops of a vertex with given degree $d$ and its limiting behavior for different values of $d$ as the number $N$ of vertices grows. Depending on $d=d(N)$, four different limit distributions appear: Poisson distribution, normal distribution, convolution of normal and stable distributions, and stable distribution. We also find the asymptotics of the mean number of loops in the graph. 
@article{TRSPY_2013_282_a16,
     author = {Yu. L. Pavlov and M. M. Stepanov},
     title = {Limit distributions of the number of loops in a~random configuration graph},
     journal = {Informatics and Automation},
     pages = {212--230},
     publisher = {mathdoc},
     volume = {282},
     year = {2013},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TRSPY_2013_282_a16/}
}
TY  - JOUR
AU  - Yu. L. Pavlov
AU  - M. M. Stepanov
TI  - Limit distributions of the number of loops in a~random configuration graph
JO  - Informatics and Automation
PY  - 2013
SP  - 212
EP  - 230
VL  - 282
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/TRSPY_2013_282_a16/
LA  - ru
ID  - TRSPY_2013_282_a16
ER  - 
%0 Journal Article
%A Yu. L. Pavlov
%A M. M. Stepanov
%T Limit distributions of the number of loops in a~random configuration graph
%J Informatics and Automation
%D 2013
%P 212-230
%V 282
%I mathdoc
%U http://geodesic.mathdoc.fr/item/TRSPY_2013_282_a16/
%G ru
%F TRSPY_2013_282_a16
Yu. L. Pavlov; M. M. Stepanov. Limit distributions of the number of loops in a~random configuration graph. Informatics and Automation, Branching processes, random walks, and related problems, Tome 282 (2013), pp. 212-230. http://geodesic.mathdoc.fr/item/TRSPY_2013_282_a16/

[1] Bender E.A., Canfield E.R., “The asymptotic number of labeled graphs with given degree sequences”, J. Comb. Theory A, 24:3 (1978), 296–307 | DOI | MR | Zbl

[2] Bollobás B., “A probabilistic proof of an asymptotic formula for the number of labelled regular graphs”, Eur. J. Comb., 1 (1980), 311–316 | DOI | MR | Zbl

[3] Faloutsos M., Faloutsos P., Faloutsos Ch., “On power-law relationships of the Internet topology”, SIGCOMM'99, Proc. Conf. on Applications, Technologies, Architectures, and Protocols for Computer Communication, Comput. Commun. Rev., 29, ACM, New York, 1999, 251–262 | DOI

[4] Gnedenko B., “Sur la distribution limite du terme maximum d'une série alétorie”, Ann. Math. Ser. 2, 44 (1943), 423–453 | DOI | MR | Zbl

[5] van der Hofstad R.W., Hooghiemstra G., Znamenski D., “Distances in random graphs with finite mean and infinite variance degrees”, Electron. J. Probab., 12 (2007), 703–766 | MR | Zbl

[6] Ibragimov I.A., Linnik Yu.V., Nezavisimye i statsionarno svyazannye velichiny, Nauka, M., 1965

[7] Janson S., “The probability that a random multigraph is simple”, Comb. Probab. Comput., 18 (2009), 205–225 | DOI | MR | Zbl

[8] Janson S., Łuczak T., Ruciński A., Random graphs, Wiley, New York, 2000 | MR | Zbl

[9] Molloy M., Reed B., “A critical point for random graphs with a given degree sequence”, Random Struct. Algorithms, 6 (1995), 161–179 | DOI | MR | Zbl

[10] Newman M.E.J., Strogatz S.H., Watts D.J., “Random graphs with arbitrary degree distributions and their applications”, Phys. Rev. E, 64 (2001), 026118 | DOI

[11] Pavlov Yu.L., “On power-law random graphs and branching processes”, Computer data analysis and modeling: Complex stochastic data and systems, Proc. 8th Int. Conf., V. 1, Belarus. State Univ., Minsk, 2007, 92–98

[12] Reittu H., Norros I., “On the power-law random graph model of massive data networks”, Perform. Eval., 55 (2004), 3–23 | DOI

[13] Sevastyanov B.A., Vetvyaschiesya protsessy, Nauka, M., 1971 | MR | Zbl

[14] Stepanov M., “On the loop number of a node of random graph “Internet-type””, Optimal stopping and stochastic control, Abstr. Int. Workshop., Petrozavodsk, 2005, 65