О максимальной степени вершины условного Интернет-графа

Даниил Андреевич Беспалов, Юрий Леонидович Павлов, Daniil Bespalov, Yury Pavlov

Аннотация


Рассматриваются конфигурационные графы с N вершинами, степени которых являются независимыми случайными величинами, распределенными по степенному закону с медленно меняющейся функцией равной 1/zeta(tau), где zeta(tau) - значение зема-функции Римана в точке tau, 1<tau<2. Конфигурационные графы часто используются для моделирования сложных сетей коммуникаций, в частности, Интеренета. Изучается подмножество таких случайных графов при условии, что сумма степеней всех вершин известна и равна n. С помощью обобщенной схемы размещения частиц по ячейкам в работе доказаны теоремы о предельном распределении максимальной степени вершины, при различном характере стремления n,N к бесконечности.

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


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

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

PDF

Литература


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

Павлов Ю.Л. Об асимптотике степенной структуры условных Интернет-графов // Труды КарНЦ РАН. 2020. № 7. C. 77–83. doi: 10.17076/mat1202

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

Павлов Ю.Л., Чеплюкова И.А. Случайные графы Интернет-типа и обобщенная схема размещения // Дискретная математика. 2008. Т. 20, вып. 3. С. 3-18. 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

Durrett R. Random Graph Dynamics. Cambridge: Cambridge University Press, 2006, x+212 p. doi: 10.1017/CBO9780511546594

Hofstad R. Random Graphs and Complex Networks. Volume

One. Cambridge: Cambridge University Press, 2017, 337 p.

doi: 10.1017/9781316779422

Newman M. E. J. The Structure and Function of Complex Networks//SIAM Review. 2003. Vol. 45, iss. 2. P. 167-256. doi: 10.1137/S003614450342480

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

Ссылки

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


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

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