Evolution of Robust Network Topologies: Emergence of Central Backbones

We model the robustness against random failure or an intentional attack of networks with an arbitrary large-scale structure. We construct a block-based model which incorporates—in a general fashion—both connectivity and interdependence links, as well as arbitrary degree distributions and block correlations. By optimizing the percolation properties of this general class of networks, we identify a simple core-periphery structure as the topology most robust against random failure. In such networks, a distinct and small “core” of nodes with higher degree is responsible for most of the connectivity, functioning as a central “backbone” of the system. This centralized topology remains the optimal structure when other constraints are imposed, such as a given fraction of interdependence links and fixed degree distributions. This distinguishes simple centralized topologies as the most likely to emerge, when robustness against failure is the dominant evolutionary force.

Figure 1

(a) Block structure with 10 blocks of equal size. Each node represents a block, and black (red) edges correspond to connectivity (interdependence) edges. Squares (circles) have exponentially (Poisson) distributed connectivity degrees with ${\kappa }_i=2.25$ (${\kappa }_i=1.75$), and ${\widehat{\kappa }}_i=8$ (${\widehat{\kappa }}_i=6$). All interdependence degrees are exponentially distributed. (b) The matrices $e_{rs}$ (black squares) and ${\widehat{e}}_{rs}$ (red squares) that correspond to this ensemble. (c) $S$ as a function of $\varphi$, for random failures. The solid lines are results obtained via Eqs. (1, 2), and the filled symbols are obtained empirically with a network realization of size $N={10}^6$. The two discontinuous jumps correspond to the outer and inner rings failing in sequence.

Figure 2

(a) $S$ as a function of $\varphi$, for random failures, different $\beta$ values, $⟨k⟩=2$, and $\widehat{⟨k⟩}=0$. The solid lines are results obtained via Eqs. (1, 2), and the filled symbols are obtained empirically with a network realization of size $N={10}^6$. The dashed curve close to $\varphi =1$ corresponds to targeted attacks for $\beta \to \infty$. (b) Correlation matrix $e_{rs}/e_r{e}_s$ (top), block sizes $w_r$, and average degrees ${\kappa }_r$, for different $\beta$ values. (c) Ensemble samples with $⟨k⟩=2$ and $N={10}^3$ nodes for different $\beta$ values. The orange (square) nodes belong to the core block.

Figure 3

(a) Robustness $R$ [Eq. (3)] as a function of $\beta$ for different average degrees $⟨k⟩$, with $\widehat{⟨k⟩}=0$. (b),(c) Robustness difference between optimal ensembles $\beta \to \infty$) and random networks ($\beta =0$) with the same $⟨k⟩$, for (b) $\widehat{⟨k⟩}=0$ and (c) $\widehat{⟨k⟩}\ge 1$.

Figure 4

(a) The same as Fig. 2a, with $⟨k⟩=4$, $\widehat{⟨k⟩}=1.1$. (b) The same as Fig. 2b and the same constraints as in (a). The correlation matrix ${\widehat{e}}_{rs}/{\widehat{e}}_r{\widehat{e}}_s$ and average interdependence degrees ${\widehat{\kappa }}_r$ are shown in red. (c) The same as Fig. 2c, with $⟨k⟩=2$, $\widehat{⟨k⟩}=1.1$, and $N={10}^4$. The red edges are interdependence links.

Figure 5

(a),(b) The same as Fig. 2a for (a) random failures and (b) targeted attacks. In both cases the values $w_r$ and ${\kappa }_r$ are kept fixed. (c),(d) Ensemble samples with $N={10}^4$ nodes, $\beta \to \infty$, for (c) random failures and (d) targeted attacks.