Network susceptibilities: Theory and applications

We introduce the concept of network susceptibilities quantifying the response of the collective dynamics of a network to small parameter changes. We distinguish two types of susceptibilities: vertex susceptibilities and edge susceptibilities, measuring the responses due to changes in the properties of units and their interactions, respectively. We derive explicit forms of network susceptibilities for oscillator networks close to steady states and offer example applications for Kuramoto-type phase-oscillator models, power grid models, and generic flow models. Focusing on the role of the network topology implies that these ideas can be easily generalized to other types of networks, in particular those characterizing flow, transport, or spreading phenomena. The concept of network susceptibilities is broadly applicable and may straightforwardly be transferred to all settings where networks responses of the collective dynamics to topological changes are essential.

Figure 1

The global edge susceptibility ${\chi }_{\left(st\right)}$ in a model power grid. (a) Coarse-grained topology of the British high-voltage power transmission grid [9, 25]. We randomly choose 60 nodes to be generators with $P_j=+1$ ($\square$) and 60 nodes to be consumers with $P_j=-1$ ($\circ$). The transmission capacity of all edges is given by $K=4$ in arbitrary units. The color map shows the load $|L_{st}|$ of each edge. (b) Color map plot of the global edge susceptibility ${\chi }_{st}$. (c) For a given network, the susceptibility is approximately proportional to the load of the edge $|L_{st}|$. It is increased if the edge $(s,t)$ couples two weakly connected components of the responsive capacity graph $\tilde{K}$, indicated by a large overlap with the Fiedler vector $|{\mathit{q}}_{st}·{\mathit{v}}_2|$ (shown as a color code and in the inset). (d) On a global scale, the average susceptibility is proportional to the inverse algebraic connectivity $1/a_2$. The plot shows $1/a_2$ ($\square$, right scale) and the ratio ${\chi }_{st}/\left|L_{st}\right|$ averaged over all edges ($\circ$, left scale) as a function of the transmission capacity $K$. The shading shows the standard deviation of ${\chi }_{st}/\left|L_{st}\right|$.

Figure 2

The Vertex-to-vertex susceptibility in uniform and realistic network topologies. (a) Color coded plot of ${\chi }_{s\to t}$ in a $256\times 256$ square grid with uniform free capacities, showing logarithmic decay. The central vertex $s$ was perturbed. (b) Decay behavior of the mean ${\chi }_{s\to t}$ in the same topology as in (a) as a function of shortest path distance $d(s,t)$. The shaded region represents a 95% confidence interval. We clearly see logarithmic decay. (c) Color coded plot of ${\chi }_{s\to t}$ in the Continental European Transmission Network topology with realistic free capacities (taken from Ref. [30]). The vertex positions are not realistic. One central vertex was perturbed. There are several highly susceptible vertices in the network periphery (dark blue). (d) Decay behavior of the mean ${\chi }_{s\to t}$ in the same topology as in (c) as a function of $d(s,t)$. We show both realistic free capacities ${\tilde{K}}_{ij,\mathrm{real}}$ as well as uniform free capacities ${\tilde{K}}_{ij,\mathrm{unif}}=\langle {\tilde{K}}_{\mathrm{real}}\rangle$ set to the mean realistic value. The same vertex as in (c) was perturbed. In the realistic case, few highly susceptible vertices in the network periphery lead to a high variance at large distances, in contrast to the uniform case.

Figure 3

The edge-to-vertex susceptibility in uniform and realistic network topologies. (a) Color coded plot of ${\chi }_{(s,t)\to j}$ in a $256\times 256$ square grid with uniform free capacities. The central edge ((128,128), (128,129)), where the numbers are integer coordinates, was perturbed. (b) Decay behavior of ${\chi }_{\left(st\right)\to j}$ in the same topology as in (a) as a function of shortest path distance $d(s,j)$. The decay has a wide spread due to direction dependence as explained in Ref. (67). (c) Color coded plot of ${\chi }_{\left(st\right)\to j}$ in the Continental European Transmission Network topology with uniform free capacities (taken from Ref. [30]). The vertex positions are not realistic. One central edge was perturbed. (d) Decay behavior of ${\chi }_{\left(st\right)\to j}$ in the same topology as in (c) as a function of $d(s,j)$. The same edge as in (c) was perturbed. The susceptibilities for a single distance are even more widely distributed than in a regular lattice . The straight lines in (b) and (d) are algebraic fits to the upper and lower envelopes of the data set to obtain the exponent of the power-law decay. As the power-law decay breaks down near the boundary due to finite-size effects, we have to choose a cutoff, restricting the fit to the shaded region.

