Об условных конфигурационных графах со случайным распределением степеней вершин

Юрий Леонидович Павлов, Yury Pavlov

Аннотация


Рассматривается случайный конфигурационный граф, степени вершин которого независимы и одинаково распределены по дискретному степенному закону. Сумма степеней вершин известна. При стремящимися к бесконечности числе вершин и числе ребер граф развивается в случайной среде, в крторой пораметр распределения степеней вершин равномерно распределен на фиксированном конечном интервале. Найдены предельные распределения максимальной степени вершины и числа вершин заданной степени.

Ключевые слова


случайный конфигурационный граф; случайная среда; степень вершины; предельные теоремы.

Полный текст:

PDF

Литература


Бейтман Г., Эрдейи А. Высшие трансцендентные функции.

Гипергеометрическая функция. Функции Лежандра. М.: Наука, 1965.

с.

Колчин В. Ф. Случайные графы. М.: Физматлит, 2000. 256 с.

Павлов Ю. Л. Предельные распределения объема гигантской

компоненты в случайном графе Интернет-типа // Дискретная

математика. 2007. Т. 19, вып. 3. С. 22--34. doi: 10.4213/dm963

Павлов Ю. Л. Об условных Интернет-графах, степени вершин

которых не имеют математического ожидания // Дискретная

математика. 2010. Т. 22, вып. 3. С. 20--33. doi: 10.4213/dm1104

Павлов Ю. Л., Дертишникова Е. Н. О предельном

распределении максимальной степени вершины в случайном графе

Интернет-типа //~Труды КарНЦ РАН. 2010. № 3, вып. 1. С. 59--65.

Павлов Ю. Л., Степанов М. М. Предельные распределения

числа петель случайного конфигурационного графа //~Труды МИАН им.~В.~А.~Стеклова. 2013. Т. 282. С. 212--230. doi:

1134/S0371968513030175

Павлов Ю. Л., Чеплюкова И. А. Случайные графы

Интернет-типа и обобщенная схема размещения //~Дискретная

математика. 2008. Т. 20, вып. 3. С. 3--18. doi: 10.4213/dm1008

Райгородский А. М. Модели случайных графов. М.: МЦНМО,

136~с.

Самосват Е. А. Моделирование Интернета с помощью

случайных графов: дис. ... канд. физ.-мат. наук. М., 2014. 98~с.

Bianconi G., Barabasi A.-L. Bose-Einstein

condensation in complex networks // Physical

Review Letters. 2001. Vol. 86. P. 5632–5635. doi:

1103/PhysRevLett.86.5632

Bollobas B. A probabilistic proof of an

asymptotic formula for the number of labelled

regular graphs // Eur. J. Comb. 1980. Vol. 1.

P. 311–316. doi: 10.1016/S0195-6698(80)80030-8

Durrett R. Random graph dynamics.

Cambridge University Press. 2006. doi:

1017/CBO9780511546594

Faloutsos C., Faloutsos P., Faloutsos M. On

power-law relationship of the Internet topology

// Computer communications Rev. 1999. Vol. 29.

P. 251–262. doi: 10.1145/316194.316229

Laurinskas A., Garunksis R. The Lerch zetafunction.

Dordrecht: Kluwer, 2002. 189 p.

Reittu H., Norros I. On the power-law

random graph model of massive data networks

// Performance Evaluation. 2004. Vol. 55, no. 4.

P. 3–23. doi: 10.1016/S0166-53/6(3)00097-x

References

Bateman H., Erdelyi A. Higher transcendental

functions. Vol. 1. New York; Toronto; London:

Megraw-hill book company, inc, 1953. 317 p.

Kolchin V. F. Random graphs. Cambridge:

University Press, 1999. 252 p.

Pavlov Yu. L. The limit distribution of the

size of a giant component in an Internettype

random graph. Discrete Mathematics and

Applications. 2007. Vol. 17, iss. 5. P. 425–438. doi:

1515/dma.2007.034

Pavlov Yu. L. On conditional Internet

graphs whose vertex degrees have no

mathematical expectation. Discrete Mathematics

and Applications. 2010. Vol. 20, iss. 5–6. P. 509–

doi: 10.1515/dma.2010.031

Pavlov Yu. L., Dertishnikova E. N. O

predel’nom raspredelenii maksimal’noj stepeni

vershiny v sluchajnom grafe Internet-tipa [On

limit distribution of maximum vertex degree in

random graph of Internet type]. Trudy KarNC

RAN [Transactions of KarRC of RAS]. 2010.

No. 3, iss. 1. P. 59–65.

Pavlov Yu. L., Stepanov M. M. Limit

distributions of the number of loops in a random

configuration graph. Proceedings of the Steklov

Institute of Mathematics. 2013. Vol. 282, iss. 1.

P. 202–219. doi: 10.1134/S0081543813060175

Pavlov Yu. L., Cheplyukova I. A. Random

graphs of Internet type and the generalised

allocation scheme. Discrete Mathematics and

Applications. 2008. Vol. 18, iss. 5. P. 447–464. doi:

1515/DMA.2008.033

Rajgorodskij A. M. Modeli sluchainyh grafov

[Models of random graphs]. Moscow: MCNMO,

136 p.

Samosvat E. A. Modelirovanie Interneta s

pomoshju sluchainyh grafov [Internet modeling

with help of random graphs]: DSc (Cand. of Phys.-

Math.) thesis. Moscow, 2014. 98 p.

Bianconi G., Barabasi A.-L. Bose-Einstein

condensation in complex networks. Physical

Review Letters. 2001. Vol. 86. P. 5632–5635. doi:

1103/PhysRevLett.86.5632

Bollobas B. A probabilistic proof of an

asymptotic formula for the number of labelled

regular graphs. Eur. J. Comb. 1980. Vol. 1. P. 311–

doi: 10.1016/S0195-6698(80)80030-8

Durrett R. Random graph dynamics.

Cambridge University Press. 2006. doi:

1017/CBO9780511546594

Faloutsos C., Faloutsos P., Faloutsos M. On

power-law relationship of the Internet topology.

Computer communications Rev. 1999. Vol. 29.

P. 251–262. doi: 10.1145/316194.316229

Laurinskas A., Garunksis R. The Lerch zetafunction.

Dordrecht: Kluwer, 2002. 189 p.

Reittu H., Norros I. On the power-law

random graph model of massive data networks.

Performance Evaluation. 2004. Vol. 55, no. 4.

P. 3–23. doi: 10.1016/S0166-53/6(3)00097-x




DOI: http://dx.doi.org/10.17076/mat313

Ссылки

  • На текущий момент ссылки отсутствуют.


© Труды КарНЦ РАН, 2014-2019