On the limit distributions of the degrees of vertices in configuration graphs with a bounded number of edges

Yu. L. Pavlov   ; E. V. Khvorostyanskaya

Sbornik. Mathematics, Tome 207 (2016) no. 3, pp. 400-417

Résumé

A model of a configuration graph on $N$ vertices is considered in which the degrees of the vertices are distributed identically and independently according to the law $\mathbf P\{\xi=k\}=k^{-\tau}-(k+1)^{-\tau}$, $k=1,2,\dots$, $\tau>0$, and the number of edges is no greater than $n$. Limit theorems for the number of vertices of a particular degree and for the maximum vertex degree as $N,n\to\infty$ are established. Bibliography: 18 titles.

Détail

Keywords: the number of vertices of a particular degree, the maximum vertex degree.
Mots-clés : configuration graph, limit distribution

Bibliographie

[1] C. Faloutsos, P. Faloutsos, M. Faloutsos, “On power-law relationships of the Internet topology”, Computer Communication Rev., 29:4 (1999), 251–262 | DOI

[2] R. Durrett, Random graph dynamics, Camb. Ser. Stat. Probab. Math., Cambridge Univ. Press, Cambridge, 2007, x+212 pp. | MR | Zbl

[3] A.-L. Barabási, R. Albert, “Emergence of scaling in random networks”, Science, 286:5439 (1999), 509–512 | DOI | MR | Zbl

[4] A. M. Raigorodskii, Modeli interneta, Izd. dom “Intellekt”, Dolgoprudnyi, 2013, 64 pp.

[5] 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 | DOI | MR | Zbl

[6] H. Reittu, I. Norros, “On the power-law random graph model of massive data networks”, Performance Evaluation, 55:1-2 (2004), 3–23 | DOI

[7] Yu. L. Pavlov, “The limit distribution of the size of a giant component in an Internet-type random graph”, Discrete Math. Appl., 17:5 (2007), 425–437 | DOI | DOI | MR | Zbl

[8] Yu. L. Pavlov, M. M. Stepanov, “Limit distributions of the number of loops in a random configuration graph”, Proc. Steklov Inst. Math., 282 (2013), 202–219 | DOI | MR | Zbl

[9] Yu. L. Pavlov, I. A. Cheplyukova, “Random graphs of Internet type and the generalised allocation scheme”, Discrete Math. Appl., 18:5 (2008), 447–463 | DOI | DOI | MR | Zbl

[10] Yu. L. Pavlov, “On the limit distributions of the vertex degrees of conditional Internet graphs”, Discrete Math. Appl., 19:4 (2009), 349–359 | DOI | DOI | MR | Zbl

[11] Yu. L. Pavlov, “On conditional Internet graphs whose vertex degrees have no mathematical expectation”, Discrete Math. Appl., 20:5-6 (2010), 509–524 | DOI | DOI | MR | Zbl

[12] A. N. Chuprunov, I. Fazekas, “An analogue of the generalised allocation scheme: limit theorems for the number of cells containing a given number of particles”, Discrete Math. Appl., 22:1 (2012), 101–122 | DOI | DOI | MR | Zbl

[13] V. F. Kolchin, Random graphs, Encyclopedia Math. Appl., 53, Cambridge Univ. Press, Cambridge, 1999, xii+252 pp. | MR | MR | Zbl | Zbl

[14] A. N. Chuprunov, I. Fazekas, “An analogue of the generalised allocation scheme: limit theorems for the maximum cell load”, Discrete Math. Appl., 22:3 (2012), 307–314 | DOI | DOI | MR | Zbl

[15] A. Erdélyi, W. Magnus, F. Oberhettinger, F. G. Tricomi, Higher transcendental functions, Based, in part, on notes left by H. Bateman, v. 1, McGraw-Hill Book Company, Inc., New York–Toronto–London, 1953, xxvi+302 pp. | MR | Zbl | Zbl

[16] I. A. Ibragimov, Yu. V. Linnik, Independent and stationary sequences of random variables, Wolters-Noordhoff Publishing, Groningen, 1971, 443 pp. | MR | MR | Zbl | Zbl

[17] Yu. L. Pavlov, E. V. Feklistova, “Limit distributions of the edge number in random configuration graph”, European Researcher, 48:5-1 (2013), 1097–1100

[18] E. V. Feklistova, Yu. L. Pavlov, “On the behavior of an edge number in a power-law random graph near a critical point”, Third Russian–Finnish symposium on discrete mathematics. Extended abstracts, IAMR KRC RAS, Petrozavodsk, 2014, 112–113