Convergence towards an Erdös-Rényi graph structure in network contraction processes*

Complex networks encountered in biology, ecology, sociology and technology often contract due to node failures, infections or attacks. The ultimate failure, taking place when the network fragments into disconnected components was studied extensively using percolation theory. We show [1-2] that long before reaching fragmentation, contracting networks lose their distinctive features. In particular, we identify that a very large class of network structures, which experience a broad class of node deletion processes, exhibit a stable flow towards a universal fixed point, representing a maximum-entropy ensemble, namely the Erdös-Rényi ensemble characterized by a Poisson degree distribution. This is in sharp contrast to network expansion processes, which lead to diverse families of complex networks, whose structure is highly sensitive to details of the growth mechanism.
These results imply that contracting networks in the late stages of node failure cascades, attacks and epidemics reach a common universal structure, providing a unifying framework for their analysis.

[1] I. Tishby, O. Biham and E. Katzav, Phys. Rev. E 100, 032314 (2019).
[2] I. Tishby, O. Biham and E. Katzav, Phys. Rev. E 101, 062308 (2020).