Диаметр конфигурационных графов со степенным распределением

Марина Лери, Marina Leri

Аннотация


Рассматриваются случайные конфигурационные графы с дискретным степенным распределением степеней вершин. Параметр распределения принимает фиксированные значения. Посредством имитационного моделирования найдены оценки диаметра графа. Предложены зависимости диаметра от объема графа и параметра распределения степеней вершин.

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


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

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

PDF

Литература


Лери М. М. Об условиях связности конфигурационных графов // Труды КарНЦ РАН. 2020. № 7. С. 71–75. doi: 10.17076/mat1227

Bollobas B. A probabilistic proof of an asymptotic formula for the number of labelled regular graphs // Eur. J. Combin. 1980. Vol. 1, iss. 4. P. 311–316. doi: 10.1016/S0195-6698(80)80030-8

Bollobas B., Riordan O. M. The diameter of a scale-free random graph // Combinatorica. 2004. Vol. 24, no. 1. P. 5–34. doi: 10.1007/s00493-004-

-2

Chung F., Lu L. The average distances in random graphs with given expected degrees // Proc. of the National Acad. Sci. of the USA. 2002. Vol. 99, iss. 25. P. 15879–15882. doi: 10.1073/pnas.252631999

Dijkstra E. W. A note on two problems in connexion with graphs // Numer. Math. 1959. Vol. 1, iss. 1. P. 269–271. doi: 10.1007/BF01386390

Durrett R. Random graph dynamics. Cambridge: Cambridge Univ. Press, 2007. 221 p.

Faloutsos C., Faloutsos P., Faloutsos M. On power-law relationships of the internet topology // Comp. Comm. Rev. 1999. Vol. 29. P. 251–262. doi: 10.1145/316194.316229

Fernholz D., Ramachandran V. The diameter of sparse random graphs // Random Struct. Alg. 2007. Vol. 31, iss 4. P. 482–516. doi: 10.1002/rsa.20197

Hofstad R. Random graphs and complex networks. Vol. 1. Cambridge: Cambridge Univ. Press, 2017. 337 p. doi: 10.1017/9781316779422

Hofstad R. Random graphs and complex networks. 2018. Vol. 2. 314 p.

URL: https://www.win.tue.nl/∼rhofstad/NotesRGCNII.pdf (дата обращения: 25.04.2021).

Newman M. E. J. The structure and function of complex networks // SIAM Rev. 2003. Vol. 45, iss. 2. P. 167–256. doi: 10.1137/S003614450342480

Reittu H., Norros I. On the power-law random graph model of massive data networks // Performance Evaluation. 2004. Vol. 55, iss. 1-2. P. 3–23. doi: 10.1016/S0166-5316(03)00097-X

References in English

Leri M. M. Ob usloviyakh svyaznosti konfiguratsionnykh grafov [On conditions of configuration graphs’ connectivity]. Trudy KarNTs RAN [Trans. KarRC RAS]. 2020. No. 7. P. 71–75. doi: 10.17076/mat1227




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

Ссылки

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


Лицензия Creative Commons
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.

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