О максимальной модулярности случайных конфигурационных графов

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

Аннотация


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

 


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


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

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

PDF

Литература


Ибрагимов И.А., Линник Ю.В. Независимые и стационарно связанные величины. М.: Наука, 1965, 524 с.

Barabasi A.-L., Albert R. Emergence of scaling in random networks//~Science. 1999. Vol. 286. P.

--512. doi: 10.1126/science286.5499.509

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

Durrett R. Random Graph Dynamics. Cambridge: Cambridge University Press, 2007, 223 p. doi: 10.1017/CBO9780511546594

Guimera R., Sales-Prado M., Amaral L.A.N. Modularity from fluctuation in random graphs and complex networks//~Physical Review E70. 2004. 025101. doi: 10.1103/PhysRevE.70.025101

Hofstad R. Random Graphs and Complex Networks. Volume

One. Cambridge: Cambridge University Press, 2017, 337 p. doi: 10.1017/9781316779422

McDiarmid C., Sherman F. Modularity of Erdos-Renyi random graphs//~29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis and Algorithms. LIPIcs. 2018. Vol. 110. P. 31.1--31.18. doi: 10.4230/LIPIcs.AofA.2018.31

Newman M.E.J., Girvan M. Finding and evaluating community structure in networks//~Physical Review E69. 2004. 026113.

doi: 10.1103/PhysRewE.69.026113

Newman M.E.J. Fast algorithm for detecting community structure in networks//~Physical Review E69. 2004. 066133.

doi: 10.1103/PhysRewE.69.066133

Newman M.E.J. Modularity and community structure in networks//~PNAS. 2006. Vol. 103, iss. 23. P. 8577--8582. doi: 10.1073/pnas.0602103

Prokhorenkova L., Pralat P., Raigorodskii A.V. Modularity in several random graph models.//~Electronic Notes in Discrete Mathematics. 2017. Vol. 61. 23. P. 941--953. doi: 10.1016/j.endm.2017.07.058

Reittu H., Norros I. On the power-law random graph model

of massive data networks //~Performance Evaluation. 2004. Vol.

, no~4. P. 3--23. doi: 10.1016/S0166-53/6(3)00097-x




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

Ссылки

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


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

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