Random Graphs' Robustness in Random Environment


  • Marina Leri Russian Academy of Sciences
  • Yury Pavlov Russian Academy of Sciences




We consider configuration graphs the vertex degrees of which are independent and
  follow the power-law distribution. Random graphs dynamics takes place in a random
  environment with the parameter of vertex degree distribution following
  uniform distributions on finite fixed intervals. As the number of vertices tends
  to infinity the limit distributions of the maximum vertex degree and the number
  of vertices with a given degree were obtained. By computer simulations we study
  the robustness of those graphs from the viewpoints of link saving and node survival
  in the two cases of the destruction process: the ``targeted attack'' and the
  ``random breakdown''. We obtained and compared the results under the conditions that
  the vertex degree distribution was averaged with respect to the distribution of the
  power-law parameter or that the values of the parameter were drawn from the uniform
  distribution separately for each vertex.


Arinaminparthy N, Kapadia S, May R (2012). Size and Complexity in Model Financial Systems. Proceedings of the National Academy of Sciences of the USA, 109, 18338-18343.

Bertoin J (2011). Burning Cars in a Parking Lot. Commun. Math. Phys., 306, 261-290.

Bertoin J (2012). Fires on Trees. Annales de l'Institut Henri Poincare Probabilites et Statistiques, 48(4), 909-921.

Bianconi G, Barabasi AL (2001). Bose-Einstein Condensation in Complex Networks. Physical Review Letters, 86, 5632-5635.

Bollobas B (1980). A Probabilistic Proof of an Asymptotic Formula for the Number of Labelled Regular Graphs. Eur. J. Comb., 1, 311-316.

Bollobas B, Riordan O (2004). Robustness and Vulnerability of Scale-free Random Graphs. Internet Mathematics, 1(1), 1-35.

Drossel B, Schwabl F (1992). Self-organized Critical Forest-fire Model. Phys. Rev. Lett., 69, 1629-1632.

Durrett R (2007). Random Graph Dynamics. Cambridge Univ. Press, Cambridge.

Faloutsos C, Faloutsos P, Faloutsos M (1999). On Power-law Relationships of the Internet Topology. Computer Communications Rev., 29, 251-262.

Leri M (2016). Forest Fire Model on Configuration Graphs with Random Node Degree Distribution. In XVII-th International Summer Conference on Probability and Statistics: Conference Proceedings and Abstracts, pp. 29-32.

Leri M, Pavlov Y (2014). Power-law Random Graphs' Robustness: Link Saving and Forest Fire Model. Austrian Journal of Statistics, 43(4), 229-236.

Leri M, Pavlov Y (2016). Forest Fire Models on Configuration Random Graphs. Fundamenta Informaticae, 145(3), 313-322.

Mahadevan P, Krioukov D, Fomenkov M, Huffaker B, Dimitropoulos X, Claffy K, Vahdat A (2006). The Internet AS-Level Topology: Three Data Sources and One Definitive Metric. ACM SIGCOMM Computer Communication Review (CCR), 36(1), 17-26.

Norros I, Reittu H (2008). Attack Resistance of Power-law Random Graphs in the Finite Mean, Infinite Variance Region. Internet Mathematics, 5(3), 251-266.

Pavlov Y (2016). On Conditional Configuration Graphs with Random Distribution of Vertex Degrees. Transactions of Karelian Research Centre of Russian Academy of Science: Mathematical Modeling and Information Technologies, 8, 62-72. In Russian.

Reittu H, Norros I (2004). On the Power-law Random Graph Model of Massive Data Networks. Performance Evaluation, 55, 3-23.



How to Cite

Leri, M., & Pavlov, Y. (2017). Random Graphs’ Robustness in Random Environment. Austrian Journal of Statistics, 46(3-4), 89-98. https://doi.org/10.17713/ajs.v46i3-4.674