Geodesic
On limit behavior of maximum vertex degree in a conditional configuration graph near critical points
Diskretnaya Matematika, Tome 28 (2016) no. 2, pp. 58-70.

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

We consider configuration graphs with $N$ vertices. The degrees of vertices are independent identically distributed random variables having the power-law distribution with parameter $\tau>0$. There are two critical values of this parameter: $\tau=1$ and $\tau=2$. The properties of a graph change significantly when $\tau=\tau(N)$ passes these points as $N\to\infty$. Let $G_{N, n}$ be the subset of random graphs under the condition that sum of degrees of its vertices is equal to $n$. The limit theorem for the maximum vertex degree in $G_{N, n}$ as $N, n\to\infty$ and $\tau\to 1$ or $\tau\to 2$ is proved.
Keywords: random graph, configuration graph, maximum vertex degree, power-law distribution, critical point, limit theorems. 
@article{DM_2016_28_2_a5,
     author = {Yu. L. Pavlov and E. V. Feklistova},
     title = {On limit behavior of maximum vertex degree in a conditional configuration graph near critical points},
     journal = {Diskretnaya Matematika},
     pages = {58--70},
     publisher = {mathdoc},
     volume = {28},
     number = {2},
     year = {2016},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2016_28_2_a5/}
}
TY  - JOUR
AU  - Yu. L. Pavlov
AU  - E. V. Feklistova
TI  - On limit behavior of maximum vertex degree in a conditional configuration graph near critical points
JO  - Diskretnaya Matematika
PY  - 2016
SP  - 58
EP  - 70
VL  - 28
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2016_28_2_a5/
LA  - ru
ID  - DM_2016_28_2_a5
ER  - 
%0 Journal Article
%A Yu. L. Pavlov
%A E. V. Feklistova
%T On limit behavior of maximum vertex degree in a conditional configuration graph near critical points
%J Diskretnaya Matematika
%D 2016
%P 58-70
%V 28
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2016_28_2_a5/
%G ru
%F DM_2016_28_2_a5
Yu. L. Pavlov; E. V. Feklistova. On limit behavior of maximum vertex degree in a conditional configuration graph near critical points. Diskretnaya Matematika, Tome 28 (2016) no. 2, pp. 58-70. http://geodesic.mathdoc.fr/item/DM_2016_28_2_a5/

[1] Watts D. J., Strogatz S. H.,, “Collective dynamics of "small-world-networks”, Nature, 393 (1998), 440–442 | DOI

[2] Barabasi A. L., Albert R., “Emergence of scaling in random network”, Science, 286 (1999), 509–512 | DOI | MR | Zbl

[3] Newman M. E. J., “The structure and function of complex networks”, SIAM Rev., 45 (2003), 167–256 | DOI | MR | Zbl

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

[5] Durrett R., Random graph dynamics, Cambridge Univ. Press, 2007, 224 pp. | MR | Zbl

[6] Bollobas 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

[7] Faloutsos M., Faloutsos P., Faloutsos C., “On power-law relationships of the Internet topology”, Proc. of the ACM/SIGCOMM'99, 1999, 251–261

[8] Bollobas B., Riordan O., “The diameter of a scale-free random graph”, Combinatorica, 24 (2004), 5–34 | DOI | MR | Zbl

[9] Pavlov Yu. L., “Predelnye raspredeleniya ob'ema gigantskoi komponenty v sluchainom grafe Internet-tipa”, Diskretnaya matematika, 19:3 (2007), 22–34 | DOI | MR | Zbl

[10] Pavlov Yu. L., Stepanov M. M., “Predelnye raspredeleniya chisla petel sluchainogo konfiguratsionnogo grafa”, Tr.MIAN im. V.A. Steklova, 282 (2013), 212–230 | MR | Zbl

[11] Newman M. E. J., Strogatz S. H., Watts D. J., “Random graphs with arbitrary degree distribution and their applications”, Phys.Rev.E., 64 (2001), 1–17

[12] Aiello W., Chung F., Lu L., “A random graph model for massive graphs”, Proc. 32nd ACM Symp. Theory of Comput., 2000, 171–180 | MR | Zbl

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

[14] Pavlov Yu. L., Cheplyukova I. A., “Sluchainye grafy Internet-tipa i obobschennaya skhema razmescheniya”, Diskretnaya matematika, 20:3 (2008), 3–18 | DOI | MR | Zbl

[15] Kolchin V. F., Sluchainye grafy, Fizmatlit, Moskva, 2000, 256 pp. ; Kolchin V. F., Random Graphs, Cambridge University Press, 1998, 268 pp. | MR | MR

[16] Pavlov Yu. L., “O predelnykh raspredeleniyakh stepenei vershin v uslovnykh Internet-grafakh”, Diskretnaya matematika, 21:3 (2009), 14–23 | DOI | MR | Zbl

[17] Pavlov Yu. L., Dertishnikova E. N., “O predelnom raspredelenii maksimalnoi stepeni vershiny v sluchainom grafe Internet-tipa”, Trudy Karelskogo nauchnogo tsentra RAN, seriya Matematicheskoe modelirovanie i informatsionnye tekhnologii, 3 (2010), 59–65

[18] Pavlov Yu. L., “Ob uslovnykh Internet-grafakh, stepeni vershin kotorykh ne imeyut matematicheskogo ozhidaniya”, Diskretnaya matematika, 22:3 (2010), 20–33 | DOI | MR | Zbl

[19] Bateman H., Erdelyi A., Higher Transcendental functions, 1, McGraw-Hill Book Company, Inc., 1953, 316 pp. ; Beitman G., Erdeii A., Vysshie transtsendentnye funktsii. Gipergeometricheskaya funktsiya. Funktsiya Lezhandra, Nauka, Moskva, 1965 | MR

[20] Kolchin V. F., Sluchainye otobrazheniya, M.: Nauka, 1984, 208 pp. ; Kolchin V. F., “Random mappings”, Trans. Ser. in Math. and Eng., Optimization Software Inc. Publications Division, New York, 1986, 207 pp. | MR | MR | Zbl