Условия связности Интернет-графов
Аннотация
Рассматривается конфигурационный граф с N вершинами, степени которых независимы и одинаково распределены по степенному закону, зависящему от медленно меняющейся функции. Они равны числу исходящих из вершин занумерованных полуребер. Граф образуется путем попарного равновероятного соединения полуребер друг с другом для образования ребер. Такие модели можно использовать для адекватного описания различных сетей коммуникаций и топологии сети Интернет. В статье исследуются условия, при выполнении которых случайный конфигурационный графасимптотическисвязен при N->oo. Найдены также оценки скорости сходимости к нулю вероятности того, что граф не связен.
Ключевые слова
Полный текст:
PDFЛитература
Золотарев В. М., Шиганов И. С. Дополнения // Сенета Е. Правильно меняющиеся функции. М.: Наука, 1985. С. 100–131.
Ибрагимов И. А., Линник Ю. В. Независимые и стационарно связанные величины. М.: Наука, 1965. 524 с.
Лукач Е. Характеристические функции. М.: Наука, 1979. 424 с.
Павлов Ю. Л. Об асимптотике степенной структуры условных Интернет-графов // Труды Карельского научного центра РАН. 2020. № 7. С. 77–83. doi: 10.17076/mat1202
Павлов Ю. Л. Об условии связности Интернет-
графа с изменяющимся параметром распределения степеней вершин // Труды Карельского научного центра РАН. 2020. № 7. С. 84–88. doi: 10.17076/mat1170
Павлов Ю. Л. О связности конфигурационных
графов // Дискретная математика. 2019. Т. 31,
вып. 2. С. 115–123. doi: 10.4213/dm1008
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-6698(80)80030-8
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. 2021. URL: https://www.win.
tue.nl/∼rhofstad/NotesRGCNII.pdf (дата обраще-
ния: 15.03.2022).
Reittu H., Norros I. On the effect
of very large nodes in Internet graphs
// GLOBECOM02 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. 55, iss. 1-2.
P. 3–23. doi: 10.1016/S0166-5316(03)00097-X
DOI: http://dx.doi.org/10.17076/mat1560
Ссылки
- На текущий момент ссылки отсутствуют.
![Лицензия Creative Commons](http://i.creativecommons.org/l/by/4.0/88x31.png)
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
© Труды КарНЦ РАН, 2014-2019