Informatics and Applications
2018, Volume 12, Issue 2, pp 2-10
ON THE ROBUSTNESS OF CONFIGURATION GRAPHS IN A RANDOM ENVIRONMENT
Abstract
The paper considers configuration graphs with vertex degrees being independent identically distributed random variables following the power-law distribution with a random parameter. The parameter of the vertex degree distribution follows the truncated gamma distribution. The authors study the robustness of such graphs to the two types of destruction processes: random and targeted. The graphs function in a random environment where the values of the vertex degree distribution parameter are chosen separately for each vertex. A comparative analysis of destruction effects on these models and on graphs with the degree distribution common for all vertices and induced by averaging over the distribution parameter has been performed. The conditions under which the study of the graphs' behavior in a random environment can be reduced to the study of the evolution of graphs with an averaged vertex degree distribution are discussed. A comparative analysis of destruction effects of the two types of destruction processes has been performed.
[+] References (17)
- Durrett, R. 2007. Random graph dynamics. Cambridge: Cambridge University Press. 221 p.
- Hofstad, R. 2011. Random graphs and complex networks. Cambridge: Cambridge University Press. Vol. 1. 363 p.
- Cohen, R., K. Erez, D. Ben-Avraham, and S. Havlin.
2000. Resilience of the Internet to random breakdowns. Phys. Rev. Lett. 85:4626-4628.
- Bollobas, B., and O. Riordan. 2004. Robustness and vul-nerability of scale-free random graphs. Internet Math. 1(1):1-35.
- Faloutsos, C., P. Faloutsos, and M. Faloutsos. 1999. On power-law relationships of the internet topology. Comp. Comm. R. 29:251-262.
- Reittu, H., and I. Norros. 2004. On the power-law random graph model of massive data networks. Perform. Evaluation 55:3-23.
- Bollobas, B.A. 1980. A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. Eur. J. Combust. 1:311-316.
- Leri, M., and Yu. Pavlov. 2014. Power-law random graphs' robustness: Link saving and forest fire model. Austrian J. Stat. 43(4):229-236.
- Leri, M., and Yu. Pavlov. 2016. Forest fire models on con-figuration random graphs. Fundam. Inform. 145(3):313- 322.
- Biaconi, G., and A.-L. Barabasi. 2001. Bose-Einstein condensation in complex networks. Phys. Rev. Lett. 86(24):5632-5635.
- Pavlov, Y. 2016. On random graphs in random environment. 11th Conference (International) "Computer Data Analysis and Modeling: Theoretical and Applied Stochastics " Proceedings. Minsk. 177-180.
- Afanasyev, V. I., C. Boinghoff, G. Kersting, and V. A. Vatutin. 2012. Limit theorems for weekly branching processes in random environment. J. Theor. Probab. 25(3):703-732.
- Leri, M., and Y. Pavlov. 2017. On robustness of con-figuration graphs in random environment. 4th Russian Finnish Symposium on Descrete Mathematics Proceedings. Eds. J. Karhumaki and A. Saarela. TUCS lecture notes ser. Turku, Finland: Turku Centre for Computer Science. 26:112-115.
- Leri, M. M. 2015. Pozhar na konfiguratsionnom grafe so sluchaynymi perekhodami ognya po rebram [Forest fire on configuration graph with random fire propagation]. Informatika i ee Primeneniya - Inform. Appl. 9(3):67-73.
- Drossel, B., and F Schwabl. 1992. Self-organized critical forest-fire model. Phys. Rev. Lett. 69:1629-1632.
- Bertoin, J. 2012. Fires on trees. Ann. I. H. Poincare Pr. 48(4):909-921.
- Arinaminparty, N., S. Kapadia, and R. May. 2012. Size and complexity in model financial systems. P. Natl. Acad. Sci. USA 109:18338-18343.
[+] About this article
Title
ON THE ROBUSTNESS OF CONFIGURATION GRAPHS IN A RANDOM ENVIRONMENT
Journal
Informatics and Applications
2018, Volume 12, Issue 2, pp 2-10
Cover Date
2018-05-30
DOI
10.14357/19922264180201
Print ISSN
1992-2264
Publisher
Institute of Informatics Problems, Russian Academy of Sciences
Additional Links
Key words
configuration graphs; power-law distribution; gamma distribution; robustness; forest fire model; simulation
Authors
M. M. Leri  and Yu. L. Pavlov
Author Affiliations
Institute of Applied Mathematical Research of the Karelian Research Centre of the Russian Academy of Sciences, 11 Pushkinskaya Str., Petrozavodsk 185910, Russian Federation
|