Global robustness versus local vulnerabilities in complex synchronous networks

In complex network-coupled dynamical systems, two questions of central importance are how to identify the most vulnerable components and how to devise a network making the overall system more robust to external perturbations. To address these two questions, we investigate the response of complex networks of coupled oscillators to local perturbations. We quantify the magnitude of the resulting excursion away from the unperturbed synchronous state through quadratic performance measures in the angle or frequency deviations. We find that the most fragile oscillators in a given network are identified by centralities constructed from network resistance distances. Further defining the global robustness of the system from the average response over ensembles of homogeneously distributed perturbations, we find that it is given by a family of topological indices known as generalized Kirchhoff indices. Both resistance centralities and Kirchhoff indices are obtained from a spectral decomposition of the stability matrix of the unperturbed dynamics and can be expressed in terms of resistance distances. We investigate the properties of these topological indices in small-world and regular networks. In the case of oscillators with homogeneous inertia and damping coefficients, we find that inertia only has small effects on robustness of coupled oscillators. Numerical results illustrate the validity of the theory.

Figure 1

Ratio of the performance measures ${\mathcal{P}}_1$ for graph (a) vs. (e) of Fig. 2 (shown in the insets), for a quench perturbation of magnitude $\delta P_0=0.01$ and duration $\gamma {\tau }_0=500$ on node $k=1,2,3,...20$ (see text). On average, graph (e) is four times more robust to external perturbations than graph (a) (blue dashed line). However, some nodes of graph (a) can be more robust than those of graph (e) (red crosses correspond to quench perturbation applied on the red nodes shown in the inset). Both specific local vulnerabilities (crosses) and global averaged robustness (blue dashed lines) are well predicted by combinations of local centralities, and global topological indices (orange solid line, see text).

Figure 2

Six networks with $n=20$ nodes obtained by the rewiring procedure of Ref. [48], starting from a cyclic graph and rewiring every edge of the network with a probability $p=0.15$ (a), $p=0.3$ (b), $p=0.45$ (c), $p=0.6$ (d), $p=0.75$ (e), and $p=0.9$ (f). The node numbering used in Fig. 3 is indicated in panel (a).

Figure 3

Performances measures ${\mathcal{P}}_1$ (left) and ${\mathcal{P}}_2$ (right) for the graphs of Fig. 2 (top), Fig. 2 (middle), Fig. 2 (bottom), and a quench perturbation of magnitude $\delta P_0=0.01$ on node $k$. Numerical results (circles) and analytical Eqs. (17) (solid lines) are plotted for different durations of perturbation $\gamma {\tau }_0=0.5$ (black), 1 (blue), 10 (red), 100 (green). The asymptotic values of short and long ${\tau }_0$ given in Eqs. (20) (dotted line) and (21) (dashed line) are shown, vertically shifted by an arbitrary amount for clarity. The node numbering is given in Fig. 2.

Figure 4

Resistance centralities $C_1\left(k\right)$ (top) and $C_2\left(k\right)$ (bottom), given in Eqs. (3) and (7), respectively, for the six graphs of Fig. 2.

Figure 5

Comparison between $C_1\left(k\right)$ and $C_2\left(k\right)$ for the six graphs of Fig. 2 (see inset).

Figure 6

Time-evolution of angles (left) and frequencies (right) following a quench perturbation applied on node 6 (top panels) and 11 (bottom panels) of graph (f) in Fig. 2 with $\gamma {\tau }_0=50$. The trajectory of the perturbed oscillator is shown in red. Angles and frequencies spread more when the perturbation is applied on node 6 than on node 11, in agreement with predictions of Eqs. (21) since node 6 has the smallest, node 11 the largest centrality in this graph.

Figure 7

Trajectories of angles and phases for the graphs of Fig. 2 with $p=0.15$ (top) and $p=0.9$ (bottom) obtained by numerically time-evolving Eq. (10) for the same quench perturbation with $\gamma {\tau }_0=50$ applied on the node colored in red in the insets. In the four left panels, perturbed nodes are close to median value of $C_2\left(k\right)$, respectively, in graph with $p=0.15$ (top) and $p=0.9$ (bottom). In the four right panels, perturbed nodes are the most (top) and least (bottom) central ones according to $C_2\left(k\right)$, respectively, in graph with $p=0.15$ and $p=0.9$.

Figure 8

Averaged performances measures $\langle {\mathcal{P}}_1^{\infty }\rangle$, $\langle {\mathcal{P}}_2^{\infty }\rangle$ for the graphs of Fig. 2 obtained numerically (circles) and predicted analytically, Eqs. (17) (solid lines) for perturbations with $\gamma {\tau }_0=0.5$ (black), 1 (blue), 10 (red), 100 (green). The asymptotic values of short and long ${\tau }_0$ given in Eqs. (22) (dotted line) and (23) (dashed line) are shown, vertically shifted by an arbitrary amount for clarity.

Figure 9

Left panel: clustering coefficient $Cl$, average geodesic distance $l$ and generalized Kirchhoff indices $K{f}_1$ and $K{f}_2$, as a function of the rewiring probability $p$ for Strogatz-Watts rewired networks [48]. Each data point corresponds to an average over 30 realizations of randomly rewired graphs, obtained from an initial cyclic graph with $n=1000$ nodes and nearest to $10\mathrm{th}$-nearest neighbor coupling, where each edge is randomly rewired with a probability $p$ (parameters chosen similar as in Ref. [48], such that the graph remains connected while rewiring and is still sparse). Right panel: ratio of the Kirchhoff indices and of clustering coefficient vs. average geodesic distance. Small-world network are easily identified by the steepest slope of the orange line.

Figure 10

Generalized Kirchhoff indices $K{f}_1$ (green) and $K{f}_2$ (purple) given in Eq. (25), for a cyclic network with $n=50$ nodes with nearest and $q\mathrm{th}$-nearest-neighbor coupling. The inset sketches the model for $q=17$, 19, and 24 and with one path involving $q\mathrm{th}$ range coupling starting from node 1 (red). The addition of the $q\mathrm{th}$-nearest-neighbor coupling does not reduce geodesic distance between the reference node (red) and the set of nodes colored in blue.