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

Ирина Александровна Чеплюкова, Irina Cheplyukova

Аннотация


Рассматриваются конфигурационные графы с N вершинами. Степени вершин являются независимыми одинаково распределенными случайными величинами, распределение которых удовлетворяет следующему условию: при k → ∞
pk = P{η = k} ∼ h(k) / kg , 2 < g < 3,
где h(k) – медленно меняющаяся на бесконечности функция. Изучаются случайные графы при условии, что сумма степеней всех вершин равна n. Найдены предельные распределения числа вершин заданной степени в таком условном графе при N, n → ∞ так, что h(N)n2N(4−3g)/(g−1) ≥ C > 0.

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


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

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

PDF

Литература


Колчин В. Ф. Случайные графы. М.: Физмат-лит, 2000. 256 с.

Павлов Ю. Л. О структуре условных конфигурационных графов с ограниченным числом ребер // Труды Карельского научного центра РАН. 2025. № 4. С. 54–59. doi: 10.17076/mat2041

Павлов Ю. Л. Условные конфигурационные графы со случайным параметром степенного распределения степеней // Математический сборник. 2018. Т. 209, № 2. С. 120–137. doi: 10.4213/sm8832

Павлов Ю. Л., Хворостянская Е. В. О предельных распределениях степеней вершин конфигурационных графов с ограниченным числом ребер // Математический сборник. 2016. Т. 207, № 3. С. 93–110. doi: 10.4213/sm8512

Павлов Ю. Л., Чеплюкова И. А. Об асимптотике степенной структуры конфигурационных графов с ограничениями на число ребер // Дис- кретная математика. 2018. Т. 30, № 1. С. 77–94. doi: 10.4213/dm1445

Павлов Ю. Л., Чеплюкова И. А. Предельные распределения числа вершин заданной степени конфигурационного графа с ограниченным числом ребер // Теория вероятностей и ее применения. 2021. Т. 66, № 3. С. 468–486.doi: 10.4213/tvp5332

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

Чеплюкова И. А. О максимальной степени вершины условного конфигурационного графа // Теория вероятностей и ее применения. 2026. Т. 71, № 1. С. 78–94. doi: 10.4213/tvp5776

Чеплюкова И. А. О предельных распределениях степеней вершин конфигурационного графа // Труды Карельского научного центра РАН. 2015. № 10. С. 123–130. doi: 10.17076/mat138

Чупрунов А. Н., Фазекаш И. Аналог обобщенной схемы размещения. Предельные теоремы для числа ячеек заданного объема // Дискретная математика. 2012. Т. 24, № 1. С. 140–158. doi: 10.4213/dm1178

Barabasi L. A., Albert R. Emergence of scaling in random networks // Science. 1999. No. 286. P. 509–512. doi:10.1126/science.286.5439.509

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

Durrett R. Random graph dynamics. Cambridge: Cambridge Univ. Press, 2007. 233 p. doi: 10.1017/ CBO9780511546594

Faloutsos C., Faloutsos P., Faloutsos M. On power-law relationship of the Internet topology// Comput. Commun. Rev. 1999. No. 29. P. 251–262. doi: 10.1145/316194.316229

Hofstad R. Random graphs and complex networks. Vol. 1. Cambridge: Cambridge Univ. Press, 2017. 337 p. doi: 10.1017/9781316779422

Newman M. E. J. Networks. An introduction. Oxford: Oxford Univ. Press, 2010. 772 p.

Reittu Y., Norros I. On the power-law random graph model of massive data networks // Perform. Eval. 2004. Vol. 55, no. 1–2. P. 3–23. doi: 10.1016/S0166-5316(03)00097-X




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

Ссылки

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


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

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