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

Марина Муксумовна Лери, Marina Leri

Аннотация


Рассматриваются конфигурационные графы, степени вершин которых имеют дискретное степенное распределение с фиксированным параметром. Посредством имитационного моделирования оценивается среднее расстояние (среднее арифметическое всех расстояний между всеми парами вершин графа), и рассматриваются две характеристики: минимальное среднее расстояние в графе и максимальное. В работе строятся зависимости этих характеристик от объема графа и параметра распределения степеней вершин и строится эмпирический доверительный интервал среднего расстояния в степенном конфигурационном графе.

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


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

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

PDF

Литература


Bollobas B. A probabilistic proof of an

asymptotic formula for the number of labelled

regular graphs // European J. Comb. 1980.

Vol. 1, iss. 4. P. 311–316. doi: 10.1016/S0195-

(80)80030-8

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

Hofstad R. Random graphs and complex

networks. Vol. One. Cambridge: Cambridge Univ.

Press, 2017. 337 p. doi: 10.1017/9781316779422

Hofstad R. Random graphs and complex

networks. Vol. 2. 2018. URL: https://www.win.

tue.nl/∼rhofstad/NotesRGCNII.pdf (дата обраще-

ния: 20.04.2022)

Newman M. E. J. Networks. An Introduction.

Oxford: Oxford Univ. Press, 2010. 772 p.

doi: 10.1093/acprof:oso/9780199206650.001.0001

Newman M. E. J. Networks. Second edition.

Oxford: Oxford Univ. Press, 2018. 800 p.

doi: 10.1093/oso/9780198805090.001.0001

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




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

Ссылки

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


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

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