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

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

Аннотация


Рассматриваются конфигурационные графы с N вершинами. Степени вершин являются независимыми одинаково распределенными случайными величинвми, имеющими дискретное степенное распределение с положительным параметром r. Они равны числу занумерованных в произвольном порядке полуребер. Граф строится путем попарного равновероятного соединения полуребер для образования ребер. Изучается подмножество таких случайных графов при условии, что сумма степеней известна и равна n. Пусть r является случайной величиной, имеющей усеченное нормальное распределение на произвольном фиксированном конечном интервале. Для максимальной степени вершины и числа вершин заданной степени найдены предельные распределения в различных зонах стремления N и n к бесконечности.

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


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

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

PDF

Литература


Лери М. М., Павлов Ю. Л. Об устойчивости конфигурационных графов в случайной среде // Информатика и ее применения (в печати).

Павлов Ю. Л. О предельных распределениях степеней вершин в условных Интернетграфах // Дискретная математика. 2009. Т. 21, вып. 3. С. 14–23. doi: 10.4213/dm1057

Павлов Ю. Л. Об условных Интернетграфах, степени вершин которых не имеют математического ожидания // Дискретная математика. 2010. Т. 22, вып. 3. С. 20–33. doi: 10.4213/dm1104

Павлов Ю. Л. Об условных конфигурационных графах со случайным распределением степеней вершин // Труды КарНЦ РАН. 2016. № 8. С. 62–72. doi: 10.17076/mat313

Павлов Ю. Л. Один случай предельного поведения степеней вершин в условных конфигурационных графах// Труды КарНЦ РАН. 2017. № 8. С. 66–75. doi: 10.17076/mat613

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

Павлов Ю. Л., Дертишникова Е. Н. О предельном распределении максимальной степени вершины в случайном графе Интернет-типа // Труды КарНЦ РАН. 2010. № 3. С. 59–65.

Павлов Ю. Л., Феклистова Е. В. О предельном поведении максимальной степени вершины условного конфигурационного графа вблизи критических точек // Дискретная математика. 2016. Т. 28, вып. 2. С. 58–70. doi: 10.4213/dm1369

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

Самосват Е. А. Моделирование Интернета с помощью случайных графов: дис. ... канд. физ.-мат. наук. М., 2014. 98 с.

Bianconi G., Barabasi A.-L. Bose-Einstein condensation in complex networks // Physical Review Letters. 2001. Vol. 86. P. 5632–5635. doi: 10.1103/PhysRevLett.86.5632

Leri M., Pavlov Yu. Power-law random graph’s robustness: link saving and forest fire model // Austrian Journal of Statistics. 2014. Vol. 43, no. 4. P. 229–236.

Leri M., Pavlov Yu. Forest Fire Models on Configuration Random Graphs // Fundamenta Informaticae. 2016. Vol. 145, no. 3. P. 313–322.

Hofstad R. Random Graphs and Complex Networks. Volume One. Cambridge University Press, 2017. 337 p.

Reittu H., Norros I. On the power-law random graph model of massive data networks // Performance Evaluation. 2004. Vol. 55, no. 4. P. 3–23. doi: 10.1016/S0166-53/6(3)00097-x Поступила в редакцию 27.01.2018

REFERENCES in ENGLISH

Leri M. M., Pavlov Yu. L. Ob ustoichivosti konfiguratsionnykh grafov v sluchainoi srede [On robustness of configuration graphs in random environment]. Informatika i ee primenenija [Informatics and its applications] (in print).

Pavlov Yu. L. On the limit distributions of the vertex degrees of conditional Internet graphs. Discrete Mathematics and Applications. 2009. Vol. 19, iss. 4. P. 349-360. doi: 10.1515/DMA.2009.023

Pavlov Yu. L. On conditional Internet graphs whose vertex degrees have no mathematical expectation. Discrete Mathematics and Applications. 2010. Vol. 20, iss. 5-6. P. 509–524. doi: 10.1515/dma.2010.031

Pavlov Yu. L. Ob uslovnykh konfiguratsionnykh grafakh so sluchainym raspredeleniem stepenei vershin [On conditional configuration graphs with random distribution of vertex degrees]. Trudy KarNTs RAN [Trans. KarRC RAS]. 2016. No. 8. P. 62–72. doi: 10.17076/mat313

Pavlov Yu. L. Odin sluchai predel’nogo

povedenija stepenei vershin v uslovnykh konfiguratsionnykh grafakh [A case of limit behaviour of vertex degrees in conditional configuration graphs]. Trudy KarNTs RAN. [Trans. KarRC RAS]. 2017. No. 8. P. 66–75. doi: 10.17076/mat613

Pavlov Yu. L. Conditional configuration graphs with random parameter of the power-law degree distribution. SB MATH. 2018 (in print). doi: 10.1070/SM8832

Pavlov Yu. L., Dertishnikova E. N. O predel’nom raspredelenii maksimal’noj stepeni vershiny v sluchajnom grafe Internet-tipa [On limit distribution of maximum vertex degree in a random graph of Internet type]. Trudy KarNTs RAN [Trans. KarRC RAS]. 2010. No. 3, iss. 1. P. 59–65. doi: 10.17076/mat313

Pavlov Yu. L., Feklistova E. V. On limit behaviour of maximum vertex degree in a conditional configuration graph near critical points. Discrete Mathematics and Applications. 2017. Vol. 27, iss. 4. P. 213–222. doi: 10.1515/dma2017-0023

Pavlov Yu. L., Cheplyukova I. A. Random graphs of Internet type and the generalised allocation scheme. Discrete Mathematics and Applications. 2008. Vol. 18, iss. 5. P. 447–464. doi: 10.1515/DMA.2008.033

Samosvat E. A. Modelirovanie Interneta s pomosh’ju sluchainykh grafov [Internet modeling with help of random graphs]: DSe (Cand. of Phys.-Math) thesis. Moscow, 2014. 98 p

Bianconi G., Barabasi A.-L. Bose-Einstein condensation in complex networks. Physical Review Letters. 2001. Vol. 86. P. 5632–5635. doi: 10.1103/PhysRevLett.86.5632

Leri M., Pavlov Yu. Power-law random graph’s robustness: link saving and forest fire model. Austrian Journal of Statistics. 2014. Vol. 43, no. 4. P. 229–236.

Leri M., Pavlov Yu. Forest Fire Models on Configuration Random Graphs. Fundamenta Informaticae. 2016. Vol. 145, no. 3. P. 313–322. 14. Hofstad R. Random Graphs and Complex Networks. Volume One. Cambridge University Press, 2017. 337 p.

Reittu H., Norros I. On the power-law random graph model of massive data networks. Performance Evaluation. 2004. Vol. 55, no. 4. P. 3–23. doi: 10.1016/S0166-53/6(3)00097-x




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

Ссылки

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


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

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