Об условии связности Интернет-графа с изменяющимся параметром распределения степеней вершин

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

Аннотация


Рассматривается случайный конфигурационный граф с N вершинами, степени которых независимы и одинаково распределены по степенному закону с параметром t=t(N). Они равны числу исходящих из вершины занумерованных в произвольном порядке полуребер. Граф образуется путем попарного равновероятного соединения полуребер друг с другом для образования ребер. Такие модели можно использовать для адекватного описания топологии различных сетей коммуникаций, включая Интернет. Свойства графа зависят от поведения параметра t. В статье исследуются условия, при выполнении которых случайный конфигурационный граф асимптотически связен, если N стремится к бесконечности.

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


случайный конфигурационный граф; связность графа

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

PDF

Литература


Бейтман Г., Эрдейн А. Высшие трансцендентные функции. Гипергеометрическая функция. Функции Лежандра. М.: Наука, 1965, 296 с.

Павлов Ю.Л. О связности конфигурационных графов//~Дискретная математика. 2019. Т. 31, вып. 2. С. 115-123. doi: 10.4213/dm1573

Павлов Ю.Л., Чеплюкова И.А.} Случайные графы Интернет-типа и обобщенная схема размещения//Дискретная математика. 2008. Т. 20, вып. 3. С. 3-18. doi: 10.4213/dm1008

Hofstad R. Random Graphs and Complex Networks. Volume

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

Reittu H., Norros I.} On the effect of very large nodes in Intrnet graphs GLOBECOM'02. IEEE, 2002. P. 2624-2628. doi: 10.1109/GLOCOM.2002.1189105

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/mat1170

Ссылки

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


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

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