Сравнение устойчивости конфигурационных графов в случайной среде

Марина Муксумовна Лери, Marina Leri

Аннотация


Рассматриваются случайные конфигурационные графы, где распределение степеней вершин является дискретным степенным распределением со случайным параметром,
имеющим усеченное нормальное распределение на интервале (a,b). Проводится анализ устойчивости таких графов к случайным и направленным разрушениям, как с точки зрения сохранения связности, так и к разрушениям по типу <<лесного пожара>>. В первом случае получены модели зависимости объема максимальной компоненты графа, а также вероятности его разрушения от процента удаленных вершин и начального размера графа. В случае
<<лесного пожара>> основным объектом рассмотрения было число оставшихся в графе после <<пожара>> вершин. Наряду с двумя случаями <<начала пожара>>: случайным возгоранием и направленным поджогом вершины с наибольшей степенью, рассматривались два вида
распространения пожара: с фиксированной вероятностью распространения огня по ребрам и со случайной.

Для обоих видов внешнего воздействия проведено сравнение результатов с полученными ранее для случаев фиксированного значения параметра распределения степеней вершин и параметра, равномерно распределенного на отрезке [a,b].


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


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

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

PDF

Литература


Литература

Лери М. М. Пожар на конфигурационном графе со случайными переходами огня по ребрам // Информатика и ее применения. 2015. Т. 9, вып. 3. С. 67-73. doi: 10.14357/19922264150307

Afanasyev V. I., Boinghoff C., Kersting G., Vatutin V. A.} Limit theorems for weekly branching processes in random environment // Journal of Theoretical Probability. 2012. Vol. 25, iss. 3. P. 703-732. doi: 10.1007/s10959-010-0331-6

Arinaminparty N., Kapadia S., May R. Size and complexity in model financial systems // Proc. Natl. Acad. Sci. USA. 2012. Vol. 109, no. 45. P. 18338-18343. doi: 10.1073/pnas.1213767109

Bertoin J. Fires on trees // Annales de l'Institut Henri Poincare Probabilites et Statistiques. 2012. Vol. 48, no. 4. P. 909-921. doi: 10.1214/11-AIHP435

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

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

Bollobas B., Riordan O. Robustness and vulnerability of scale-free random graphs // Internet Mathematics. 2004. Vol. 1, no. 1. P. 1-35. doi: 10.1080/15427951.2004.10129080

Drossel B., Schwabl F. Self-organized critical forest-fire model // Physical Review Letters. 1992. Vol. 69, iss. 11. P. 1629-1632. doi: 10.1103/PhysRevLett.69.1629

Durrett R. Random Graph Dynamics. Cambridge: Cambridge University Press, 2007. 221 p.

Hofstad R. Random Graphs and Complex Networks. Vol. 1. Cambridge: Cambridge University Press, 2017. 337 p.

Leri M., Pavlov Yu. Power-law random graphs' robustness: Link saving and forest fire model // Austrian J. Stat. 2014. Vol. 43, no. 4. P. 229-236. doi: 10.17713/ajs.v43i4.34

Leri M., Pavlov Y. Forest fire models on configuration random graphs // Fundamenta Informaticae. 2016. Vol. 145, iss. 3. P. 313-322. doi: 10.3233/FI-2016-1362

Leri M., Pavlov Yu. Random graphs' robustness in random environment // Austrian J. Stat. 2017. Vol. 46, no. 3-4. P. 89-98. doi: 10.17713/ajs.v46i3-4.674

Norros I., Reittu H. Attack Resistance of Power-law Random Graphs in the Finite Mean, Infinite Variance Region // Internet Mathematics. 2008. Vol. 5, no. 3. P. 251-266. doi: 10.1080/15427951.2008.10129162

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

REFERENCES in ENGLISH

Leri M. M. Pozhar na konfiguratsionnom grafe so sluchainymi perekhodami ognya po rebram [Fire in a configuration graph with random fire propagation on edges]. Informatics and Applications. 2015. Vol. 9, iss. 3. P. 67-73. doi: 10.14357/19922264150307

Afanasyev V. I., Boinghoff C., Kersting G., Vatutin V. A. Limit theorems for weekly branching processes in random environment // Journal of Theoretical Probability. 2012. Vol. 25, iss. 3. P. 703-732. doi: 10.1007/s10959-010-0331-6

Arinaminparty N., Kapadia S., May R. Size and complexity in model financial systems // Proc. Natl. Acad. Sci. USA. 2012. Vol. 109, no. 45. P. 18338-18343. doi: 10.1073/pnas.1213767109

Bertoin J. Fires on trees // Annales de l'Institut Henri Poincare Probabilites et Statistiques. 2012. Vol. 48, no. 4. P. 909-921. doi: 10.1214/11-AIHP435

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

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

Bollobas B., Riordan O. Robustness and vulnerability of scale-free random graphs // Internet Mathematics. 2004. Vol. 1, no. 1. P. 1-35. doi: 10.1080/15427951.2004.10129080

Drossel B., Schwabl F. Self-organized critical forest-fire model // Physical Review Letters. 1992. Vol. 69, iss. 11. P. 1629-1632. doi: 10.1103/PhysRevLett.69.1629

Durrett R. Random Graph Dynamics. Cambridge: Cambridge University Press, 2007. 221 p.

Hofstad R. Random Graphs and Complex Networks. Vol. 1. Cambridge: Cambridge University Press, 2017. 337 p.

Leri M., Pavlov Yu. Power-law random graphs' robustness: Link saving and forest fire model // Austrian J. Stat. 2014. Vol. 43, no. 4. P. 229-236. doi: 10.17713/ajs.v43i4.34

Leri M., Pavlov Y. Forest fire models on configuration random graphs // Fundamenta Informaticae. 2016. Vol. 145, iss. 3. P. 313-322. doi: 10.3233/FI-2016-1362

Leri M., Pavlov Yu. Random graphs' robustness in random environment // Austrian J. Stat. 2017. Vol. 46, no. 3-4. P. 89-98. doi: 10.17713/ajs.v46i3-4.674

Norros I., Reittu H. Attack Resistance of Power-law Random Graphs in the Finite Mean, Infinite Variance Region // Internet Mathematics. 2008. Vol. 5, no. 3. P. 251-266. doi: 10.1080/15427951.2008.10129162

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

Ссылки

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


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

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