Условия связности Интернет-графов

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

Аннотация


Рассматривается конфигурационный граф с 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
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.

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