Extreme vulnerability to intruder attacks destabilizes network dynamics Authors: Amirhossein Nazerian, Sahand Tangerami, Malbor Asllani, David Phillips, Hernán Makse, Francesco Sorrentino Published: 2026 ABSTRACT Consensus, synchronization, formation control, and power grid balance are examples of desirable dynamical states that arise in networks. Here we investigate how such states can be destabilized by an intruder agent within an otherwise functioning network. We see that a single adversarial node, coupled through adversarial connections to one or more other nodes, is sufficient to destabilize the entire network. We further show that concentrating the attack on a single low-indegree node induces the greatest instability, challenging the common assumption that hubs are the most critical nodes. This leads to a new characterization of network vulnerability, identifying low-indegree nodes as the most vulnerable components. Although derived for linear systems, our results extend to nonlinear networks, including the Kuramoto model. These findings reveal an intrinsic vulnerability of technological, social, and biological networks. Introduction Complex networks are ubiquitous in technological, biological, and social systems. It is often the case that the nodal dynamics of these networks evolve over time to reach a well-defined dynamical state, such as consensus in opinion dynamics, synchronization in oscillator networks, or a desired pattern in coupled autonomous systems1–3. Ensuring the robustness of such networks against failures and attacks is a critical research challenge4. Robustness has been studied extensively from both structural and dynamical perspectives5–8. Traditional approaches to studying network robustness, including structural attacks such as cascading failures via percolation theory and node or edge removals, have offered valuable insights. Structural interventions, such as cascade failures9–12, node or edge removals12,13, and network fragmentation14, examine how disruptions alter the network’s connectivity. Alternatively, network instabilities may arise from the presence of adversarial connections between the nodes of a network15–17. In contrast to cascading failures, which are triggered by the removal of nodes or edges, adversarial interactions correspond to the addition of links with negative weights. Such interactions have been reported in brain networks as inhibitory connections between neurons17, in social networks as antagonistic relationships between agents15, and in distributed control systems as faulty or corrupted communication processes16. While both cascading failures9,10,18,19 and instabilities induced by adversarial interactions can disrupt network functionality, they operate through fundamentally different mechanisms. Cascading failures typically unfold as discrete, far-from-equilibrium processes, whereas adversarial interactions affect an existing equilibrium through continuous dynamical effects. In this work, we focus on the latter mechanism, namely the destabilization induced by adversarial connections. Although distinct in nature, both edge removals and adversarial interactions can ultimately lead to network instability. A fundamental question, with significant societal and technological implications, is how desired dynamical network states (such as coordinated dynamical states in networks of drones or autonomous vehicles) can be disrupted by the purposeful insertion of one or a few adversarial agents. In particular, this is relevant to the case of cyber-attacks (CAs) against cyber-physical systems (CPSs) and critical infrastructures, such as power grids20, autonomous vehicle fleets21, and industrial networks22. Since CAs target the cyber (software) level, while leaving the physical (hardware) level unaltered, they can be effectively modeled as network nodes that have the same structure as the others, but act adversarially. Because CPSs rely on synchronization and coordination among such agents to ensure stability and proper functionality23, the presence of even a small number of adversarial nodes can directly undermine these mechanisms, rendering CPSs particularly vulnerable to attacks that disrupt synchronization24. Thus, an essential step in order to develop resilience against cyber-attacks is to understand the mechanisms by which one or a few intruder agents within an otherwise functioning network may compromise its dynamics. Our work also extends to attacks against social networks and biological networks, which we demonstrate using the classical Kuramoto model25. Many real-world networks are highly directed, non-normal, and hierarchically organized, structural features known to strongly shape their dynamical response26–37. In such systems, asymmetries in the interaction pattern generate preferred source-to-sink directions of flow, while the network architecture is often close to acyclic, with only sparse or weak feedback loops. As a consequence, perturbations do not need to spread isotropically: they can be transiently amplified, strongly biased downstream, and funneled toward terminal or sink components31,34,37. These features naturally call for spectral measures that capture both stability and transient amplification when assessing vulnerability to adversarial attacks. For all the cases of consensus, synchronization, formation control, power grid balance, and Kuramoto-type dynamics, we will see that the most vulnerable components of a network are the low-indegree nodes, where the indegree of node i is defined as the sum of the weights of the connections directed to node i, as opposed to the hubs on which much previous work has focused4. Thus, while attacks targeting the hubs usually lead to more severe cascading failures, attack strategies that leverage adversarial interactions are more effective when targeting nodes with low indegree. The general theme of this paper is illustrated in Fig. 1 through an example. Figure 1 (a) displays a network of drones attempting to attain a desired formation. The intruder attack consists in a single intruder node establishing an adversarial connection with one of the network nodes, which is shown in (b). The bottom panels of Fig. 1 are pictorial representations of the spatial trajectories of the drones before and after the attack: in (c), they converge to a set of desired target positions; in (d), they diverge from the target positions, due to the interactions with the intruder.Fig. 1Illustration of an intruder attack on a network of drones attaining a given formation.The top panels show a network of coupled drones, before (A) and after (B) an intruder attack. The bottom panels display the trajectories of the drones before the attack in (C), showing convergence to the target positions, and after the attack in (D), showing divergence from the target position. The target positions are represented as stars in (C) and (D). Illustration of an intruder attack on a network of drones attaining a given formation. The top panels show a network of coupled drones, before (A) and after (B) an intruder attack. The bottom panels display the trajectories of the drones before the attack in (C), showing convergence to the target positions, and after the attack in (D), showing divergence from the target position. The target positions are represented as stars in (C) and (D). Results This paper investigates the case of intruder attacks on networks, where our definition of an intruder is a network node that obeys the same individual dynamics and communicates with the same output function as the other network nodes, but acts maliciously in order to disrupt the network dynamics. In terms of the mathematical model, this means that an intruder node obeys the same individual (uncoupled) dynamics and it uses the same output function as the other nodes in the network, but it interacts with the remaining nodes in a purposefully adversarial way. In what follows, we mathematically formulate the problem of intruder attacks on networks and derive rigorous conditions to quantify their destabilizing effects on the dynamics. Although our results extend to both undirected and directed networks, we focus principally on the latter as real-world systems are usually characterized by directional interactions27,31,34,38. We first focus on the important case of the linear consensus problem in networks and then consider other types of network dynamics, including formation control, power grid stability, and synchronization in oscillator networks. Our work reveals an intrinsic vulnerability in technological systems, such as autonomous networks, power grids, and sensor systems, emphasizing the need for a deeper understanding of these weaknesses and the development of specific strategies to mitigate them. We consider a general set of equations for the network dynamics, 1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\dot{{{{\boldsymbol{x}}}}}}_{i}(t)={{{\boldsymbol{F}}}}({{{{\boldsymbol{x}}}}}_{i}(t))-{\sum }_{j=1}^{N}{L}_{ij}{{{\boldsymbol{H}}}}({{{{\boldsymbol{x}}}}}_{j}(t)-{{{\boldsymbol{\beta}}}}_{j}),\quad i=1,...,N,$$\end{document}x°i(t)=F(xi(t))−∑j=1NLijH(xj(t)−βj),i=1,...,N, where xi(t) is the m-dimensional state of node i at time t and N is the number of nodes. The individual nodal dynamics is given by F(xi(t)), and the output of node j is given by the function H(xj(t) − \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{\boldsymbol{\beta}}}}_{j}$$\end{document}βj) where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{\boldsymbol{\beta}}}}_{j}$$\end{document}βj is an m-dimensional constant vector that acts as a coordinate shift (\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{\boldsymbol{\beta}}}}_{j}$$\end{document}βj may be zero). The network connectivity is described by a digraph with adjacency matrix A = [Aij], where Aij is the strength of the directed coupling from node j to node i ≠ j, Aij > 0 indicates a cooperative interaction (also sometimes called mutualistic or attractive), Aij < 0 indicates an adversarial interaction (also sometimes called competitive or repulsive), and Aij = 0 indicates no interaction. The indegree of node i is equal to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${d}_{i}^{in}={\sum }_{j\ne i}{A}_{ij}$$\end{document}diin=∑j≠iAij and the outdegree of node i is equal to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${d}_{i}^{out}={\sum }_{j\ne i}{A}_{ji}$$\end{document}diout=∑j≠iAji. The Laplacian matrix is denoted by L = [Lij] where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${L}_{ij}=({\delta }_{ij}{d}_{i}^{in}-{A}_{ij})$$\end{document}Lij=(δijdiin−Aij), and δij is the Kronecker delta. By construction, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\sum }_{j=1}^{N}{L}_{ij}=0,\forall i$$\end{document}∑j=1NLij=0,∀i. For clarity, we note that two sign conventions for the Laplacian matrix are used in the literature: one with off-diagonal entries equal to the adjacency matrix and diagonal entries equal to the negative indegrees, and one with off-diagonal entries equal to the negative adjacency matrix and diagonal entries equal to the indegrees. In this work, we adopt the latter convention. We proceed under the assumption that the Laplacian matrix L is ‘proper’, i.e., all the eigenvalues of L have non-negative real parts, and there is only one eigenvalue equal to 0. Conditions for the Laplacian matrix of a signed digraph to be proper have been thoroughly investigated in the literature15–17. Ref. 39 (Definition 2.32) defines, for a given Laplacian matrix L, the following algebraic connectivity \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f\in {\mathbb{R}}$$\end{document}f∈R which may be considered as a generalization of the Fiedler value40 for digraphs: 2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f(L):={{\min }_{{{{\boldsymbol{X}}}}\ne {{{\boldsymbol{0}}}},{{{\boldsymbol{X}}}}\perp 1}}\frac{{{{{\boldsymbol{X}}}}}^{\top }L{{{\boldsymbol{X}}}}}{{{{{\boldsymbol{X}}}}}^{\top }{{{\boldsymbol{X}}}}}={\lambda }_{\min }\left({V}^{\top }\frac{L+{L}^{\top }}{2}V\right).$$\end{document}f(L):=minX≠0,X⊥1X⊤LXX⊤X=λminV⊤L+L⊤2V. Here, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$V\in {{\mathbb{R}}}^{N\times N-1}$$\end{document}V∈RN×N−1 is an orthonormal basis for the null subspace of 1⊤, i.e., V is a matrix whose columns are normal and orthogonal to one another and have zero column sums, and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\lambda }_{\min }(S)$$\end{document}λmin(S) indicates the smallest eigenvalue of the symmetric matrix S. Note that if L is symmetric (the graph is undirected), the Fiedler value of the Laplacian α = f≥0, where the strict inequality is achieved if and only if the graph is connected. The algebraic connectivity f is relevant to studying the synchronization and consensus stabilities of directionally coupled networks. Also, f appears in studying the contractivity of such dynamics and their respective Lyapunov functions, e.g., see ref. 39(Corollary 4.23). Note that for f < 0, − f measures the time scale of the unstable dynamics. We consider the presence of an adversarial agent, labeled as node N + 1, and that this agent is described by the same functions F and H as the remaining nodes. As a result, the network equations can be written, 3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\dot{{{{\boldsymbol{x}}}}}}_{i}(t)={{{\boldsymbol{F}}}}({{{{\boldsymbol{x}}}}}_{i}(t))-\mathop{\sum }_{j=1}^{N+1}{{L}_{aug}}_{ij}{{{\boldsymbol{H}}}}({{{{\boldsymbol{x}}}}}_{j}(t)-{{{\boldsymbol{\beta}}}}_{j}),$$\end{document}x°i(t)=F(xi(t))−∑j=1N+1LaugijH(xj(t)−βj),i = 1, . . . , N + 1, where the augmented Laplacian matrix Laug is either equal to 4\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${L}_{aug}^{b}=\left[\begin{array}{cc}L+\,{{\mbox{diag}}}\,({{{\boldsymbol{b}}}})&-{{{\boldsymbol{b}}}}\\ -{{{{\boldsymbol{b}}}}}^{\top }&-c\end{array}\right]$$\end{document}Laugb=L+diag(b)−b−b⊤−c in the case that the intruder is bidirectionally coupled to the network nodes or equal to 5\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${L}_{aug}^{u}=\left[\begin{array}{cc}L+\,{\mbox{diag}}\,({{{\boldsymbol{b}}}})&-{{{\boldsymbol{b}}}}\\ {{{{\boldsymbol{0}}}}}^{\top }&0\end{array}\right]$$\end{document}Laugu=L+diag(b)−b0⊤0 in the case that the intruder is unidirectionally coupled to the network nodes. In both (4) and (5) the vector b = [bi ≤ 0], b ≠ 0 (i.e., at least one bi < 0) contains the weights with which the additional node connects to nodes 1, . . . , N. A negative (zero) weight bi indicates the presence (absence) of an adversarial connection between the intruder and node i. Furthermore, we introduce the attack budget, defined as the positive quantity \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$c=-{\sum }_{i=1}^{N}{b}_{i}$$\end{document}c=−∑i=1Nbi, which is taken to be equal to the sum of the negatives of the weights of all the connections established by the intruder with the existing network nodes. A fundamental realization of the general dynamics (1), which we will analyze in detail in what follows, is that of the single-integrator consensus dynamics, described by the equation, 6\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\dot{{{{\boldsymbol{X}}}}}(t)=-L{{{\boldsymbol{X}}}}(t),$$\end{document}X°(t)=−LX(t), in the N-dimensional state vector X = [x1, x2, . . . , xN] (xi here is a scalar). When the Laplacian matrix is proper, Eq. (6) reaches consensus asymptotically independent of its initial condition, i.e., \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\lim }_{t\to \infty }}{x}_{i}(t)=\bar{x}$$\end{document}limt→∞xi(t)=x¯, i = 1, . . . , N, where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\bar{x}$$\end{document}x¯ is the consensus state41. In Supplementary Note 1, we provide an example of single-integrator consensus dynamics (6) on a network subject to a single intruder attack to further motivate the relevance of the algebraic connectivity f. In this example, the intruder unidirectionally connects to different network nodes, resulting in different values of the algebraic connectivity f as the Laplacian matrix \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${L}_{aug}^{u}$$\end{document}Laugu changes. In all cases, we see that after the intruder connects to one of the other nodes, the individual trajectories xi(t) diverge from one another. We characterize consensus in terms of the time evolution of the norm of the perturbations about the consensus state 7\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\parallel \delta {{{\boldsymbol{X}}}}(t)\parallel :=\sqrt{\mathop{\sum }_{j=1}^{N}{\left({x}_{j}(t)-\frac{1}{N}{\sum }_{k=1}^{N}{x}_{k}(t)\right)}^{2}}.$$\end{document}∥δX(t)∥:=∑j=1Nxj(t)−1N∑k=1Nxk(t)2. Consensus is achieved if ∥δX(t)∥ → 0 as t → ∞. Definition 1 Destabilization of the single-integrator consensus dynamics. By construction, the Laplacian matrix has one eigenvalue equal to zero. The consensus dynamics (6) is: (i) stable iff all the remaining eigenvalues have positive real part and (ii) unstable iff at least one of the remaining eigenvalues has negative real part. Consequently, we call a destabilization a transition from (i) to (ii). We take the original Laplacian matrix L to be proper, which guarantees that consensus is achieved prior to the attack. However, the addition of a single adversarial connection with the intruder implies that the resulting augmented Laplacian matrices \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${L}_{aug}^{b}$$\end{document}Laugb and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${L}_{aug}^{u}$$\end{document}Laugu are no longer proper, as they are known to possess at least one eigenvalue with negative real part (see e.g.,16,17) and, as a consequence, consensus is not achieved. While the addition of a single adversarial connection with the intruder produces a destabilization, in this paper, we focus not on α(Laug), the asymptotic rate of instability for ∥δX(t)∥, but rather on its transient rate of instability ∣f(Laug)∣≥∣α(Laug)∣ immediately following the attack. As detailed in Subsection A of the Methods, a larger transient growth arises from the non-normal dynamics characteristic of directed networks27,42. We emphasize the transient rate for three main reasons: (i) when Eq. (1) is obtained via linearization about an unstable synchronous solution35, it accurately describes the dynamics only shortly after the perturbation, rendering the asymptotic rate less relevant; (ii) the transient rate provides a worst-case estimate, as it is greater than or equal to the asymptotic rate; and (iii) larger transient growth increases the likelihood that a perturbation produces a significant alteration of the system dynamics27–30,35. Supplementary Note 1 also reviews some of the relevant properties of the algebraic connectivity f from ref. 39. In principle, one could consider the presence of more than one intruder; however, we show in what follows that under appropriate conditions, a single attacker is able to destabilize the network dynamics, so we focus on the case of a single attacker. The case of multiple intruders is studied in Supplementary Note 2. Next, we introduce our two main problems, which we call attack via bidirectional connections and attack via unidirectional connections. Problem 1 Statement: Attack via bidirectional connections. Given the N-dimensional possibly asymmetric Laplacian matrix L, and a budget − c, find the weights b = [bi], bi≤0, i = 1, …, N, with ∑ibi = − c≤0 such that the algebraic connectivity f of the new graph with Laplacian matrix \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${L}_{aug}^{b}$$\end{document}Laugb in Eq. (4) is minimized. Proposition 2 Given − c ≤ 0 and the Laplacian matrix \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${L}_{aug}^{b}$$\end{document}Laugb in Eq. (4), the minimum algebraic connectivity f is achieved when \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${b}_{{i}^{*}}=-c$$\end{document}bi*=−c for one node i* and bi = 0 for all other nodes i ≠ i*, i.e., the entire budget must be allocated to one node. Proof See Methods IV B. □ Proposition 3 Given a budget − c ≤ 0 in Problem 1, the algebraic connectivity is f ≤ 0. Proof See Methods IV C. □ Problem 2 Statement: Attack via unidirectional connections. Given the N-dimensional possibly asymmetric Laplacian matrix L, and a budget − c, find the weights b = [bi], bi ≤ 0, i = 1, …, N, with ∑ibi = − c ≤ 0 such that the algebraic connectivity f of the new graph with the Laplacian matrix \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${L}_{aug}^{u}$$\end{document}Laugu in Eq. (5) is minimized. Proposition 4 Given − c ≤ 0 and the Laplacian matrix \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${L}_{aug}^{u}$$\end{document}Laugu in Eq. (5), the minimum algebraic connectivity f is achieved when \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${b}_{{i}^{*}}=-c$$\end{document}bi*=−c for one node i* and bi = 0 for all other nodes i ≠ i*, i.e., the entire budget must be allocated to one node. Proof See Methods IV D. □ Proposition 5 Given a budget − c ≤ 0 in Problem 2, the algebraic connectivity is f ≤ 0. Proof See Methods IV E. □ Propositions 2 and 4 are used in the next subsections to characterize the effect of the particular selection of the network nodes to which the intruder should connect, i = 1, . . , N, in order to maximize the severity of the attack. Supplementary Note 3 discusses the case of bidirectional attacks in undirected networks with symmetric Laplacian matrices, for which we also prove that the optimal attack is to allocate the entire budget to one node. Balanced directed graphs Next, we investigate in detail the case of interest that the directed graph is balanced, i.e., for each one of its nodes, the indegree equals the outdegree, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${d}_{i}={d}_{i}^{in}={d}_{i}^{out},i=1,..,N$$\end{document}di=diin=diout,i=1,..,N (di is simply the degree of node i.) Undirected graphs form a particular class within the broader class of balanced directed graphs. Based on Propositions 2 and 4, we know that the optimal attack is to allocate the entire budget on one connection only. In what follows, we study the attack to node i of a given network, i.e., we set b = [bj], bi = − c, bj≠i = 0. We are interested in how the algebraic connectivity f of a balanced directed graph is affected by an intruder attack. By using matrix perturbation theory, we study Problem 1 in the limit of very small and very large budget c and obtain that:for small budget c: the algebraic connectivity \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f({L}_{aug}^{b})=-1.1c$$\end{document}f(Laugb)=−1.1c, andfor large budget c: the algebraic connectivity \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f({L}_{aug}^{b})=-2c+L_{ii}/2$$\end{document}f(Laugb)=−2c+Lii/2.For details on the derivations, see Methods, Digraphs with a Bidirectional Connection. Note the dependence on the degree of node i, di = Lii. for small budget c: the algebraic connectivity \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f({L}_{aug}^{b})=-1.1c$$\end{document}f(Laugb)=−1.1c, and for small budget c: the algebraic connectivity \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f({L}_{aug}^{b})=-1.1c$$\end{document}f(Laugb)=−1.1c, and for large budget c: the algebraic connectivity \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f({L}_{aug}^{b})=-2c+L_{ii}/2$$\end{document}f(Laugb)=−2c+Lii/2. for large budget c: the algebraic connectivity \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f({L}_{aug}^{b})=-2c+L_{ii}/2$$\end{document}f(Laugb)=−2c+Lii/2. Using a similar approach, we can also study Problem 2 and obtain that:for small budget c: the algebraic connectivity \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f({L}_{aug}^{u})=-0.1c$$\end{document}f(Laugu)=−0.1c, andfor large budget c: the algebraic connectivity \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f({L}_{aug}^{u})=-\frac{\sqrt{2}+1}{2}c+(3+2\sqrt{2}){L}_{ii}$$\end{document}f(Laugu)=−2+12c+(3+22)Lii.For details of the derivations, see Methods, Digraphs with a Unidirectional Connection. Also in this case, note the dependence on the degree of node i, di = Lii. for small budget c: the algebraic connectivity \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f({L}_{aug}^{u})=-0.1c$$\end{document}f(Laugu)=−0.1c, and for small budget c: the algebraic connectivity \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f({L}_{aug}^{u})=-0.1c$$\end{document}f(Laugu)=−0.1c, and for large budget c: the algebraic connectivity \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f({L}_{aug}^{u})=-\frac{\sqrt{2}+1}{2}c+(3+2\sqrt{2}){L}_{ii}$$\end{document}f(Laugu)=−2+12c+(3+22)Lii. for large budget c: the algebraic connectivity \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f({L}_{aug}^{u})=-\frac{\sqrt{2}+1}{2}c+(3+2\sqrt{2}){L}_{ii}$$\end{document}f(Laugu)=−2+12c+(3+22)Lii. Figure 2 summarizes the results of this section by providing a schematic for how the algebraic connectivity f varies with the magnitude of the budget c. The top (bottom) panel is for the case of Problem 1 (Problem 2.) The figure shows that our calculations in the small and large budget limits can be used to sketch the dependence of the algebraic connectivity on c. In both panels, it is shown that the slopes in the small- and large-c limits are constant, while the intercept of the large-c asymptote increases with the node degree. This indicates that the algebraic connectivity is minimized when the node degree is minimal. Let us further remark that the above result should be interpreted in the context of the adopted Laplacian. More precisely, in the appropriate cost limit, the optimal node ranking is determined by the diagonal entries Lii of the adopted coupling operator. For example, for the symmetrically normalized Laplacian43, Lii = 1 for all i, and therefore this distinction between nodes vanishes.Fig. 2Schematic dependence of the algebraic connectivity on the attack budget.Panels (A, B) schematically illustrate the algebraic connectivity, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f({L}_{aug}^{b})$$\end{document}f(Laugb) and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f({L}_{aug}^{u})$$\end{document}f(Laugu), of the asymmetric Laplacian matrices \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${L}_{aug}^{b}$$\end{document}Laugb and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${L}_{aug}^{u}$$\end{document}Laugu defined in Eqs. (4) and (5), corresponding to directed graphs with bidirectional (panel A) and unidirectional (panel B) adversarial connections, respectively. In each case, a single node (either i, j, or k) is attacked with budget − c < 0. The dashed black lines show the asymptotic relations \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f({L}_{aug}^{b})=-1.1c$$\end{document}f(Laugb)=−1.1c (panel A) and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f({L}_{aug}^{u})=-0.1c$$\end{document}f(Laugu)=−0.1c (panel B). The colored dashed lines in panel (A) correspond to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f({L}_{aug}^{b})=-2c+{L}_{xx}/2$$\end{document}f(Laugb)=−2c+Lxx/2, whereas those in panel (B) correspond to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f({L}_{aug}^{u})=-(\sqrt{2}+1)c/2+{f}_{{{{\rm{inter}}}}}^{x}$$\end{document}f(Laugu)=−(2+1)c/2+finterx, for x = i, j, k, where the intercept is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${f}_{{{{\rm{inter}}}}}^{x}=(3+2\sqrt{2}){L}_{xx}$$\end{document}finterx=(3+22)Lxx. The schematics are not drawn to scale and are intended only to illustrate the qualitative behavior. Schematic dependence of the algebraic connectivity on the attack budget. Panels (A, B) schematically illustrate the algebraic connectivity, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f({L}_{aug}^{b})$$\end{document}f(Laugb) and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f({L}_{aug}^{u})$$\end{document}f(Laugu), of the asymmetric Laplacian matrices \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${L}_{aug}^{b}$$\end{document}Laugb and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${L}_{aug}^{u}$$\end{document}Laugu defined in Eqs. (4) and (5), corresponding to directed graphs with bidirectional (panel A) and unidirectional (panel B) adversarial connections, respectively. In each case, a single node (either i, j, or k) is attacked with budget − c < 0. The dashed black lines show the asymptotic relations \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f({L}_{aug}^{b})=-1.1c$$\end{document}f(Laugb)=−1.1c (panel A) and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f({L}_{aug}^{u})=-0.1c$$\end{document}f(Laugu)=−0.1c (panel B). The colored dashed lines in panel (A) correspond to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f({L}_{aug}^{b})=-2c+{L}_{xx}/2$$\end{document}f(Laugb)=−2c+Lxx/2, whereas those in panel (B) correspond to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f({L}_{aug}^{u})=-(\sqrt{2}+1)c/2+{f}_{{{{\rm{inter}}}}}^{x}$$\end{document}f(Laugu)=−(2+1)c/2+finterx, for x = i, j, k, where the intercept is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${f}_{{{{\rm{inter}}}}}^{x}=(3+2\sqrt{2}){L}_{xx}$$\end{document}finterx=(3+22)Lxx. The schematics are not drawn to scale and are intended only to illustrate the qualitative behavior. General directed graphs The overall behavior of the algebraic connectivity f for a general digraph (i.e., a digraph that is not balanced) subject to an adversarial node addition is more difficult to characterize. In the limit of a large budget c, we derive the same relationships we had previously obtained in the case of balanced digraphs: \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f({L}_{aug}^{b})=-2c+{L}_{ii}/2$$\end{document}f(Laugb)=−2c+Lii/2 in the case of a bidirectional adversarial node addition and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f({L}_{aug}^{u})=-\frac{\sqrt{2}+1}{2}c+(3+2\sqrt{2}){L}_{ii}$$\end{document}f(Laugu)=−2+12c+(3+22)Lii in the case of a unidirectional adversarial node addition, with the only difference that in this case the dependence is on the indegree \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${d}_{i}^{in}={L}_{ii}$$\end{document}diin=Lii of a node, rather than its degree. The above relations indicate that for any directed graph, in the limit of a large budget c, the algebraic connectivity f is defined by the indegree of the targeted node. In general, the curve f(Laug) vs c in the limit of small c, i.e., the initial slope of the curve for small c, depends non-trivially on the choice of the targeted node. However, certain relations can still be derived for the average slope in directed graphs, which is discussed next. We direct our focus to the change in the algebraic connectivity in the limit of small c, 8\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\frac{df}{dc}:={{\lim }_{c\to {0}^{-}}}\frac{\tilde{f}-{f}_{new}}{c}.$$\end{document}dfdc:=limc→0−f~−fnewc. Here, c≥0 is the budget, and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\tilde{f}$$\end{document}f~ is the algebraic connectivity corresponding to the Laplacian matrix Laug before the attack, i.e., to the matrix \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\tilde{L}$$\end{document}L~: 9\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{array}{r}\begin{array}{ll}\tilde{L}=&\left[\begin{array}{cc}L&{{{\boldsymbol{0}}}}\\ {{{{\boldsymbol{0}}}}}^{\top }&0\end{array}\right].\end{array}\end{array}$$\end{document}L~=L00⊤0. We consider the two cases of (i) an attack via bidirectional connection (\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${L}_{aug}^{b}$$\end{document}Laugb in Eq. (4)), and (ii) an attack via unidirectional connection (\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${L}_{aug}^{u}$$\end{document}Laugu in Eq. (5)). We target all nodes of the network one by one and calculate df/dc for each targeted node, i.e., we set bi = − cei where ei has all zero entries except for entry i which is equal to 1. Then, we calculate the average slope < df/dc > : 10\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\left \langle \frac{df}{dc} \right \rangle :=\frac{1}{N}{\sum}_{i=1}^{N}\frac{d{f}_{i}}{dc},$$\end{document}dfdc:=1N∑i=1Ndfidc, where fi is the algebraic connectivity when bi is used in either Eqs. (4) or (5). Next, we investigate the algebraic connectivity for selected real networks, such as animal, biological, social, neural, trade, metabolic, and genetic networks. The network data is obtained from ref. 44. All the adjacency matrices have positive entries, with certain networks being weighted and certain being unweighted (detailed information on these networks can be found in Supplementary Note 4). For each network dataset, we apply our analysis to their largest strongly connected component. We emphasize that the slope dfi/dc is not easy to characterize for non-balanced digraphs since the slope dfi/dc and the indegree of the node i may not have a monotonic relationship. This is shown in Supplementary Note 4 using two examples of animal networks; for one, the slope is directly related to the indegree, while for the other, the slope is not correlated with the indegree. Figure 3 shows the mean slope < df/dc > , averaged over all the network nodes, for a collection of real networks under unidirectional attacks. We see the emergence of a clear scaling relation with the size of the network N, namely < df/dc > = − 1/N. This result is analytically proven in Methods, Proof of mean-slope relation. We conclude that larger networks are less reactive on average to intruder attacks. We have also computed the most negative slope \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\min (df/dc):={{\min }_{i}}d{f}_{i}/dc$$\end{document}min(df/dc):=minidfi/dc and the mean slope < df/dc > under bidirectional and unidirectional attacks, and those plots are provided in Supplementary Note 4.Fig. 3Mean slope 〈df/dc〉 for unidirectional attacks on real-world networks.The mean slope 〈df/dc〉 for unidirectional (Eq. (5)) connections of the adversarial agent for selected real-world networks of size N. The dashed black curve shows the analytically predicted relation 〈df/dc〉 = − 1/N. Mean slope 〈df/dc〉 for unidirectional attacks on real-world networks. The mean slope 〈df/dc〉 for unidirectional (Eq. (5)) connections of the adversarial agent for selected real-world networks of size N. The dashed black curve shows the analytically predicted relation 〈df/dc〉 = − 1/N. Applications Although our results are derived for the case of the consensus dynamics (6), they have direct implications in the case of several real-world applications, described by the general set of equations (1). Below, we discuss three applications of interest in the realm of man-made networks. A detailed asymptotic stability analysis for each application is provided in the Methods. Specifically, the synchronization dynamics is analyzed in Methods, Asymptotic stability analysis for the case of synchronization dynamics, the power grid dynamics in Methods, Asymptotic stability analysis for the case of power grid dynamics, and the formation control dynamics in Methods, Asymptotic Stability Analysis for the Case of Formation Control Dynamics. As a first application, we consider synchronization of coupled chaotic oscillators. A model for the emergence of synchronization in a network of coupled oscillators is the following, 11\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\dot{{{{\boldsymbol{x}}}}}}_{i}(t)={{{\boldsymbol{F}}}}({{{{\boldsymbol{x}}}}}_{i}(t))-\sigma {\sum }_{j=1}^{N}{L}_{ij}{{{\boldsymbol{H}}}}({{{{\boldsymbol{x}}}}}_{j}(t)),$$\end{document}x°i(t)=F(xi(t))−σ∑j=1NLijH(xj(t)), where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{{\boldsymbol{x}}}}}_{i}(t)\in {{\mathbb{R}}}^{m}$$\end{document}xi(t)∈Rm is the state of oscillator i at time t, the functions \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{\boldsymbol{F}}}}:{{\mathbb{R}}}^{m}\to {{\mathbb{R}}}^{m}$$\end{document}F:Rm→Rm and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{\boldsymbol{H}}}}:{{\mathbb{R}}}^{m}\to {{\mathbb{R}}}^{m}$$\end{document}H:Rm→Rm describe the local dynamics and the coupling functions, respectively. The matrix L = [Lij] is the Laplacian matrix that describes the network connectivity, and the scalar σ ≥ 0 is the coupling strength. For this example, we set the local dynamics F to be the chaotic Lorenz oscillator. The functions F and H are 12\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{\boldsymbol{x}}}}=\left[\begin{array}{c}x\\ y\\ z\end{array}\right],\,\,{{{\boldsymbol{F}}}}({{{\boldsymbol{x}}}})=\left[\begin{array}{c}10(y-x)\\ x(28-z)-y\\ xy-\frac{8}{3}z\end{array}\right],\,\,{{{\boldsymbol{H}}}}({{{\boldsymbol{x}}}})=\left[\begin{array}{c}0\\ y\\ 0\end{array}\right].$$\end{document}x=xyz,F(x)=10(y−x)x(28−z)−yxy−83z,H(x)=0y0. We take the directed network shown in Fig. 4A and set σ = 6. Figure 4B shows the synchronous time evolution of the state components xi(t) for each oscillator before the attack. Panel C shows the loss of synchronization observed after the attack. The loss of stability is the direct consequence of having mixed-sign eigenvalues of the Laplacian matrix after the attack. The plots of the y and z components show similar behavior as the x component and can be found in Supplementary Note 5. In Supplementary Note 5 we also provide an explanation for why the synchronous state becomes unstable when an attack occurs in terms of the master stability function approach (MSF)45,46.Fig. 4Effects of intruder attacks in different applications.The top row (A–C) illustrates the application to directly coupled chaotic oscillators, the middle row (D–F) to power grid dynamics described by the nonlinear swing equation, and the bottom row (G–I) to linear single-integrator robot formation control. The left column (A, D, G) shows the corresponding network topologies. Panel A displays a directed network, whereas panels D and G show undirected networks. In all networks, black and orange links denote edge weights of − 1 and 1, respectively. The middle column (B, E, H) shows the dynamics in the absence of the adversarial agent (node A), while the right column (C, F, I) shows the dynamics in its presence. In panel (D), blue square nodes represent generators and orange circular nodes represent load nodes; the adversarial agent is also a load node. Panels (B, C) show the states xi(t) of the Lorenz oscillators; panels E and F show the angular positions ϑi(t) of the generators and loads in the swing equation; and panels H and I show the robot positions in the xy plane, where diamonds denote the initial positions and stars denote the desired final positions. Effects of intruder attacks in different applications. The top row (A–C) illustrates the application to directly coupled chaotic oscillators, the middle row (D–F) to power grid dynamics described by the nonlinear swing equation, and the bottom row (G–I) to linear single-integrator robot formation control. The left column (A, D, G) shows the corresponding network topologies. Panel A displays a directed network, whereas panels D and G show undirected networks. In all networks, black and orange links denote edge weights of − 1 and 1, respectively. The middle column (B, E, H) shows the dynamics in the absence of the adversarial agent (node A), while the right column (C, F, I) shows the dynamics in its presence. In panel (D), blue square nodes represent generators and orange circular nodes represent load nodes; the adversarial agent is also a load node. Panels (B, C) show the states xi(t) of the Lorenz oscillators; panels E and F show the angular positions ϑi(t) of the generators and loads in the swing equation; and panels H and I show the robot positions in the xy plane, where diamonds denote the initial positions and stars denote the desired final positions. Ref. 47 has used the master stability function to study the stability of the synchronous solution in the case of the pinning control problem, for which a reference synchronous trajectory is selected to which all the network nodes need to synchronize. There are, however, two main differences between the two approaches. The first concerns the setting of the problem: in pinning control, one considers the role of a reference agent in driving the synchronization of a network of coupled systems toward the reference trajectory, whereas in our work, we consider the role of an intruder agent in disrupting synchronization. In the former case, the coupling of the reference agent to the rest of the network is cooperative, while in the latter it is adversarial. In particular, the insertion of an intruder effectively alters the coupling structure so that the relevant Laplacian has at least one eigenvalue with a negative real part; as a result, the asymptotic stability analysis naturally involves the evaluation of the Master Stability Function at negative real arguments, corresponding to these eigenvalues, which is not the common approach in the literature. The Methods, Asymptotic stability analysis for the case of synchronization dynamics provide master stability function plots, over both negative and positive values of its argument, for the cases of the Lorenz, Rossler, and Chua oscillators, under various node-to-node couplings. For all the cases considered, we see that the MSF is positive when its argument is negative, implying instability of the synchronous solution. The second difference concerns the observable used to characterize the effect of the intervention: while ref. 47 focuses on asymptotic stability through Lyapunov exponents, here we focus on the transient rate of instability. Next, we study the effect of a unidirectional attack on a scale-free network of Lorenz oscillators coupled in the y-variable, Eq. (12). For this case, the MSF analysis for Eq. (12), presented in the Methods, shows that, for negative values of its argument, the master stability function becomes increasingly negative as the magnitude of the argument increases. We use the algorithm from ref. 48 to randomly generate an undirected and unweighted scale-free graph, which is shown in Fig. 5A. The network has N = 100 nodes and the degree distribution follows a power law PD(k) ∝ k−γ with γ = 2.33, with an average degree of 10. We aim to study the effect of the attack on different nodes; we set σ = 10, c = 1, and vary the node i that is targeted.Fig. 5Effect of the attacked node on network destabilization.Panel (A) shows a randomly generated scale-free network under attack through either of the colored nodes (blue i = 1, orange i = 5, yellow i = 17, purple i = 94, and green i = 100). Panel B considers the dynamics of a network of coupled Lorenz oscillators, Eq. (11), and plots the norm of the transverse perturbations ∥δX(t)∥ as a function of time t for attacks targeting different nodes i. Each curve corresponds to a different attacked node, all with the same attack budget c = 1. The dashed black line indicates the onset of the attack at t = 4 s. The initial conditions of the oscillators are identical in all simulations, so that the observed differences are solely due to the attacked node. The degree of each attacked node, di, is also indicated in the plot. Effect of the attacked node on network destabilization. Panel (A) shows a randomly generated scale-free network under attack through either of the colored nodes (blue i = 1, orange i = 5, yellow i = 17, purple i = 94, and green i = 100). Panel B considers the dynamics of a network of coupled Lorenz oscillators, Eq. (11), and plots the norm of the transverse perturbations ∥δX(t)∥ as a function of time t for attacks targeting different nodes i. Each curve corresponds to a different attacked node, all with the same attack budget c = 1. The dashed black line indicates the onset of the attack at t = 4 s. The initial conditions of the oscillators are identical in all simulations, so that the observed differences are solely due to the attacked node. The degree of each attacked node, di, is also indicated in the plot. We select the nodes i = 1, 5, 17, 94, 100 with degrees 82, 47, 23, 13, and 8, respectively, and associate to these nodes the colors blue, orange, yellow, purple, and green, respectively. For more details on this example, see Supplementary Note 6. The perturbation vector for each node is calculated as \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\delta {{{{\boldsymbol{x}}}}}_{i}(t)={{{{\boldsymbol{x}}}}}_{i}(t)-\frac{1}{N}{\sum }_{j=1}^{N}{{{{\boldsymbol{x}}}}}_{j}\in {{\mathbb{R}}}^{3}$$\end{document}δxi(t)=xi(t)−1N∑j=1Nxj∈R3. We then form the transverse perturbations vector \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\delta {{{\boldsymbol{X}}}}(t)={[\delta {{{{\boldsymbol{x}}}}}_{1}{(t)}^{\top },\delta {{{{\boldsymbol{x}}}}}_{2}{(t)}^{\top },\ldots,\delta {{{{\boldsymbol{x}}}}}_{N}{(t)}^{\top }]}^{\top }\in {{\mathbb{R}}}^{3N}$$\end{document}δX(t)=[δx1(t)⊤,δx2(t)⊤,…,δxN(t)⊤]⊤∈R3N and calculate its norm: 13\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\parallel \delta {{{\boldsymbol{X}}}}(t)\parallel :=\sqrt{\delta {{{\boldsymbol{X}}}}{(t)}^{\top }\delta {{{\boldsymbol{X}}}}(t)}.$$\end{document}∥δX(t)∥:=δX(t)⊤δX(t). If the oscillators synchronize, then ∥δX(t)∥ → 0, otherwise ∥δX(t)∥ does not decay. We see from Fig. 5 B that before the attack, i.e., on the left side of the dashed black line, the norm of the transverse perturbations approaches zero, indicating that the Lorenz oscillators have synchronized. However, after attacking either one of the nodes 1, 5, 17, 94, 100, we see an immediate loss of synchronization, with a faster rate of transient instability when the nodes with lower degrees are targeted. For example, the attack on node 100 with degree 8 (the green curve) results in much larger ∥δX(t)∥ than the attack on node 1 with degree 82 (the blue curve). To conclude, this example shows that in a nonlinear networked system, lower indegree nodes are more vulnerable to intruder attacks. Note that this is consistent with the MSF analysis for the case of Eq. (12), presented in Methods, Asymptotic stability analysis for the case of synchronization dynamics, since attacking nodes with lower indegrees corresponds to evaluating the master stability function at more negative values of its argument, for which the associated maximum Lyapunov exponent is larger. As a second application, we consider power grid dynamics. The swing equation is a classical model for the dynamics of a power grid,49,5014\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\ddot{\vartheta }}_{i}(t)={p}_{i}-\gamma {\dot{\vartheta }}_{i}(t)-{\sum }_{j=1,j\ne i}^{N}{A}_{ij}\sin ({\vartheta }_{i}(t)-{\vartheta }_{j}(t))$$\end{document}ϑ¨i(t)=pi−γϑ°i(t)−∑j=1,j≠iNAijsin(ϑi(t)−ϑj(t)) where ϑi(t) is the angular displacement of node/rotor i, the scalar pi denotes the power consumption (pi < 0 for loads) or power generation (pi > 0 for generators,) the scalar γ > 0 denotes the damping ratio, and the symmetric adjacency matrix A = [Aij] describes the connectivity of the grid, i.e., Aij = Aji = 1 (0) if there is (is not) a transmission line between nodes i and j. Note that although Eq. (14) is not a particular case of Eq. (1), the linearized swing equation (see Supplementary Note 7) on which our analysis is based is. We also emphasize here that the swing equation (14) conveniently demonstrates how an intruder oscillator can be mathematically incorporated into the Laplacian matrix through a negative sign. By constraining the intruder oscillator to remain in anti-phase with the rest of the network—i.e., \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\sin ({\vartheta }_{i}(t)-{\vartheta }_{j}(t)\pm \pi )=-\sin ({\vartheta }_{i}(t)-{\vartheta }_{j}(t))$$\end{document}sin(ϑi(t)−ϑj(t)±π)=−sin(ϑi(t)−ϑj(t))—a negative sign naturally emerges in the coupling kernel. This negative sign is then absorbed into the adjacency matrix as a negative link connection, represented by − Aij. To illustrate the effect of the addition of an adversarial agent, we provide a numerical example. Here, we set γ = 0.9, and the network shown in Fig. 4D shows the grid topology before and after the addition of the adversarial agent. Nodes 1, 2, 3 and 4 are loads, nodes 5, 6 and 7 are generators, and the adversarial node is denoted as node A with a black connection with weight − 1. The vector p = [− 0.3, − 0.3, − 0.3, −0.3, 0.4, 0.4, 0.4]⊤ describes the power generated/consumed in the original power grid. Without loss of generality, for the adversarial agent, we set pA = − 0.1, so the adversarial agent acts as a load. As seen in Fig. 4E (Fig. 4F), the dynamics of the power grid converge (does not converge) to a fixed point before (after) the attack. In Supplementary Note 7, we show analytically how the addition of the adversarial agent results in at least one unstable mode of the linearized swing equation, which in turn destabilizes the nonlinear dynamics. As a third application, we consider distributed formation control. The formation control of robots is used in both civilian and military applications, see refs. 51–53. Here, we focus on positioning a set of robots on a given desired pattern, e.g., the robots are positioned around a circle with a known diameter. We take the shape-based formation control strategy from ref. 54: 15\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\dot{{{{\boldsymbol{X}}}}}(t)=(-F(L)\otimes {I}_{2})({{{\boldsymbol{X}}}}(t)-{{{\boldsymbol{\beta}}}}),$$\end{document}X°(t)=(−F(L)⊗I2)(X(t)−β),where the state vector \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{\boldsymbol{X}}}}(t)=[{x}_{1}(t),{y}_{1}(t),{x}_{2}(t),{y}_{2}(t),\ldots,{x}_{N}(t),{y}_{N}(t)]^{\top }\in {{\mathbb{R}}}^{2N}$$\end{document}X(t)=[x1(t),y1(t),x2(t),y2(t),…,xN(t),yN(t)]⊤∈R2N is the concatenation of the xy coordinates of N robots at time t. The matrix L is the symmetric Laplacian matrix that describes the connectivity between the robots, the function \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F(L):{{\mathbb{R}}}^{N\times N}\to {{\mathbb{R}}}^{N\times N}$$\end{document}F(L):RN×N→RN×N is a function of the Laplacian matrix L. The network topology for this example with N = 5 is shown in Fig. 4G. We set \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F(L)={I}_{N}-\exp (-3L)$$\end{document}F(L)=IN−exp(−3L) as in ref. 54. The vector \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{\boldsymbol{\beta}}}}\in {{\mathbb{R}}}^{2n}$$\end{document}β∈R2n is a constant vector of target positions, which we position around a circle with radius 1 in equidistant phases, i.e., \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{\boldsymbol{\beta}}}}={[\sin (0),\cos (0),\sin (\frac{2\pi }{5}),\cos (\frac{2\pi }{5}),\ldots,\sin (\frac{8\pi }{5}),\cos (\frac{8\pi }{5})]}^{\top }$$\end{document}β=[sin(0),cos(0),sin(2π5),cos(2π5),…,sin(8π5),cos(8π5)]⊤. For the adversarial agent, we set its corresponding \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{\boldsymbol{\beta}}}}_{j}$$\end{document}βj to the origin [0, 0]⊤. Figure 4 H shows the formation control in the absence of the adversarial agent, where each robot converges to its respective target position in less than 20 s. Note that this can be seen as a case of cluster synchronization, since different agents converge to different states. However, Fig. 4 I shows that in the presence of the adversarial agent, the robots no longer reach the target positions and the closed-loop system becomes unstable, the position and velocity of the robots tend to infinity. Phase synchronization based on Kuramoto dynamics Here we consider the case of phase synchronization in a network of coupled Kuramoto oscillators25, 16\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\dot{\theta }}_{i}(t)={\omega }_{i}+\frac{1}{N+1}\mathop{\sum }_{j=1}^{N+1}{A}_{ij}(t)\sin ({\theta }_{j}(t)-{\theta }_{i}(t)),$$\end{document}θ°i(t)=ωi+1N+1∑j=1N+1Aij(t)sin(θj(t)−θi(t)),i = 1, …, N + 1, where the scalar θi(t) is the phase angle of oscillator i at time t, the scalar ωi is the frequency of oscillator i. We require different frequencies for different oscillators, i.e., ωi ≠ ωj, ∀ i ≠ j. The time-varying connectivity is described by the adjacency matrix A(t) = [Aij(t)] where if node i receives a connection from node j at time t, then Aij(t) ≠ 0, otherwise Aij(t) = 0. We assume that a unidirectional adversarial connection from the intruder to one of the network nodes is established at some time T > 0. More precisely, the time-varying adjacency matrix is given by, 17\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$A(t)=\left\{\begin{array}{ll}\left[\begin{array}{cc}{A}_{0}&{{{\boldsymbol{0}}}}\\ {{{{\boldsymbol{0}}}}}^{\top }&0\end{array}\right],\quad &t < T,\\ \\ \left[\begin{array}{cc}{A}_{0}&{{{{\boldsymbol{b}}}}}^{i}\\ {{{{\boldsymbol{0}}}}}^{\top }&0\end{array}\right],\quad &t\ge T.\end{array}\right.$$\end{document}A(t)=A000⊤0,t 0.1{L}_{ii}^{2}$$\end{document}c>0.1Lii2 (dependent on the attacked node),where Lii is the indegree of the attacked node. The details of our analysis are available in Supplementary Note 8.Fig. 7Effect of the attacked node on destabilization of Kuramoto dynamics.Panel (A) shows a randomly generated scale-free network under attack through either one of the colored nodes with different indegrees (blue i = 1 with degree 82, orange i = 5 with degree 47, yellow i = 17 with degree 23, purple i = 94 with degree 13, and green i = 100 with degree 8). In panel (B), we integrate the Kuramoto dynamics of Eq. (17) on this network, and plot the norm of the phase perturbations vector ∥δθ(t)∥ as a function of time t and for different choices of the attacked node i. In panel (C), we plot the order parameter ρ(t), Eq. (19), as a function of time t and for different choices of the attacked node i. Different curves correspond to different attacked nodes, all with the same budget c = 1. The dashed black line denotes the start time of the attack. The initial conditions of the oscillators are chosen randomly from the uniform distribution [0, 0.1]. The plot also provides the degree of node i as degi. The highlighted background denotes the standard deviation over 20 realizations. The natural frequencies of the oscillators are randomly drawn from a Normal distribution with a mean of 0.1 and a standard deviation of 0.001. The small budget should be c < 10−2 (independent of the attacked node), The small budget should be c < 10−2 (independent of the attacked node), the large budget should be \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$c > 0.1{L}_{ii}^{2}$$\end{document}c>0.1Lii2 (dependent on the attacked node), the large budget should be \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$c > 0.1{L}_{ii}^{2}$$\end{document}c>0.1Lii2 (dependent on the attacked node), Effect of the attacked node on destabilization of Kuramoto dynamics. Panel (A) shows a randomly generated scale-free network under attack through either one of the colored nodes with different indegrees (blue i = 1 with degree 82, orange i = 5 with degree 47, yellow i = 17 with degree 23, purple i = 94 with degree 13, and green i = 100 with degree 8). In panel (B), we integrate the Kuramoto dynamics of Eq. (17) on this network, and plot the norm of the phase perturbations vector ∥δθ(t)∥ as a function of time t and for different choices of the attacked node i. In panel (C), we plot the order parameter ρ(t), Eq. (19), as a function of time t and for different choices of the attacked node i. Different curves correspond to different attacked nodes, all with the same budget c = 1. The dashed black line denotes the start time of the attack. The initial conditions of the oscillators are chosen randomly from the uniform distribution [0, 0.1]. The plot also provides the degree of node i as degi. The highlighted background denotes the standard deviation over 20 realizations. The natural frequencies of the oscillators are randomly drawn from a Normal distribution with a mean of 0.1 and a standard deviation of 0.001. In Supplementary Note 9, we compare the effects of an intruder attack on two leaf nodes (nodes with degree 1): one connected to the hub node (the node with the highest degree) and one not connected to the hub. By examining the dynamics immediately after the attack, we do not observe any difference between the two cases in their transient response. Discussion This work identifies a fundamental vulnerability of complex dynamical networks: a single node connected through adversarial links to one or more other nodes is sufficient to destabilize the network dynamics, regardless of the network size. Such an attack provides a generic mechanism for disrupting consensus in opinion dynamics, synchronization in oscillator networks, and desired formations in coupled autonomous systems. Furthermore, we find that targeting a node with the smallest indegree, defined as the sum of the weights of all incoming connections, typically destabilizes the network in the shortest time. In contrast, attacking hub nodes generally results in a slower onset of instability. Intuitively, this can be explained as follows: hubs respond less to the coupling with the intruder due to a large number of in-neighbors, while low-indegree nodes respond more. The practical implementation of negative (adversarial) interactions depends on the application domain, but is in general, well-grounded across a wide range of systems. In technological and engineering networks, the distinction between cooperative and adversarial interactions often reduces to the sign of a feedback gain. In standard Laplacian coupling, the interaction acting on node i takes the form g(xref − xi), where xref is a reference state, xi is the state of node i, and g is a scalar gain. Cooperative interactions correspond to g > 0, whereas adversarial interactions correspond to g < 0. Thus, changing the sign of the feedback gain naturally switches between the two regimes. In practice, such sign changes may arise from faulty or malicious agents, incorrect controller design, or cyber-attacks that invert transmitted signals. In power grid applications, for example, adversarial coupling can be realized through devices enforcing anti-phase behavior, as discussed in Subsection Applications. In biological systems, negative interactions are ubiquitous and arise intrinsically. Examples include inhibitory synaptic coupling in neuronal networks, competitive interactions in ecological systems, and repression mechanisms in gene regulatory networks. In these settings, adversarial interactions are not externally imposed but are a fundamental component of the system dynamics. Within this perspective, our framework captures the effect of introducing or amplifying inhibitory interactions in otherwise cooperative networks. In social systems, negative coupling emerges through antagonistic or contrarian behavior. For instance, in opinion dynamics models, some individuals may systematically oppose the state of their neighbors (so-called “contrarians”), effectively inducing negative interactions. Likewise, misinformation or adversarial agents in online networks can disrupt consensus by promoting opposing views. These mechanisms provide realistic pathways through which adversarial interactions can arise and influence collective dynamics. Our results are in stark contrast to the expectation that hubs are the most critical nodes of a network4, and thus the ones that need to be more closely protected from attacks. This assumes particular relevance in the case of scale-free networks55. A central dogma in the field of complex networks is that scale-free networks are stable against random failures (removal) of nodes but are vulnerable, in terms of structural integrity (i.e., the size of the strongly connected component) to attacks targeting the hubs. We show a significantly different picture for the case of dynamical attacks considered here: while the structure of scale-free networks is more vulnerable to attacks targeting the hubs4, their dynamics is more vulnerable to attacks targeting nodes with low indegree. In summary, while hubs exhibit high vulnerability in terms of structural integrity, they are somewhat protected in dynamical contexts, leading to a situation where low-degree nodes are most vulnerable. Ref. 56 had also shown that the structural controllability of a network was enhanced when driver nodes are not connected to high-degree nodes. Ref. 57 had found that the structural controllability of a network depends strongly on the fraction of low in-degree and low out-degree nodes. However, destabilizing the network dynamics does not require controllability, and here we provide simple sufficient conditions to induce instability of this dynamics. Our work complements a large literature on the importance of low-degree nodes and weak ties58; the relevance of low-degree nodes, under specific circumstances, is also acknowledged in the literature on percolation dynamics on networks4 and the importance of weak ties on stability for predator-prey networks has been pointed out in ref. 59. Our work complements the large literature that focuses on conditions to ensure the stability of the network dynamics, see e.g., ref. 60, while we focus on instability and on characterizing the severity of such instability. We investigate the fundamental question of how desired dynamical states can be disrupted by the purposeful insertion of one or a few intruder agents. Our intruders are structurally similar to the other network agents, which is consistent with the case of cyber-attacks. Our results are initially derived for the case of the linear consensus problem but have implications in a broad variety of network dynamics, including opinion dynamics, synchronization, formation control, and power grid balancing. We also study the case of the Kuramoto model, which is relevant to synchronization of biological systems. That having been said, we do not claim that our results apply to all the possible realizations of Eq. (1), but to a variety of cases of interest. Our work on intruder attacks in networked systems intersects with the domain of network interdiction, which has been extensively studied in operations research and optimization contexts. Smith and Song’s comprehensive survey on network interdiction61 provides a systematic overview of how adversaries can strategically disrupt network operations by targeting critical components. While traditional network interdiction focuses primarily on structural disruptions such as removing nodes or edges to maximize the disruption of flow, connectivity, or shortest paths62,63, our approach examines dynamical disruptions through adversarial connections that destabilize the network’s equilibrium states. This distinction is crucial: classical interdiction models often assume a static network structure where the adversary’s goal is to disconnect components or increase path lengths61,64, whereas our framework considers how a single intruder node can exploit the network’s dynamical properties to induce instability while leaving the structural connectivity intact. Our results complement the interdiction literature by demonstrating that in cyber-physical systems, power grids, and consensus networks, dynamical vulnerability differs fundamentally from structural vulnerability: targeting low-indegree nodes rather than high-degree hubs identified as critical in classical interdiction models65 produces the most severe instabilities. This finding suggests that protection strategies derived from structural interdiction theory may be insufficient for dynamical networks, necessitating new defense mechanisms that account for both topological and dynamical characteristics. We show the emergence of universal scaling properties, with small perturbations causing uniform responses and larger ones exposing specific vulnerabilities, especially at the low-indegree nodes. When applied to real complex networks, we see that it may not always be easy to characterize the rate of instability produced by the attack in the general case of non-balanced digraphs. However, our theory (see also Fig. 3) shows that the rate of instability generated by an attack on a single node averaged over all N networks nodes scales exactly as − N−1, for the case that the adversarial connection is unidirectional. This indicates that larger networks are more robust, on average, against intruder attacks. Although our work focuses on the case that an intruder node is added to an existing network, it can be generalized to the case that an existing network node becomes an intruder. In that case, the strategy that maximizes the effects of an attack is for the intruder to target only one node with the lowest indegree, where the indegree is computed by counting all the nodes in the network, except for the intruder. An obvious countermeasure against intruder attacks is to disconnect the attacker(s) from the network. This is consistent, for example, with the load shedding strategy, commonly implemented for power grids in the case of a power imbalance. In general, shedding the part of the network that includes the intruder provides a viable solution against intruder attacks, which is easier to do when the attacker is connected to the rest of the network by a single link compared to the case of multiple links. This observation highlights a trade-off between the severity of an attack and the recoverability from such an attack. Extending the present framework to higher-order (many-body) interactions represents a natural and promising direction for future work. Recent studies have shown that such interactions can significantly modify synchronization properties, leading to global topological synchronization in some cases, but also to multistability and abrupt desynchronization in others66–69. This indicates that, depending on their structure, higher-order interactions may either promote coherence or give rise to additional instability mechanisms. In this context, we expect them to shift stability thresholds and modulate the system’s sensitivity to perturbations, without altering the underlying mechanism. Finally, a word of caution. While our results are rigorous for the case of linear dynamics (e.g., consensus), they are mostly based on extensive numerical calculations in the case of nonlinear dynamics. We believe more work is needed to fully characterize the effects of intruder attacks in nonlinear networks, although our work provides a strong indication that in many cases of interest, the rate of instability observed for linear networks is inherited by their nonlinear counterparts. Methods Transverse reactivity of stable and unstable consensus dynamics The first part of this subsection discusses general linear dynamical systems. The second part of this subsection focuses on linear consensus dynamics as a special case of general linear dynamical systems. Consider a linear dynamical system 21\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\dot{{{{\boldsymbol{x}}}}}(t)=M{{{\boldsymbol{x}}}}(t)$$\end{document}x°(t)=Mx(t) where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{\boldsymbol{x}}}}(t)\in {{\mathbb{R}}}^{N}$$\end{document}x(t)∈RN is the vector of system states and the square matrix \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$M\in {{\mathbb{R}}}^{N\times N}$$\end{document}M∈RN×N. Definition 6 Spectral abscissa of a matrix. Given a square matrix M ∈ RN×N, we define the spectral abscissa as the greatest real part of the matrix spectrum, 22\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\alpha (M)={{\max }_{i}}\Re ({\lambda }_{i}),$$\end{document}α(M)=maxiℜ(λi), where λ1, λ2, . . . , λN are the possibly complex eigenvalue of the matrix M and ℜ(⋅) returns the real part of its argument. The origin is a stable fixed point for the system in Eq. (21) if and only if α(M) < 0. Definition 7 Reactivity of a linear dynamical system70. The reactivity for the system in Eq. (21) is defined as, 23\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{array}{rcl}\xi \left(M\right)&:=&{\mathop{\max }_{\parallel {{{\boldsymbol{X}}}}\parallel \ne 0}}\left[\frac{1}{\parallel {{{\boldsymbol{X}}}}\parallel }\frac{d\parallel {{{\boldsymbol{X}}}}\parallel }{dt}\right]\\ &=&{{\max }_{{{{\boldsymbol{X}}}}\ne 0}}\frac{{{{{\boldsymbol{X}}}}}^{\top }\left(\frac{M+{M}^{\top }}{2}\right){{{\boldsymbol{X}}}}}{{{{{\boldsymbol{X}}}}}^{\top }{{{\boldsymbol{X}}}}}\\ &=&{\lambda }_{\max }\left(\frac{M+{M}^{\top }}{2}\right)=:{\lambda }_{\max }(S),\end{array}$$\end{document}ξM:=max∥X∥≠01∥X∥d∥X∥dt=maxX≠0X⊤M+M⊤2XX⊤X=λmaxM+M⊤2=:λmax(S), where the matrix S = (M + M⊤)/2 is the symmetric part of the matrix M and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\lambda }_{\max }(\cdot )$$\end{document}λmax(⋅) indicates the largest eigenvalue of the symmetric matrix in its argument. The reactivity measures the maximal rate of instantaneous growth/decay of the norm of the state vector. If \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\xi \left(M\right) < 0$$\end{document}ξM<0 (\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\xi \left(M\right) > 0$$\end{document}ξM>0), the norm of the state vector will decay (may grow) instantaneously. The choice of X that maximizes (23) is the eigenvector v1 of the matrix S associated with the eigenvalue \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\lambda }_{\max }(S)$$\end{document}λmax(S). Note that the reactivity is computed by maximizing over X, thus it provides a worst-case instantaneous rate of growth for ∥X∥. In the case that X is generically chosen, it will have a non-zero component along the eigenvector v1, thus the worst-case rate of growth for ∥X∥ will be observed with probability 1. Theorem 8 The reactivity of the dynamics (21) is greater than or equal to the spectral abscissa of the matrix M, i.e., ξ(M) ≥ α(M). Proof We set S = (M + M⊤)/2 and write the reactivity of the dynamics (21), 24\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\xi (M)= {{\max }_{{{{\boldsymbol{Z}}}}\ne 0}}\frac{{{{{\boldsymbol{Z}}}}}^{\top }S{{{\boldsymbol{C}}}}}{{{{{\boldsymbol{Z}}}}}^{\top }{{{\boldsymbol{Z}}}}}\ge {{{{{\boldsymbol{v}}}}}_{1}}^{\top }S{{{{\boldsymbol{v}}}}}_{1}\\= {{{{{\boldsymbol{v}}}}}_{1}}^{\top }\left(\frac{M+{M}^{\top }}{2}\right){{{{\boldsymbol{v}}}}}_{1}\\= \frac{1}{2}({{{{\boldsymbol{v}}}}}_{1}^{\top }M{{{{\boldsymbol{v}}}}}_{1}+{{{{\boldsymbol{v}}}}}_{1}^{\top }{M}^{\top }{{{{\boldsymbol{v}}}}}_{1})\\= \frac{1}{2}({{{{\boldsymbol{v}}}}}_{1}^{\top }\alpha (M){{{{\boldsymbol{v}}}}}_{1}+\alpha (M){{{{\boldsymbol{v}}}}}_{1}^{\top }{{{{\boldsymbol{v}}}}}_{1})\\= \alpha (M)$$\end{document}ξ(M)=maxZ≠0Z⊤SCZ⊤Z≥v1⊤Sv1=v1⊤M+M⊤2v1=12(v1⊤Mv1+v1⊤M⊤v1)=12(v1⊤α(M)v1+α(M)v1⊤v1)=α(M) This concludes the proof. □ Theorem 8 is important as it states that the instantaneous rate of growth of the state Z in (21) can be either larger than or equal to the asymptotic rate of growth of Z. This is true in both the cases of asymptotically stable and unstable dynamics. If α(M) > 0, we then see that ξ(M) ≥ α(M) > 0. This indicates that for an unstable system, the rate of instantaneous growth is positive and exceeds or is equal to the rate of asymptotic growth. It is inferred that the inequality in (24) is satisfied with the equal sign when the left and right eigenvectors of the matrix M associated with the eigenvalue λ1 coincide. This means that Z* = v1 becomes the maximizer in (24). The discussion that follows is for the single-integrator consensus dynamics in Eq. (6), \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\dot{{{{\boldsymbol{X}}}}}(t)=-L{{{\boldsymbol{X}}}}(t)$$\end{document}X°(t)=−LX(t), which is a special case of the general linear dynamical system in Eq. (21). We write the eigenvalue equation Lvi = λivi, where λi (vi) are the possibly complex eigenvalues (eigenvectors) of the Laplacian matrix L, i = 1, . . . , N. By the property that the rows of the Laplacian all sum to zero, there exists one eigenvalue of the Laplacian equal to zero, with the corresponding eigenvector having entries that are all the same. We index this eigenvalue j. Without loss of generality, we set ℜ(λ1(L)) ≤ ℜ(λ2(L)) ≤ . . . ≤ℜ(λN(L)), where ℜ(⋅) returns the real part of its argument. When the Laplacian matrix is proper, j = 1 and ℜ(λ1(L)) = 0, which results in an asymptotically stable consensus dynamics Eq. (6). Here, we remove the assumption that the Laplacian is proper and present a general theory of transient and asymptotic stability for Eq. (6). Any point such that 25\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${x}_{1}={x}_{2}=...={x}_{N}$$\end{document}x1=x2=...=xN is an equilibrium for the dynamics (6). The set of points that satisfy (25) defines the consensus manifold. We are interested in whether the consensus manifold is asymptotically stable or unstable and in characterizing the maximum rate of transient instability away from this manifold. Thus in what follows, we focus on the transverse consensus dynamics, 26\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\dot{{{{\boldsymbol{Z}}}}}(t)=-A{{{\boldsymbol{Z}}}}(t)$$\end{document}Z°(t)=−AZ(t)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{\boldsymbol{Z}}}}\in {{\mathbb{R}}}^{N-1}={V}^{\top }{{{\boldsymbol{X}}}}$$\end{document}Z∈RN−1=V⊤X, the matrix \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$A\in {{\mathbb{R}}}^{N-1\times N-1}={V}^{\top }LV$$\end{document}A∈RN−1×N−1=V⊤LV and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$V\in {{\mathbb{R}}}^{N\times N-1}$$\end{document}V∈RN×N−1 is an orthonormal basis for the null subspace of 1⊤, i.e., V is a matrix whose columns are normal and orthogonal to one another and have zero column sums. Remark 3 The matrix A has the same spectrum as the Laplacian matrix L, except for one eigenvalue of the matrix L which is equal zero, i.e., \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{\mathcal{S}}}}(L)={{{\mathcal{S}}}}(A)\cup \{0\}$$\end{document}S(L)=S(A)∪{0} where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{\mathcal{S}}}}(\cdot )$$\end{document}S(⋅) returns the spectrum of the matrix in its argument. In our previous work71, we studied the entire consensus dynamics Eq. (6) under the assumption the consensus dynamics was stable, i.e., α(− A) < 0. In this case, the trajectories of the system states eventually approach the origin (asymptotic stability), while the magnitude of the states may grow at transient times due to positive reactivity, which is not desirable in various situations, such as linearized dynamics about a fixed point. This transient growth may result in the invalidity of the linearization assumption. Unlike previous work by us and others27,29,32,70–78, here we are mostly concerned with the reactivity of the transverse dynamics, i.e., Eq. (26) in the case that α(− A) > 0, i.e., the system Eq. (6) is asymptotically unstable. Next, we comment on the relevance of both the spectral abscissa and the reactivity on the transverse consensus dynamics (26). The asymptotic rate of Z(t) in (26) is given by α(− A), i.e., the spectral abscissa of − A. In general, α(− A) can be either positive or negative. On the other hand, the instantaneous rate of growth of the norm of the vector Z is given by the reactivity, 27\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{array}{r}\begin{array}{ll}\xi \left(-A\right)&={{\max }_{\parallel {{{\boldsymbol{Z}}}}\parallel \ne 0}}\left[\frac{1}{\parallel {{{\boldsymbol{Z}}}}\parallel }\frac{d\parallel {{{\boldsymbol{Z}}}}\parallel }{dt}\right]={\lambda }_{\max }\left(-\frac{A+{A}^{\top }}{2}\right).\end{array}\end{array}$$\end{document}ξ−A=max∥Z∥≠01∥Z∥d∥Z∥dt=λmax−A+A⊤2. Thus, a positive (negative) reactivity ξ(− A) indicates that the norm of the state Z tends to grow (shrink) in the limit of t → 0. Proposition 9 The algebraic connectivity of the graph represented by the Laplacian matrix in Eq. (6) is equal to the negative of the reactivity of the transverse dynamics in Eq. (26), that is, f(L) ≡ − ξ(− A). Proof The reactivity of the dynamics in Eq. (27) is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\xi \left(-A\right):= {{\max }_{\parallel {{{\boldsymbol{Z}}}}\parallel \ne 0}}\left[\frac{1}{\parallel {{{\boldsymbol{Z}}}}\parallel }\frac{d\parallel {{{\boldsymbol{Z}}}}\parallel }{dt}\right]\\= {{\max }_{\parallel {{{\boldsymbol{Z}}}}\parallel \ne 0}}\left[\frac{1}{\sqrt{{{{{\boldsymbol{Z}}}}}^{\top }{{{\boldsymbol{Z}}}}}}\frac{d\sqrt{{{{{\boldsymbol{Z}}}}}^{\top }{{{\boldsymbol{Z}}}}}}{dt}\right]\\= {{\max }_{\parallel {{{\boldsymbol{Z}}}}\parallel \ne 0}}\left[\frac{1}{\sqrt{{{{{\boldsymbol{Z}}}}}^{\top }{{{\boldsymbol{Z}}}}}}\frac{{\dot{{{{\boldsymbol{Z}}}}}}^{\top }{{{\boldsymbol{Z}}}}+{{{{\boldsymbol{Z}}}}}^{\top }\dot{{{{\boldsymbol{Z}}}}}}{2\sqrt{{{{{\boldsymbol{Z}}}}}^{\top }{{{\boldsymbol{Z}}}}}}\right]\\= {{\max }_{\parallel {{{\boldsymbol{Z}}}}\parallel \ne 0}}\left[\frac{{{{{\boldsymbol{Z}}}}}^{\top }(-A-{A}^{\top }){{{\boldsymbol{Z}}}}}{2{{{{\boldsymbol{Z}}}}}^{\top }{{{\boldsymbol{Z}}}}}\right].$$\end{document}ξ−A:=max∥Z∥≠01∥Z∥d∥Z∥dt=max∥Z∥≠01Z⊤ZdZ⊤Zdt=max∥Z∥≠01Z⊤ZZ°⊤Z+Z⊤Z°2Z⊤Z=max∥Z∥≠0Z⊤(−A−A⊤)Z2Z⊤Z. Also, V⊤V = I, L = VAV⊤ and X = VZ which indicates X⊥1 since X ∈ range(V), so \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\xi \left(-A\right)= {{\max }_{\parallel {{{\boldsymbol{Z}}}}\parallel \ne 0}}\left[\frac{{{{{\boldsymbol{Z}}}}}^{\top }\left(-({V}^{\top }V)A({V}^{\top }V)-({V}^{\top }V){A}^{\top }({V}^{\top }V)\right){{{\boldsymbol{Z}}}}}{2{{{{\boldsymbol{Z}}}}}^{\top }{{{\boldsymbol{Z}}}}}\right]\\= {{\max }_{\parallel {{{\boldsymbol{Z}}}}\parallel \ne 0}}\left[\frac{({{{{\boldsymbol{Z}}}}}^{\top }{V}^{\top })(-L-{L}^{\top })(V{{{\boldsymbol{Z}}}})}{2({{{{\boldsymbol{Z}}}}}^{\top }{V}^{\top })(V{{{\boldsymbol{Z}}}})}\right]\\= {{\max }_{{{{\boldsymbol{X}}}}\ne 0,{{{\boldsymbol{X}}}}\perp {{{\bf{1}}}}}}\left[\frac{{{{{\boldsymbol{X}}}}}^{\top }(-L-{L}^{\top }){{{\boldsymbol{X}}}}}{2{{{{\boldsymbol{X}}}}}^{\top }{{{\boldsymbol{X}}}}}\right]\\= -{{\min }_{{{{\boldsymbol{X}}}}\ne 0,{{{\boldsymbol{X}}}}\perp {{{\bf{1}}}}}}\left[\frac{{{{{\boldsymbol{X}}}}}^{\top }(L+{L}^{\top }){{{\boldsymbol{X}}}}}{2{{{{\boldsymbol{X}}}}}^{\top }{{{\boldsymbol{X}}}}}\right]\\= -{{\min }_{{{{\boldsymbol{X}}}}\ne 0,{{{\boldsymbol{X}}}}\perp {{{\bf{1}}}}}}\left[\frac{{{{{\boldsymbol{X}}}}}^{\top }L{{{\boldsymbol{X}}}}}{{{{{\boldsymbol{X}}}}}^{\top }{{{\boldsymbol{X}}}}}\right]\\= -f(L).$$\end{document}ξ−A=max∥Z∥≠0Z⊤−(V⊤V)A(V⊤V)−(V⊤V)A⊤(V⊤V)Z2Z⊤Z=max∥Z∥≠0(Z⊤V⊤)(−L−L⊤)(VZ)2(Z⊤V⊤)(VZ)=maxX≠0,X⊥1X⊤(−L−L⊤)X2X⊤X=−minX≠0,X⊥1X⊤(L+L⊤)X2X⊤X=−minX≠0,X⊥1X⊤LXX⊤X=−f(L). That concludes the proof. □ In what follows, we refer to ξ(− A) in Eq. (27) as either the reactivity of the dynamics in Eq. (26) or the transverse reactivity of the consensus dynamics in Eq. (6), interchangeably. The instantaneous rate of growth of the transverse consensus dynamics in Eq. (26) is greater or equal to the asymptotic rate of growth, i.e., ξ(− A)≥α(− A). Proof The relation ξ(− A)≥α(− A) is obtained by placing M = − A in Theorem 8. □ To illustrate the relation ξ(− A) ≥ α(− A), we provide a numerical example of stable and unstable dynamics. First, we randomly generate the proper Laplacian matrix 28\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$L=\left[\begin{array}{ccccc}1&-1&0&0&0\\ 0&1&0&0&-1\\ -1&-1&2&0&0\\ 0&0&0&0&0\\ 0&0&0&-1&1\end{array}\right]$$\end{document}L=1−10000100−1−1−120000000000−11 with all eigenvalues with non-negative real-part and only one zero eigenvalue. The matrix A in Eq. (26) corresponding to the Laplacian matrix L in (28) is 29\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$A=\left[\begin{array}{cccc}1.5427&-0.1809&0.2337&-0.9045\\ -0.1483&2.1281&0.5427&0.4045\\ 0.5427&-0.1809&0.2337&0.0955\\ 0.5427&-0.1809&-0.7663&1.0955\end{array}\right].$$\end{document}A=1.5427−0.18090.2337−0.9045−0.14832.12810.54270.40450.5427−0.18090.23370.09550.5427−0.1809−0.76631.0955. Here, ξ(− A) = − 0.0250≥α(− A) = − 1. We simulate Eq. (26) from the initial condition Z(0) = [ − 0.2187, − 0.1115, 0.9320, 0.2667] and plot the norm of the transverse perturbation ∥Z(t)∥ in Fig. 8 A on a logarithmic scale. As evident by the slope of ∥Z(t)∥ vs t, the transient rate of growth ξ(− A) is larger than the asymptotic rate of decay α(− A).Fig. 8Transient growth and decay in consensus dynamics.Panels (A, B) show the transverse consensus dynamics governed by Eq. (26) for the cases of stable and unstable dynamics, respectively. In both panels, the vertical axis is shown on a logarithmic scale, so that the slopes of the curves represent the rates of decay (panel A) and growth (panel B). In both cases, the transient rate, ξ(− A), exceeds the corresponding asymptotic rate, α(− A), demonstrating that the initial decay or growth is faster than its long-term asymptotic behavior. Transient growth and decay in consensus dynamics. Panels (A, B) show the transverse consensus dynamics governed by Eq. (26) for the cases of stable and unstable dynamics, respectively. In both panels, the vertical axis is shown on a logarithmic scale, so that the slopes of the curves represent the rates of decay (panel A) and growth (panel B). In both cases, the transient rate, ξ(− A), exceeds the corresponding asymptotic rate, α(− A), demonstrating that the initial decay or growth is faster than its long-term asymptotic behavior. Next, we add an adversarial agent to the above Laplacian matrix with a budget − c = − 0.001 and obtain 30\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${L}_{aug}=\left[\begin{array}{cccccc}1&-1&0&0&0&0\\ 0&1&0&0&-1&0\\ -1&-1&2&0&0&0\\ 0&0&0&-0.001&0&0.001\\ 0&0&0&-1&1&0\\ 0&0&0&0.001&0&-0.001\end{array}\right]$$\end{document}Laug=1−100000100−10−1−12000000−0.00100.001000−1100000.0010−0.001 which has mixed signed real-part eigenvalues. For the Laplacian matrix (30), the corresponding matrix Aaug in Eq. (26) is 31\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${A}_{aug}=\left[\begin{array}{ccccc}1.4923&-0.1527&0.2024&-0.9160&0.0840\\ -0.2178&2.1372&0.4923&0.3739&0.3739\\ 0.4923&-0.1527&0.2014&0.0840&0.0850\\ 0.4923&-0.1527&-0.7976&1.0840&0.0840\\ 0.4923&-0.1527&0.2034&0.0840&0.0830\end{array}\right].$$\end{document}Aaug=1.4923−0.15270.2024−0.91600.0840−0.21782.13720.49230.37390.37390.4923−0.15270.20140.08400.08500.4923−0.1527−0.79761.08400.08400.4923−0.15270.20340.08400.0830. Here, ξ(− Aaug) = 0.0874≥α(− Aaug) = 0.002. We simulate Eq. (26) from the initial condition Z(0) = [0.1202, 0.1937, 0.1545, 0.8538, 0.4418] and plot the norm of the transverse perturbation ∥Z(t)∥ in Fig. 8 B in the log scale. As evident by the slope of ∥Z(t)∥ vs t, the transient rate of decay ξ(− A) is larger than the asymptotic rate of decay α(− A). Proof of Proposition 2 Given the possibly asymmetric Laplacian L and the budget − c < 0, we solve 32\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ {{\min }_{{{{\boldsymbol{b}}}},{{{\boldsymbol{x}}}}}}\quad {{{{\boldsymbol{x}}}}}^{\top }\left({V}^{\top }\frac{{L}_{aug}^{b}+{{L}_{aug}^{b}}^{\top }}{2}V\right){{{\boldsymbol{x}}}}\\ \,{{\mbox{subject}}} \,{{\mbox{to}}}\,\quad {{{{\boldsymbol{x}}}}}^{\top }{{{\boldsymbol{x}}}}=1,\\ {L}_{aug}^{b}=\left[\begin{array}{cc}L+\,{\mbox{diag}}\,&({{{\boldsymbol{b}}}})-{{{\boldsymbol{b}}}}\\ -{{{{\boldsymbol{b}}}}}^{\top }&-c\end{array}\right],\\ {b}_{i}\le 0,\quad \forall i=1,\ldots,N,\\ {\sum }_{i=1}^{N}{b}_{i}=-c.$$\end{document}minb,xx⊤V⊤Laugb+Laugb⊤2Vxsubjecttox⊤x=1,Laugb=L+diag(b)−b−b⊤−c,bi≤0,∀i=1,…,N,∑i=1Nbi=−c. First, we set y ≔ Vx which also implies 1⊤y = 0 and rewrite the optimization in y and b: 33\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ {{\min }_{{{{\boldsymbol{b}}}},{{{\boldsymbol{y}}}}}}\quad {{{{\boldsymbol{y}}}}}^{\top }\frac{{L}_{aug}^{b}+{{L}_{aug}^{b}}^{\top }}{2}{{{\boldsymbol{y}}}}\\ \,{{\mbox{subject}}}\, {{\mbox{to}}}\,\quad {{{{\boldsymbol{y}}}}}^{\top }{{{\boldsymbol{y}}}}=1,\\ {{{{\bf{1}}}}}^{\top }{{{\boldsymbol{y}}}}=0,\\ {L}_{aug}^{b}=\left[\begin{array}{cc}L+\,{\mbox{diag}}\,({{{\boldsymbol{b}}}})&-{{{\boldsymbol{b}}}}\\ -{{{{\boldsymbol{b}}}}}^{\top }&-c\end{array}\right],\\ {b}_{i}\le 0,\quad \forall i=1,\ldots,N,\\ {\sum }_{i=1}^{N}{b}_{i}=-c.$$\end{document}minb,yy⊤Laugb+Laugb⊤2ysubjecttoy⊤y=1,1⊤y=0,Laugb=L+diag(b)−b−b⊤−c,bi≤0,∀i=1,…,N,∑i=1Nbi=−c. In the above optimization, we set \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{\boldsymbol{y}}}}=:{[{{{{\boldsymbol{y}}}}}_{r}^{\top },{y}_{N+1}]}^{\top }$$\end{document}y=:[yr⊤,yN+1]⊤ and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{{\boldsymbol{y}}}}}_{r}^{\top }={[{y}_{1},{y}_{2},\ldots,{y}_{N}]}^{\top }\in {{\mathbb{R}}}^{N}$$\end{document}yr⊤=[y1,y2,…,yN]⊤∈RN, i.e., we separate the last entry of the vector y from the remaining entries. We also introduce the generic assumption yi ≠ yj, ∀ i ≠ j, i = 2, …, N, j = 2, …, N. The objective function is 34\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{{\boldsymbol{y}}}}}^{\top }\frac{{L}_{aug}^{b}+{{L}_{aug}^{b}}^{\top }}{2}{{{\boldsymbol{y}}}}= -{y}_{N+1}^{2}c+{{{{\boldsymbol{y}}}}}_{r}^{\top }\frac{L+{L}^{\top }}{2}{{{{\boldsymbol{y}}}}}_{r}\\ -2{y}_{N+1}{{{{\boldsymbol{y}}}}}_{r}^{\top }{{{\boldsymbol{b}}}}+{{{{\boldsymbol{y}}}}}_{r}^{\top }\,{\mbox{diag}}\,({{{\boldsymbol{b}}}}){{{{\boldsymbol{y}}}}}_{r}.$$\end{document}y⊤Laugb+Laugb⊤2y=−yN+12c+yr⊤L+L⊤2yr−2yN+1yr⊤b+yr⊤diag(b)yr. The two terms \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$-2{y}_{N+1}{{{{\boldsymbol{y}}}}}_{r}^{\top }{{{\boldsymbol{b}}}}+{{{{\boldsymbol{y}}}}}_{r}^{\top }\,{\mbox{diag}}\,({{{\boldsymbol{b}}}}){{{{\boldsymbol{y}}}}}_{r}$$\end{document}−2yN+1yr⊤b+yr⊤diag(b)yr in the above equation that explicitly depend on b are written as 35\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$-2{y}_{N+1}{{{{\boldsymbol{y}}}}}_{r}^{\top }{{{\boldsymbol{b}}}}+{{{{\boldsymbol{y}}}}}_{r}^{\top }\,{\mbox{diag}}\,({{{\boldsymbol{b}}}}){{{{\boldsymbol{y}}}}}_{r}= {\sum }_{i=1}^{N}-2{y}_{N+1}{y}_{i}{b}_{i}+{\sum }_{i=1}^{N}{y}_{i}^{2}{b}_{i}\\= \mathop{\sum }_{i=1}^{N}\left({y}_{i}^{2}-2{y}_{N+1}{y}_{i}\right){b}_{i}\\= :{\sum }_{i=1}^{N}{\beta }_{i}{b}_{i}$$\end{document}−2yN+1yr⊤b+yr⊤diag(b)yr=∑i=1N−2yN+1yibi+∑i=1Nyi2bi=∑i=1Nyi2−2yN+1yibi=:∑i=1Nβibi where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\beta }_{i}={y}_{i}^{2}-2{y}_{N+1}{y}_{i},\,i=1,2,\ldots,N$$\end{document}βi=yi2−2yN+1yi,i=1,2,…,N. Since these two terms in the objective function depend linearly on b and ∑jbj = − c and bj ≤ 0, ∀ j, thus one assigns all budget on the node with the maximum βi, i.e., \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${b}_{{i}^{*}}=-c$$\end{document}bi*=−c, bj = 0, ∀ j ≠ i*, and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${i}^{*}=\arg {{\max }_{i}}{\beta }_{i}$$\end{document}i*=argmaxiβi. That concludes the proof. □ We remark that Proposition 2 simply predicts under generic assumptions the particular structure of b*, the optimal b, namely that all the entries of b* will be zero except for one, but it does not predict which one. Proof of Proposition 3 We evaluate the algebraic connectivity using (2) and take the vector X0 = [N, −1, −1, ⋯ , −1]⊤ such that its entries sum to 0. Evaluating the Rayleigh quotient for Laug from (4) and X0 yields \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f\le \frac{{{{{\boldsymbol{X}}}}}_{0}^{\top }{L}_{aug}{{{{\boldsymbol{X}}}}}_{0}}{{{{{\boldsymbol{X}}}}}_{0}^{\top }{{{{\boldsymbol{X}}}}}_{0}}=-\frac{{(N+1)}^{2}c}{{N}^{2}+N}\le 0.$$\end{document}f≤X0⊤LaugX0X0⊤X0=−(N+1)2cN2+N≤0. Thus f ≤ 0. □ Proof of Proposition 4 Given the possibly asymmetric Laplacian L and the budget − c < 0, we solve 36\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ {{\min }_{{{{\boldsymbol{b}}}},{{{\boldsymbol{x}}}}}}\quad {{{{\boldsymbol{x}}}}}^{\top }\left({V}^{\top }\frac{{L}_{aug}^{u}+{{L}_{aug}^{u}}^{\top }}{2}V\right){{{\boldsymbol{x}}}}\\ \,{{\mbox{subject}}} \,{{\mbox{to}}}\,\quad {{{{\boldsymbol{x}}}}}^{\top }{{{\boldsymbol{x}}}}=1,\\ {L}_{aug}^{u}=\left[\begin{array}{cc}L+\,{\mbox{diag}}\,({{{\boldsymbol{b}}}})&-{{{\boldsymbol{b}}}}\\ {{{{\boldsymbol{0}}}}}^{\top }&0\end{array}\right],\\ {b}_{i}\le 0,\quad \forall i=1,\ldots,N,\\ {\sum }_{i=1}^{N}{b}_{i}=-c.$$\end{document}minb,xx⊤V⊤Laugu+Laugu⊤2Vxsubjecttox⊤x=1,Laugu=L+diag(b)−b0⊤0,bi≤0,∀i=1,…,N,∑i=1Nbi=−c. First, we set y ≔ Vx which also implies 1⊤y = 0 and rewrite the optimization in y and b: 37\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ {{\min }_{{{{\boldsymbol{b}}}},{{{\boldsymbol{y}}}}}}\quad {{{{\boldsymbol{y}}}}}^{\top }\frac{{L}_{aug}^{u}+{{L}_{aug}^{u}}^{\top }}{2}{{{\boldsymbol{y}}}}\\ \,{{\mbox{subject}}}\, {{\mbox{to}}}\,\quad {{{{\boldsymbol{y}}}}}^{\top }{{{\boldsymbol{y}}}}=1,\\ {{{{\bf{1}}}}}^{\top }{{{\boldsymbol{y}}}}=0,\\ {L}_{aug}^{u}=\left[\begin{array}{cc}L+\,{\mbox{diag}}\,({{{\boldsymbol{b}}}})&-{{{\boldsymbol{b}}}}\\ {{{{\boldsymbol{0}}}}}^{\top }&0\end{array}\right],\\ {b}_{i}\le 0,\quad \forall i=1,\ldots,N,\\ {\sum }_{i=1}^{N}{b}_{i}=-c.$$\end{document}minb,yy⊤Laugu+Laugu⊤2ysubjecttoy⊤y=1,1⊤y=0,Laugu=L+diag(b)−b0⊤0,bi≤0,∀i=1,…,N,∑i=1Nbi=−c. In the above optimization, we set \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{\boldsymbol{y}}}}=:{[{{{{\boldsymbol{y}}}}}_{r}^{\top },{y}_{N+1}]}^{\top }$$\end{document}y=:[yr⊤,yN+1]⊤ and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{{\boldsymbol{y}}}}}_{r}^{\top }={[{y}_{1},{y}_{2},\ldots,{y}_{N}]}^{\top }\in {{\mathbb{R}}}^{N}$$\end{document}yr⊤=[y1,y2,…,yN]⊤∈RN, i.e., we separate the last entry of the vector y from the remaining entries. We also introduce the generic assumption yi ≠ yj, ∀ i ≠ j, i = 2, …, N, j = 2, …, N. The objective function is 38\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{array}{r}\begin{array}{ll}{{{{\boldsymbol{y}}}}}^{\top }\frac{{L}_{aug}^{u}+{{L}_{aug}^{u}}^{\top }}{2}{{{\boldsymbol{y}}}}=&-{y}_{N+1}{{{{\boldsymbol{y}}}}}_{r}^{\top }{{{\boldsymbol{b}}}}+{{{{\boldsymbol{y}}}}}_{r}^{\top }\frac{L+{L}^{\top }}{2}{{{{\boldsymbol{y}}}}}_{r}\\ &+{{{{\boldsymbol{y}}}}}_{r}^{\top }\,{\mbox{diag}}\,({{{\boldsymbol{b}}}}){{{{\boldsymbol{y}}}}}_{r}\end{array}\end{array}$$\end{document}y⊤Laugu+Laugu⊤2y=−yN+1yr⊤b+yr⊤L+L⊤2yr+yr⊤diag(b)yr The two terms \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$-{y}_{N+1}{{{{\boldsymbol{y}}}}}_{r}^{\top }{{{\boldsymbol{b}}}}+{{{{\boldsymbol{y}}}}}_{r}^{\top }\,{\mbox{diag}}\,({{{\boldsymbol{b}}}}){{{{\boldsymbol{y}}}}}_{r}$$\end{document}−yN+1yr⊤b+yr⊤diag(b)yr in the above equation that explicitly depend on b are written as 39\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$-{y}_{N+1}{{{{\boldsymbol{y}}}}}_{r}^{\top }{{{\boldsymbol{b}}}}+{{{{\boldsymbol{y}}}}}_{r}^{\top }\,{\mbox{diag}}\,({{{\boldsymbol{b}}}}){{{{\boldsymbol{y}}}}}_{r}= {\sum }_{i=1}^{N}-{y}_{N+1}{y}_{i}{b}_{i}+{\sum }_{i=1}^{N}{y}_{i}^{2}{b}_{i}\\= {\sum }_{i=1}^{N}\left({y}_{i}^{2}-{y}_{N+1}{y}_{i}\right){b}_{i}\\= {\sum }_{i=1}^{N}{\beta }_{i}{b}_{i}$$\end{document}−yN+1yr⊤b+yr⊤diag(b)yr=∑i=1N−yN+1yibi+∑i=1Nyi2bi=∑i=1Nyi2−yN+1yibi=∑i=1Nβibi where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\beta }_{i}={y}_{i}^{2}-{y}_{N+1}{y}_{i},\,i=1,2,\ldots,N$$\end{document}βi=yi2−yN+1yi,i=1,2,…,N. Since these two terms in the objective function depend linearly on b and ∑jbj = − c and bj ≤ 0, ∀ j, thus one assigns all budget on the node with the maximum βi, i.e., \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${b}_{{i}^{*}}=-c$$\end{document}bi*=−c, bj = 0, ∀ j ≠ i*, and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${i}^{*}=\arg {{\max }_{i}}{\beta }_{i}$$\end{document}i*=argmaxiβi. That concludes the proof. □ Proof of Proposition 5 We evaluate the algebraic connectivity using (2) and take the vector X0 = [N, −1, −1, ⋯ , −1]⊤ such that its entries sum to 0. Evaluating the Rayleigh quotient for Laug from (5) and x0 yields \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f\le \frac{{{{{\boldsymbol{X}}}}}_{0}^{\top }{L}_{aug}{{{{\boldsymbol{X}}}}}_{0}}{{{{{\boldsymbol{X}}}}}_{0}^{\top }{{{{\boldsymbol{X}}}}}_{0}}=-\frac{(N+1)c}{{N}^{2}+N}\le 0.$$\end{document}f≤X0⊤LaugX0X0⊤X0=−(N+1)cN2+N≤0. Thus, f ≤ 0, and the proof is complete. □ Digraphs with a Unidirectional Connection Here we use matrix perturbation theory79 to predict the changes in the eigenvalues of a given matrix A0 subject to a small perturbation ϵA1, i.e., Λϵ = Λ0 + ϵΛ1 + ϵ2Λ2 + ⋯ where Λϵ is the estimated eigenvalues of the matrix Aϵ = A0 + ϵA1, Λ0 is the exact eigenvalues of A0, and ϵkΛk, ∀ k ≥ 1, are the kth order approximation of changes in the eigenvalues Λ0. In the following, we focus on the case of directed networks, i.e., for which the matrix A0 is asymmetric and set k = 1. Thus, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{\Lambda }}}_{1}=\,{\mbox{diag}}\,({W}_{0}^{*}{A}_{1}{V}_{0})$$\end{document}Λ1=diag(W0*A1V0), where W0 and V0 are the matrices of the left and the right eigenvectors of A0 such that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${W}_{0}^{*}{V}_{0}=I$$\end{document}W0*V0=I, and the superscript * denotes conjugate transpose. The limit of small c and unidirectional connection: In this case, we set ϵ = c and 40\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${A}_{0}={V}^{\top }\frac{\tilde{L}+{\tilde{L}}^{\top }}{2}V,\quad {A}_{1}={V}^{\top }\frac{{P}_{i}+{P}_{i}^{\top }}{2}V$$\end{document}A0=V⊤L~+L~⊤2V,A1=V⊤Pi+Pi⊤2V where 41\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\tilde{L}=\left[\begin{array}{cccccccc}&&&&&&&0\\ &&&&&&&\vdots \\ &&&&&&&0\\ &&&L&&&&0\\ &&&&&&&0\\ &&&&&&&\vdots \\ &&&&&&&0\\ 0&\ldots &0&0&0&\ldots &0&0\end{array}\right],$$\end{document}L~=0⋮0L00⋮00…000…00,42\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${P}_{i}=\left[\begin{array}{cccccccc}0&\ldots &0&0&0&\ldots &0&0\\ \vdots &\ddots &\vdots &\vdots &\vdots &\ddots &\vdots &\vdots \\ 0&\ldots &0&0&0&\ldots &0&0\\ 0&\ldots &0&-1&0&\ldots &0&1\\ 0&\ldots &0&0&0&\ldots &0&0\\ \vdots &\ddots &\vdots &\vdots &\vdots &\ddots &\vdots &\vdots \\ 0&\ldots &0&0&0&\ldots &0&0\\ 0&\ldots &0&0&0&\ldots &0&0\end{array}\right]$$\end{document}Pi=0…000…00⋮⋱⋮⋮⋮⋱⋮⋮0…000…000…0−10…010…000…00⋮⋱⋮⋮⋮⋱⋮⋮0…000…000…000…00 where Pi has the entry -1 on the main diagonal on the ith position. The first order matrix perturbation theory is then 43\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${f}_{b}= {f}_{0}+c\frac{df}{db}\\= {{{{\boldsymbol{v}}}}}_{0}^{\top }{A}_{0}{{{{\boldsymbol{v}}}}}_{0}+c{{{{\boldsymbol{v}}}}}_{0}^{\top }{A}_{1}{{{{\boldsymbol{v}}}}}_{0}\\= {{{{\boldsymbol{v}}}}}_{0}^{\top }{V}^{\top }\frac{\tilde{L}+{\tilde{L}}^{\top }}{2}V{{{{\boldsymbol{v}}}}}_{0}+c{{{{\boldsymbol{v}}}}}_{0}^{\top }{V}^{\top }\frac{{P}_{i}+{P}_{i}^{\top }}{2}V{{{{\boldsymbol{v}}}}}_{0}\\= :{{{{\boldsymbol{y}}}}}_{0}^{\top }\frac{\tilde{L}+{\tilde{L}}^{\top }}{2}{{{{\boldsymbol{y}}}}}_{0}+c{{{{\boldsymbol{y}}}}}_{0}^{\top }\frac{{P}_{i}+{P}_{i}^{\top }}{2}{{{{\boldsymbol{y}}}}}_{0}\\= :{f}_{0}+c{{{{\boldsymbol{y}}}}}_{0}^{\top }\frac{{P}_{i}+{P}_{i}^{\top }}{2}{{{{\boldsymbol{y}}}}}_{0}$$\end{document}fb=f0+cdfdb=v0⊤A0v0+cv0⊤A1v0=v0⊤V⊤L~+L~⊤2Vv0+cv0⊤V⊤Pi+Pi⊤2Vv0=:y0⊤L~+L~⊤2y0+cy0⊤Pi+Pi⊤2y0=:f0+cy0⊤Pi+Pi⊤2y0 where y0 ≔ Vv0 and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{{\boldsymbol{y}}}}}_{0}^{\top }\left(\frac{\tilde{L}+{\tilde{L}}^{\top }}{2}\right){{{{\boldsymbol{y}}}}}_{0}={f}_{0}$$\end{document}y0⊤L~+L~⊤2y0=f0. Note that since the graph is balanced, the Laplacian matrix L has both row and column sums equal to zero. Also, considering the block diagonal structure of the matrix \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\tilde{L}$$\end{document}L~ results in having two zero eigenvalues, one corresponding to the eigenvector with all entries equal ones and the other eigenvalue f0 = 0 corresponding to the eigenvector \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{{\boldsymbol{y}}}}}_{0}=\frac{1}{\sqrt{N(N+1)}} [1,\,1,\,\ldots 1,\,-N] \in {{\mathbb{R}}}^{N+1}$$\end{document}y0=1N(N+1)[1,1,…1,−N]∈RN+1. We are interested in the change in the zero eigenvalue corresponding to the eigenvector y0. It thus follows 44\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{array}{r}\begin{array}{ll}{f}_{b}&={f}_{0}+c{{{{\boldsymbol{y}}}}}_{0}^{\top }\frac{{P}_{i}+{P}_{i}^{\top }}{2}{{{{\boldsymbol{y}}}}}_{0}=0+c(-0.1)=-0.1c.\end{array}\end{array}$$\end{document}fb=f0+cy0⊤Pi+Pi⊤2y0=0+c(−0.1)=−0.1c. The limit of large c and unidirectional connection: Here, we set ϵ = 1 and 45\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${A}_{0}=c{V}^{\top }\frac{{P}_{i}+{P}_{i}^{\top }}{2}V=c{V}^{\top }{P}_{i}V,\quad {A}_{1}={V}^{\top }\frac{\tilde{L}+{\tilde{L}}^{\top }}{2}V$$\end{document}A0=cV⊤Pi+Pi⊤2V=cV⊤PiV,A1=V⊤L~+L~⊤2V where the matrices Pi and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\tilde{L}$$\end{document}L~ are defined in Eq. (41). Now, the eigenvalue of interest is the most negative nonzero eigenvalue of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\frac{{P}_{i}+{P}_{i}^{\top }}{2}$$\end{document}Pi+Pi⊤2 which is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${f}_{0}=-\frac{\sqrt{2}+1}{2}$$\end{document}f0=−2+12. The corresponding eigenvector is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{{\boldsymbol{y}}}}}_{0}^{i}={[0\cdots 0\sqrt{2}+10\cdots 0-1]}^{\top }$$\end{document}y0i=[0⋯02+10⋯0−1]⊤ where the ith and the last entry of this eigenvector have nonzero elements. We set \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{{\boldsymbol{y}}}}}_{0}^{i}=V{{{{\boldsymbol{v}}}}}_{0}^{i}$$\end{document}y0i=Vv0i as the effective vector for the first-order approximation of matrix perturbation theory. The first-order change in the eigenvalue f0 is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\xi \left(M\right) < 0$$\end{document}ξM<0. Therefore, the perturbed eigenvalue after selecting node i is 46\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{{{\boldsymbol{y}}}}}_{0}^{i}}^{\top }{A}_{1}{{{{\boldsymbol{y}}}}}_{0}^{i}={{{{{\boldsymbol{y}}}}}_{0}^{i}}^{\top }\frac{\tilde{L}+{\tilde{L}}^{\top }}{2}{{{{\boldsymbol{y}}}}}_{0}^{i}=(3+2\sqrt{2}){L}_{ii} > 0$$\end{document}y0i⊤A1y0i=y0i⊤L~+L~⊤2y0i=(3+22)Lii>0 Digraphs with a Bidirectional Connection The limit of small c and bidirectional connection: all the derivations are similar to the case of unidirectional connection except for the matrix 47\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${P}_{i}=\left[\begin{array}{cccccccc}0&\ldots &0&0&0&\ldots &0&0\\ \vdots &\ddots &\vdots &\vdots &\vdots &\ddots &\vdots &\vdots \\ 0&\ldots &0&0&0&\ldots &0&0\\ 0&\ldots &0&-1&0&\ldots &0&1\\ 0&\ldots &0&0&0&\ldots &0&0\\ \vdots &\ddots &\vdots &\vdots &\vdots &\ddots &\vdots &\vdots \\ 0&\ldots &0&0&0&\ldots &0&0\\ 0&\ldots &0&1&0&\ldots &0&-1\end{array}\right].$$\end{document}Pi=0…000…00⋮⋱⋮⋮⋮⋱⋮⋮0…000…000…0−10…010…000…00⋮⋱⋮⋮⋮⋱⋮⋮0…000…000…010…0−1. This results in 48\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{array}{r}\begin{array}{ll}{f}_{b}&={f}_{0}+c{{{{\boldsymbol{y}}}}}_{0}^{\top }\frac{{P}_{i}+{P}_{i}^{\top }}{2}{{{{\boldsymbol{y}}}}}_{0}=0+c(-1.1)=-1.1c.\end{array}\end{array}$$\end{document}fb=f0+cy0⊤Pi+Pi⊤2y0=0+c(−1.1)=−1.1c. The limit of large c and bidirectional connection: Here, we set ϵ = 1 and 49\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${A}_{0}=c{V}^{\top }\frac{{P}_{i}+{P}_{i}^{\top }}{2}V=c{V}^{\top }{P}_{i}V,\quad {A}_{1}={V}^{\top }\frac{\tilde{L}+{\tilde{L}}^{\top }}{2}V$$\end{document}A0=cV⊤Pi+Pi⊤2V=cV⊤PiV,A1=V⊤L~+L~⊤2V where the matrices Pi and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\tilde{L}$$\end{document}L~ are defined in Eqs. (47) and (41). Now, the eigenvalue of interest is the one and only nonzero eigenvalue of V⊤PiV, which is f0 = − 2. Since V is a similarity transformation, the matrix Pi has the same eigenvalue f0 = − 2 and the corresponding eigenvector is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{{\boldsymbol{y}}}}}_{0}^{i}={[0\cdots 0-1/\sqrt{2}0\cdots 01/\sqrt{2}]}^{\top }$$\end{document}y0i=[0⋯0−1/20⋯01/2]⊤ where the ith and the last entry of this eigenvectors have nonzero elements. We define \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{{\boldsymbol{y}}}}}_{0}^{i}:=V{{{{\boldsymbol{v}}}}}_{0}^{i}$$\end{document}y0i:=Vv0i as the effective vector for the first-order approximation of matrix perturbation theory. The first-order change in the eigenvalue f0 is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${f}_{b}={f}_{0}+\epsilon {{{{{\boldsymbol{y}}}}}_{0}^{i}}^{\top }{A}_{1}{{{{\boldsymbol{y}}}}}_{0}^{i}=-\frac{\sqrt{2}+1}{2}c+(3+2\sqrt{2}){L}_{ii}.$$\end{document}fb=f0+ϵy0i⊤A1y0i=−2+12c+(3+22)Lii.. Therefore, the perturbed eigenvalue after selecting node i is 50\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${f}_{b}={f}_{0}+\epsilon {{{{{\boldsymbol{y}}}}}_{0}^{i}}^{\top }{A}_{1}{{{{\boldsymbol{y}}}}}_{0}^{i}=-2c+\frac{{L}_{ii}}{2}.$$\end{document}fb=f0+ϵy0i⊤A1y0i=−2c+Lii2. Proof of mean-slope relation We show this relation < df/dc > = − 1/N in what follows. We emphasize that we proceed without introducing the assumption that the network is balanced. Based on first order perturbation theory, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$d{f}_{i}/dc={{{{\boldsymbol{y}}}}}_{0}^{\top }\frac{{P}_{i}+{P}_{i}^{\top }}{2}{{{{\boldsymbol{y}}}}}_{0}$$\end{document}dfi/dc=y0⊤Pi+Pi⊤2y0 where y0 = Vv0 where v0 is eigenvector corresponding to the smallest eigenvalue of the matrix \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${V}^{\top }\frac{\tilde{L}+{\tilde{L}}^{\top }}{2}V$$\end{document}V⊤L~+L~⊤2V and the matrices Pi and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\tilde{L}$$\end{document}L~ are defined in Eq. (41). Note that y0 is in the range of the matrix V, resulting in the zero-sum of the entries of the vector y0. It follows 51\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\left \langle \frac{df}{dc} \right\rangle= \frac{1}{N}{\sum}_{i=1}^{N}\frac{d{f}_{i}}{dc}=\frac{1}{N}{{{{\boldsymbol{y}}}}}_{0}^{\top }\left({\sum}_{i=1}^{N}\frac{{P}_{i}+{P}_{i}^{\top }}{2}\right){{{{\boldsymbol{y}}}}}_{0}\\= :\frac{1}{N}{{{{\boldsymbol{y}}}}}_{0}^{\top }\left(\overline{P}\right){{{{\boldsymbol{y}}}}}_{0},$$\end{document}dfdc=1N∑i=1Ndfidc=1Ny0⊤∑i=1NPi+Pi⊤2y0=:1Ny0⊤P¯y0, where the matrix \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\bar{P}$$\end{document}P¯ has the following form 52\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\bar{P}={\sum }_{i=1}^{N}\frac{{P}_{i}+{P}_{i}^{\top }}{2}=\left[\begin{array}{ccccc}-1&&&&\frac{1}{2}\\ &-1&&&\frac{1}{2}\\ &&\ddots &&\vdots \\ &&&-1&\frac{1}{2}\\ \frac{1}{2}&\frac{1}{2}&\ldots &\frac{1}{2}&0\end{array}\right].$$\end{document}P¯=∑i=1NPi+Pi⊤2=−112−112⋱⋮−1121212…120. It follows that the matrix \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\bar{P}$$\end{document}P¯ has N − 1 eigenvalues which are equal to − 1, and the corresponding eigenvectors have their sum of the entries equal to zero. This suggests that these eigenvectors form a basis for the vector y0 and thus the product \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{{\boldsymbol{y}}}}}_{0}^{\top }\bar{P}{{{{\boldsymbol{y}}}}}_{0}=-1$$\end{document}y0⊤P¯y0=−1. Therefore, < df/dc > = − 1/N. □ Asymptotic stability analysis for the case of synchronization dynamics Next, we present standard derivations from refs. 4546. A particular solution for the synchronization dynamics (11) is the synchronous solution x1(t) = x2(t) = . . . = xN(t) = s(t), where s(t), evolves in time based on the equation: 53\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\dot{{{{\boldsymbol{s}}}}}(t)={{{\boldsymbol{F}}}}({{{\boldsymbol{s}}}}(t)).$$\end{document}s°(t)=F(s(t)). The synchronization manifold is the set of phase space points that satisfy x1 = x2 = …xN. We study the time evolution of infinitesimal perturbations about the synchronization manifold, δxi(t) ≔ xi(t) − s(t). The synchronization is stable if δxi(t) → 0 as t → ∞, ∀ i, which implies xi(t) → s(t) as t → ∞, ∀ i. To study the asymptotic stability of the perturbations δxi(t), we linearize Eq. (11) about s(t) and derive the following linearized sets of dynamical equations: 54\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\delta {\dot{{{{\boldsymbol{x}}}}}}_{i}(t)=D{{{\boldsymbol{F}}}}({{{\boldsymbol{s}}}}(t))\delta {{{{\boldsymbol{x}}}}}_{i}(t)-\sigma {\sum }_{j=1}^{N}{L}_{ij}D{{{\boldsymbol{H}}}}({{{\boldsymbol{s}}}}(t))\delta {{{{\boldsymbol{x}}}}}_{j}(t),$$\end{document}δx°i(t)=DF(s(t))δxi(t)−σ∑j=1NLijDH(s(t))δxj(t),i = 1, …, N, where DF(s(t)) and DH(s(t)) are the Jacobians of F and H evaluated at s(t), respectively. A compact form of the above equations can be obtained by first concatenating the perturbation vectors as \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\delta {{{\boldsymbol{X}}}}(t):={\left[\delta {{{{\boldsymbol{x}}}}}_{1}{(t)}^{\top },\ldots,\delta {{{{\boldsymbol{x}}}}}_{N}{(t)}^{\top }\right]}^{\top }\in {{\mathbb{R}}}^{mN}$$\end{document}δX(t):=δx1(t)⊤,…,δxN(t)⊤⊤∈RmN, and then writing: 55\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\delta \dot{{{{\boldsymbol{X}}}}}(t)=\left({I}_{N}\otimes D{{{\boldsymbol{F}}}}(s)-\sigma L\otimes D{{{\boldsymbol{H}}}}(s)\right)\delta {{{\boldsymbol{X}}}}(t),$$\end{document}δX°(t)=IN⊗DF(s)−σL⊗DH(s)δX(t), where ⊗ denotes the Kronecker product. We call V the matrix having for columns the eigenvectors of L and Λ the associated diagonal matrix, having the eigenvalues of L on the main diagonal. Equation (55) can be decoupled through the eigen-decomposition of the Laplacian matrix L by applying the similarity transformation \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$T=V\otimes {I}_{m}\in {{\mathbb{R}}}^{mN\times mN}$$\end{document}T=V⊗Im∈RmN×mN, 56\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\delta \dot{{{{\boldsymbol{Z}}}}}(t)=\left({I}_{N}\otimes D{{{\boldsymbol{F}}}}(s)-\sigma {{\Lambda }}\otimes D{{{\boldsymbol{H}}}}(s)\right)\delta {{{\boldsymbol{Z}}}}(t),$$\end{document}δZ°(t)=IN⊗DF(s)−σΛ⊗DH(s)δZ(t),where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\delta {{{\boldsymbol{Z}}}}(t)={T}^{-1}\delta {{{\boldsymbol{X}}}}(t)\in {{\mathbb{R}}}^{mN}$$\end{document}δZ(t)=T−1δX(t)∈RmN. By setting \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${[\delta {{{{\boldsymbol{z}}}}}_{1}{(t)}^{\top },\ldots,\delta {{{{\boldsymbol{z}}}}}_{N}{(t)}^{\top }]}^{\top }:=\delta {{{\boldsymbol{Z}}}}(t)$$\end{document}[δz1(t)⊤,…,δzN(t)⊤]⊤:=δZ(t), with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\delta {{{{\boldsymbol{z}}}}}_{i}(t)\in {{\mathbb{R}}}^{m},\forall i$$\end{document}δzi(t)∈Rm,∀i, we can write the decomposed equation of transformed perturbations as 57\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\delta {\dot{{{{\boldsymbol{z}}}}}}_{i}(t)=\left(D{{{\boldsymbol{F}}}}({{{\boldsymbol{s}}}}(t))-\sigma {\lambda }_{i}D{{{\boldsymbol{H}}}}({{{\boldsymbol{s}}}}(t))\right)\delta {{{{\boldsymbol{z}}}}}_{i}(t),$$\end{document}δz°i(t)=DF(s(t))−σλiDH(s(t))δzi(t),i = 1, …, N. By construction, one eigenvalue λ1 = 0, which is associated to stability of the dynamics on the synchronization manifold. As such it is excluded from the analysis that follows, which focuses on the stability of the dynamics transverse to this manifold. The synchronization is stable if \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\delta {{{{\boldsymbol{z}}}}}_{i}(t)\to 0$$\end{document}δzi(t)→0 as t →∞, ∀ i. From Eq. (57), we see that the stability of the synchronization is dependent on the Jacobians DF(s(t)) and DH(s(t)), and the scalar σλi. We introduce the parameter K = σλi and determine the stability of 58\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\dot{{{{\boldsymbol{y}}}}}(t)=\left(D{{{\boldsymbol{F}}}}({{{\boldsymbol{s}}}}(t))-KD{{{\boldsymbol{H}}}}({{{\boldsymbol{s}}}}(t))\right){{{\boldsymbol{y}}}}(t),$$\end{document}y°(t)=DF(s(t))−KDH(s(t))y(t), where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{\boldsymbol{y}}}}(t)\in {{\mathbb{R}}}^{m}$$\end{document}y(t)∈Rm is a generic vector representing perturbations. The stability is assessed through the evaluation of the Maximum Lyapunov Exponent (MLE), 59\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\,{\mbox{MLE}}\,={{\lim }_{t\to \infty }}\frac{1}{t}\log \frac{\parallel {{{\boldsymbol{y}}}}(t)\parallel }{\parallel {{{\boldsymbol{y}}}}(0)\parallel }.$$\end{document}MLE=limt→∞1tlog∥y(t)∥∥y(0)∥. If the MLE is negative (positive), the above system is stable (unstable). Now, assume the set of parameters \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{\mathcal{K}}}}$$\end{document}K for which the system (58) is stable (MLE < 0). If \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\sigma {\lambda }_{i}\in {{{\mathcal{K}}}}$$\end{document}σλi∈K, i = 2, . . . , N, then the synchronization dynamics (11) is stable and xi(t) → s(t) when t → ∞. The master stability function (MSF) maps the parameter K to the maximum Lyapunov exponent (MLE) of Eq. (58). In the following, we present MSF plots for real values of K for three well-known oscillators, the Lorenz, Rössler, and Chua systems, and for several choices of the output function H(x). For all combinations of F(x) and H(x) considered in this study, the MSF is positive for negative values of K. Under the assumption that this property holds in general, it follows that a sufficient condition for the synchronous state to become unstable is that at least one of the eigenvalues of the Laplacian matrix L has a negative real part. Lorenz MSF plots The state vector, the local dynamics, and the coupling function for the Lorenz system are 60\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{array}{r}{{{\boldsymbol{x}}}}=\left[\begin{array}{c}x\\ y\\ z\end{array}\right],\quad {{{\boldsymbol{F}}}}({{{\boldsymbol{x}}}})=\left[\begin{array}{c}10(y-x)\\ x(28-z)-y\\ xy-\frac{8}{3}z\end{array}\right],\quad {{{\boldsymbol{H}}}}({{{\boldsymbol{x}}}})=H{{{\boldsymbol{x}}}},\end{array}$$\end{document}x=xyz,F(x)=10(y−x)x(28−z)−yxy−83z,H(x)=Hx, where the matrix H is the linear coupling matrix. We provide 9 MSF plots for the Lorenz system, where for each plot, a different entry of H is equal to 1, and all others are zero. It follows that the Jacobian DH(s) = H. The Jacobian of the local dynamics is 61\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{\boldsymbol{s}}}}=\left[\begin{array}{c}{x}_{s}\\ {y}_{s}\\ {z}_{s}\end{array}\right],\quad D{{{\boldsymbol{F}}}}({{{\boldsymbol{s}}}})=\left[\begin{array}{ccc}-10&10&0\\ 28-{z}_{s}&-1&-{x}_{s}\\ {y}_{s}&{x}_{s}&-\frac{8}{3}\end{array}\right]$$\end{document}s=xsyszs,DF(s)=−1010028−zs−1−xsysxs−83 Figure 9 shows that the MSF is positive in all different coupling setups over the negative range of the MSF argument K. Thus it shows that the synchronization is locally unstable for negative ranges of the parameter K.Fig. 9Master stability functions for both positive and negative values of the function argument.Master stability plots for the Lorenz system (A), Roessler system (B), and Chua System (C). Plots show the Maximum Lyapunov Exponent (MLE) as the argument K of Eq. (58) is varied. In each subfigure, panel in row i (from the top) and column j (from the left) shows the case when Hij = 1, and all other entries of the matrix H are zero. Master stability functions for both positive and negative values of the function argument. Master stability plots for the Lorenz system (A), Roessler system (B), and Chua System (C). Plots show the Maximum Lyapunov Exponent (MLE) as the argument K of Eq. (58) is varied. In each subfigure, panel in row i (from the top) and column j (from the left) shows the case when Hij = 1, and all other entries of the matrix H are zero. Rössler MSF plots The state vector, the local dynamics, and the coupling function for the Rossler system are 62\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{array}{r}{{{\boldsymbol{x}}}}=\left[\begin{array}{c}x\\ y\\ z\end{array}\right],\quad {{{\boldsymbol{F}}}}({{{\boldsymbol{x}}}})=\left[\begin{array}{c}-y-z\\ x+0.1y\\ 0.1+(x-35)z\end{array}\right],\quad {{{\boldsymbol{H}}}}({{{\boldsymbol{x}}}})=H{{{\boldsymbol{x}}}},\end{array}$$\end{document}x=xyz,F(x)=−y−zx+0.1y0.1+(x−35)z,H(x)=Hx, where the matrix H is the linear coupling matrix. We provide 9 MSF plots for the Rossler system, where for each plot, a different entry of H is equal to 1, and all others are zero. It follows that the Jacobian DH(s) = H. The Jacobian of the local dynamics is 63\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{\boldsymbol{s}}}}=\left[\begin{array}{c}{x}_{s}\\ {y}_{s}\\ {z}_{s}\end{array}\right],\quad D{{{\boldsymbol{F}}}}({{{\boldsymbol{s}}}})=\left[\begin{array}{ccc}0&-1&-1\\ 1&0.1&0\\ {z}_{s}&0&{x}_{s}-35\end{array}\right]$$\end{document}s=xsyszs,DF(s)=0−1−110.10zs0xs−35 Figure 9 shows that the MSF is positive in all different coupling setups over the negative range of the MSF argument K. Thus it shows that the synchronization is locally unstable for negative ranges of the parameter K. Chua’s circuit MSF plots The state vector, the local dynamics, and the coupling function for the Chua’s circuit system are 64\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{array}{r}{{{\boldsymbol{x}}}}=\left[\begin{array}{c}x\\ y\\ z\end{array}\right],\quad {{{\boldsymbol{F}}}}({{{\boldsymbol{x}}}})=\left[\begin{array}{c}10(y-x+g(x))\\ x-y+z\\ \left.-17.85y\right]\end{array}\right],\quad {{{\boldsymbol{H}}}}({{{\boldsymbol{x}}}})=H{{{\boldsymbol{x}}}},\end{array}$$\end{document}x=xyz,F(x)=10(y−x+g(x))x−y+z−17.85y,H(x)=Hx, where the matrix H is the linear coupling matrix, and the function 65\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$g(x)=\left\{\begin{array}{cc}-bx-a+b,& x > 1,\\ -ax,& | x| < 1,\\ -bx+a-b,& x < -1,\end{array}\right.,\quad \left\{\begin{array}{c}a=-1.2,\\ b=-0.7.\end{array}\right.$$\end{document}g(x)=−bx−a+b,x>1,−ax,∣x∣<1,−bx+a−b,x<−1,,a=−1.2,b=−0.7. We provide 9 MSF plots for the Chua’s circuit system, where for each plot, a different entry of H is equal to 1, and all others are zero. It follows that the Jacobian DH(s) = H. The Jacobian of the local dynamics is 66\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{\boldsymbol{s}}}}=\left[\begin{array}{c}{x}_{s}\\ {y}_{s}\\ {z}_{s}\end{array}\right],\quad D{{{\boldsymbol{F}}}}({{{\boldsymbol{s}}}})=\left[\begin{array}{ccc}-10-10d({x}_{s})&10&0\\ 1&-1&1\\ 0&-17.85&0\end{array}\right]$$\end{document}s=xsyszs,DF(s)=−10−10d(xs)1001−110−17.850 where d(xs) = b when ∣xs∣ > 1, and d(xs) = a, otherwise. Figure 9 shows that the MSF is positive in all different coupling setups over the negative range of the MSF argument K. Thus, it shows that the synchronization is locally unstable for negative ranges of the parameter K. Asymptotic stability analysis for the case of power grid dynamics We linearize Eq. (14) about the synchronous operating state \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\theta }_{i}^{*}={\omega }_{s}t+{\theta }_{i}^{0}$$\end{document}θi*=ωst+θi0, 67\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{array}{rcl}\delta {\ddot{\vartheta }}_{i}(t)&=&-\gamma {\delta \dot{\vartheta }}_{i}(t)-{\sum }_{j=1,j\ne i}^{N}{A}_{ij}\cos ({\theta }_{i}^{0}-{\theta }_{j}^{0})(\delta {\vartheta }_{i}-\delta {\vartheta }_{j})\\ &=&-\gamma {\delta \dot{\vartheta }}_{i}(t)-{\sum }_{j=1,j\ne i}^{N}{A}_{ij}^{{\prime} }(\delta {\vartheta }_{i}-\delta {\vartheta }_{j}) \hfill \\ &=&-\gamma {\delta \dot{\vartheta }}_{i}(t)-{\sum }_{j=1}^{N}{L}_{ij}^{{\prime} }\delta {\vartheta }_{j} \hfill \end{array}$$\end{document}δϑ¨i(t)=−γδϑ°i(t)−∑j=1,j≠iNAijcos(θi0−θj0)(δϑi−δϑj)=−γδϑ°i(t)−∑j=1,j≠iNAij′(δϑi−δϑj)=−γδϑ°i(t)−∑j=1NLij′δϑji = 1, . . . , N, where γ > 0, A = [Aij] is the original adjacency matrix, i.e., Aij = Aji = 1 (0) if there is (is not) a transmission line between nodes i and j, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$A{\prime}=[{A}_{ij}^{{\prime} }]$$\end{document}A′=[Aij′] is the weighted adjacency matrix, with entries \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${A}_{ij}^{{\prime} }={A}_{ij}\cos ({\theta }_{i}^{0}-{\theta }_{j}^{0})$$\end{document}Aij′=Aijcos(θi0−θj0), and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${L}^{{\prime} }=[{L}_{ij}^{{\prime} }]$$\end{document}L′=[Lij′] is the associated Laplacian matrix, with entries \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${L}_{ij}^{{\prime} }=({\delta }_{ij}{\sum }_{j}{A}_{ij}^{{\prime} }-{A}_{ij}^{{\prime} })$$\end{document}Lij′=(δij∑jAij′−Aij′). We proceed under the assumption that, prior to the intervention of the intruder, the differences \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\theta }_{i}^{0}-{\theta }_{j}^{0}$$\end{document}θi0−θj0 are small, so that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${A}_{ij}\prime > 0$$\end{document}Aij′>0 iff Aij = 1, for which the Laplacian matrix \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${L}^{{\prime} }$$\end{document}L′ is proper. By diagonalizing the Laplacian matrix \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${L}^{{\prime} }$$\end{document}L′, the last line of Eq. (67) can be transformed into the following independent equations, 68\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\ddot{y}}_{k}(t)=-\gamma {\dot{y}}_{k}(t)-{\lambda }_{k}^{{\prime} }{y}_{k}(t),$$\end{document}y¨k(t)=−γy°k(t)−λk′yk(t),k = 1, . . , N, where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\lambda }_{k}^{{\prime} }$$\end{document}λk′, k = 1, . . , N, are the eigenvalues of the matrix \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${L}^{{\prime} }$$\end{document}L′. By construction, there is one eigenvalue \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\lambda }_{k}^{{\prime} }=0$$\end{document}λk′=0, which corresponds to marginal stability of the synchronous operating state \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\theta }_{i}^{*}={\omega }_{s}t+{\theta }_{i}^{0}$$\end{document}θi*=ωst+θi0. Transverse stability is determined by the remaining eigenvalues of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${L}^{{\prime} }$$\end{document}L′, as we explain below. In the case that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\lambda }_{k}^{{\prime} }$$\end{document}λk′ is real, Eq. (68) is: (i) stable for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\lambda }_{k}\prime > 0$$\end{document}λk′>0, (ii) unstable for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\lambda }_{k}\prime < 0$$\end{document}λk′<0, and (iii) marginally stable for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\lambda }_{k}\prime=0$$\end{document}λk′=0. A more interesting case is for a complex eigenvalue of the Laplacian \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\lambda }_{k}\prime=\alpha+j\beta$$\end{document}λk′=α+jβ, for which the characteristic equation is, 69\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${r}^{2}+\gamma r+(\alpha+j\beta )=0,$$\end{document}r2+γr+(α+jβ)=0, where here r is a complex number and we recall that γ is real and positive. The largest real part root of Eq. (69) is 70\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$-\frac{\gamma }{2}+\frac{1}{2}\sqrt{\frac{| D|+{\gamma }^{2}-4\alpha }{2}},$$\end{document}−γ2+12∣D∣+γ2−4α2, where the modulus of the complex discriminant \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$| D|=\sqrt{{({\gamma }^{2}-4\alpha )}^{2}+16{\beta }^{2}}$$\end{document}∣D∣=(γ2−4α)2+16β2. Eq. (70) is negative if 71\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\beta }^{2} < {\gamma }^{2}\alpha .$$\end{document}β2<γ2α. For stability of the synchronous operating state, criterion (71) needs to be satisfied for all the eigenvalues \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\lambda }_{k}\prime=\alpha+j\beta$$\end{document}λk′=α+jβ of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${L}\prime$$\end{document}L′ (with the exception of the one zero eigenvalue.) It is easy to see that (71) is never satisfied for α < 0. We thus conclude that a sufficient condition for the synchronous operating state to be unstable is that at least one of the eigenvalues of the matrix \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${L}^{{\prime} }$$\end{document}L′ has negative real part (however, instability is also possible when all the eigenvalues of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${L}^{{\prime} }$$\end{document}L′ have negative or zero real part.) Asymptotic Stability Analysis for the Case of Formation Control Dynamics In the case of Eq. (15), the dynamics is linear, and stability depends uniquely on the spectrum of the matrix F(L). In the case considered in this paper that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F(L)={I}_{N}-\exp (-3L)$$\end{document}F(L)=IN−exp(−3L), each eigenvalue of the matrix F(L) is equal to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mu }_{k}=1-\exp (-3{\lambda }_{k})$$\end{document}μk=1−exp(−3λk), where λk is an eigenvalue of L, k = 1, . . , N. It follows that the transformation that maps λk into μk preserves the origin and the sign of the real part of the eigenvalues. Specifically, 72\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\lambda }_{k}=0\iff {\mu }_{k}=0,$$\end{document}λk=0⇔μk=0, and 73\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{\rm{sgn}}}}\left(\Re ({\mu }_{k})\right)={{{\rm{sgn}}}}\left(\Re ({\lambda }_{k})\right),\qquad k=1,\ldots,N,$$\end{document}sgnℜ(μk)=sgnℜ(λk),k=1,…,N, where with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{{\rm{sgn}}}}(x)$$\end{document}sgn(x) we indicate the sign of x. We conclude that if the Laplacian matrix L is (is not) proper, the formation control state is stable (unstable.) Asymptotic stability analysis for the case of the Kuramoto dynamics We fix the adjacency matrix A and linearize Eq. (16) about the phase locked state \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\theta }_{i}^{*}={\omega }_{s}t+{\theta }_{i}^{0}$$\end{document}θi*=ωst+θi0, 74\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\delta {\dot{\vartheta }}_{i}(t)= -\frac{1}{N+1}{\sum }_{j=1,j\ne i}^{N+1}{A}_{ij}\cos ({\theta }_{i}^{0}-{\theta }_{j}^{0})(\delta {\vartheta }_{i}-\delta {\vartheta }_{j})\\= -\frac{1}{N+1}{\sum }_{j=1,j\ne i}^{N+1}{A}_{ij}^{{\prime} }(\delta {\vartheta }_{i}-\delta {\vartheta }_{j})\\= -\frac{1}{N+1}{\sum }_{j=1,j\ne i}^{N+1}{L}_{ij}^{{\prime} }\delta {\vartheta }_{j}$$\end{document}δϑ°i(t)=−1N+1∑j=1,j≠iN+1Aijcos(θi0−θj0)(δϑi−δϑj)=−1N+1∑j=1,j≠iN+1Aij′(δϑi−δϑj)=−1N+1∑j=1,j≠iN+1Lij′δϑji = 1, . . . , N, where A = [Aij] is the fixed adjacency matrix defined in Eq. (17) either before or after the attack, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$A{\prime}=[{A}_{ij}^{{\prime} }]$$\end{document}A′=[Aij′] is the weighted adjacency matrix, with entries \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${A}_{ij}^{{\prime} }={A}_{ij}\cos ({\theta }_{i}^{0}-{\theta }_{j}^{0})$$\end{document}Aij′=Aijcos(θi0−θj0), and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${L}^{{\prime} }=[{L}_{ij}^{{\prime} }]$$\end{document}L′=[Lij′] is the associated Laplacian matrix, with entries \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${L}_{ij}^{{\prime} }=({\delta }_{ij}{\sum }_{j}{A}_{ij}^{{\prime} }-{A}_{ij}^{{\prime} })$$\end{document}Lij′=(δij∑jAij′−Aij′). We proceed under the assumption that, prior to the intervention of the intruder, the differences \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\theta }_{i}^{0}-{\theta }_{j}^{0}$$\end{document}θi0−θj0 are small, so that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${A}_{ij}\prime > 0$$\end{document}Aij′>0 iff Aij = 1, for which the Laplacian matrix \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${L}^{{\prime} }$$\end{document}L′ is proper. By diagonalizing the Laplacian matrix \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${L}^{{\prime} }$$\end{document}L′, the last line of Eq. (74) can be transformed as follows, 75\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\dot{y}}_{k}=-{\lambda }_{k}^{{\prime} }{y}_{k},$$\end{document}y°k=−λk′yk,k = 1, . . , N, where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\lambda }_{k}^{{\prime} }$$\end{document}λk′, k = 1, . . , N, are the eigenvalues of the matrix \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${L}^{{\prime} }$$\end{document}L′. Equation (75) is stable if the real part of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\lambda {\prime}$$\end{document}λ′ is positive, unstable if it is negative, and marginally stable if \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\lambda {\prime}=0$$\end{document}λ′=0. By construction, there is one eigenvalue \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\lambda }_{k}^{{\prime} }=0$$\end{document}λk′=0, which corresponds to marginal stability of the phase locked state \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\theta }_{i}^{*}={\omega }_{s}t+{\theta }_{i}^{0}$$\end{document}θi*=ωst+θi0. Transverse stability is achieved if all the other eigenvalues of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${L}^{{\prime} }$$\end{document}L′ have positive real part. We conclude that a sufficient condition for the phase-locked state to become unstable is that at least one of the eigenvalues of the matrix \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${L}^{{\prime} }$$\end{document}L′ has a negative real part. Reproducibility code description The MATLAB code used to generate Fig. 5B performs the following steps. First, the adjacency matrix A is loaded, and the graph Laplacian matrix L is constructed. For each selected node i, an attack vector b is defined with bi = − c and all other entries equal to zero, with c = 1 as the budget for the attack. The unidirectional augmented Laplacian after the attack is then constructed as in Eq. (5). The simulation uses the original Laplacian before the attack time ts = 4s and switches to the augmented Laplacian for t ≥ ts. A network of coupled Lorenz oscillators is then simulated using MATLAB’s ODE solver. The norm of the transverse perturbations ∥δX(t)∥ is evaluated as in Eq. (13). Finally, the code plots ∥δX(t)∥ in time for different attacked nodes and saves a figure similar to Fig. 5B. Supplementary information Supplementary Information Transparent Peer Review file Supplementary Information Transparent Peer Review file