Figure 4

Large susceptibility and desynchronization at dead ends. (a) The edge susceptibility ${\chi }_{s\to j}$ is large for $j=s$ and $j=t$, where $t$ is the dead end adjacent to the vertex $s$. (b, c) Dynamics after a transient increase of the power $P_s$ at the vertex $s$. The impact of the perturbation is strongest for the vertices $s$ and $t$. While $s$ relaxes after a short transient period, the dead end $t$ loses synchrony permanently. We consider the topology of the British high-voltage transmission grid as in Fig. 1, of which only a magnified part is shown. We assume that the moments of inertia $M_j\equiv M$ and the damping coefficient $D_j\equiv D$ are the same for all machines. The machines have power injections of $P_j/M=\pm 1{\mathrm{s}}^{-2}$ and all edges have the transmission capacity $K/M=4{\mathrm{s}}^{-2}$ and $D/M=0.1{\mathrm{s}}^{-1}$.

Figure 5

Change of flow magnitudes $|F_{ij}|$ after (a) the damage ($\kappa =-0.1\times K_{st}$) or (b) the complete outage ($\kappa =-K_{st}$) of a single edge (dashed). We compare the prediction of simple linear response approach, Eq. (21), and the modified formula, Eq. (74), to the results of a numerical solution of the steady-state condition, Eq. (9). Note the different color scales used in the figure. We consider the topology British high-voltage transmission grid as in Fig. 1, of which only a magnified part is shown.

Figure 6

Identification of critical edges using linear response theory. We analyze the effects of the breakdown of a single transmission line for two examples marked by arrows. (a–c) In the upper example, no secondary overloads occur and the grid relaxes back to steady operation after a short transient period. (d–f) In the lower example, linear response theory predicts a secondary overload (black dashed line in d), and consequently the dynamics becomes unstable, as shown in panel (f). (a, d) Loads $|F_{ij}^{\prime \prime }/K_{ij}|$ predicted by the modified linear response formula, Eq. (74). (b, e) Actual load obtained by solving the steady-state condition, Eq. (9). In (e) no steady state exists after the initial breakdown. (c, f) Grid dynamic obtained after the breakdown of the respective edge at $t=0$. We consider the topology of the British high-voltage transmission grid as in Fig. 1, of which only a magnified part is shown. We assume that the moments of inertia $M_j\equiv M$ and the damping coefficient $D_j\equiv D$ are the same for all machines. The machines have power injections of $P_j/M=\pm 1{\mathrm{s}}^{-2}$ and all edges have the transmission capacity $K/M=4{\mathrm{s}}^{-2}$ and $D/M=0.1{\mathrm{s}}^{-1}$.

Figure 7

Performance of different classifiers for the prediction of critical edges. (a, b) Histograms of characteristic quantities to identify critical (thin red line) and stable (thick blue line) edges in complex supply networks: (a) load $|L_{st}|$ before breakdown and (b) the maximum load ${max}_{(i,j)}|F_{ij}^{\prime \prime }/K_{ij}|$ predicted by linear response theory. (c, d) The performance of the classifiers can be judged by a receiver operating characteristics (ROC) curve, where the sensitivity is plotted vs. the false-positive rate for different threshold values $h$. The predicted max. load (solid green line) closely approaches the perfect limit $(0,1)$ and clearly outperforms a classifier based on the load $|L_{st}|$ (dashed). Results are collected for 100 realizations of the British grid with random positions of generators and consumers. One realization is shown in Figs. 5 and 6.