by the perturbation, and thus a few steps (one or two) of the power method already give a very accurate ap- proximation, as we shall see in the next section. This, however, is not the case when the dominant eigenvalue λ is nearly degenerate, in which case the convergence rate of the power method is ∣ λ$_{2}$ λ ∣ ≈ 1, where λ$_{2}$ is the sec- ond largest eigenvalue in absolute value. More precisely, the accuracy of our approximation is related to the spec- tral gaps through the perturbation formula, which, for undirected networks, takes the form [36] When the changes are limited to a small number of links, we have a clear computational advantage of having highly sparse matrix B . Also, including changes in the eigenvector does not imply much computational burden. In fact, the extra computational cost of using Eq. (14) in- stead of Eq. (13) amounts to computing the extra vector u $^{T}$B and projecting it onto Bv [37]. Adding weight b$_{ij}$ to directional edge ( i, j ) of a graph [38] corresponds to changing the adjacency matrix from A to A + B$_{ij}$ , where B$_{ij}$ is an n × n matrix containing all zeros except for the ( i, j ) entry b$_{ij}$ . The spectral impact I$_{B}$$_{ij}$ can be approximated, using Eq. (15), as where λ$_{i}$ and v ( i ≥ 2) are the non-dominant eigenval- ues and corresponding eigenvectors of A . When λ$_{1}$ ≈ λ$_{2}$ , the second term becomes large, indicating that λ is highly sensitive to perturbations. Most of the interesting problems in the context of net- works involve discrete changes, where A becomes A + B , and the nonzero entries of B are finite and usually of the same order of magnitude as the nonzero entries of A . If, however, the modifications are limited to a small num- ber of links in a large network, then ‖ B ‖ 2 ≪ ‖ A ‖ $_{2}$, and the perturbation results (5) and (6) would be valid with ϵC replaced by B . The other approximations we have made are also likely to be valid, and this is supported by the fact that Eq. (12) improves significantly over Eq. (5) for the example networks discussed in Section III. Equa- tions (5) and (12) then become and our approximation schemes for the spectral impact I$_{B}$ for small but finite modifications are Equation (15) is linear in B , and therefore the change can be decomposed into the sum of elementary changes, as B = ∑ $_{i}$B$_{i}$ , where B$_{i}$ can represent, for example, a mod- ification of a single edge. The corresponding first order approximation for the SI is obtained from the individ- ual contributions, as ˆ I$_{B}$ = ∑ i ˆ I$_{B}$$_{i}$ . On the other hand, Eq. (16) has a linear and a quadratic dependence on B and linear superposition cannot in general be used. How- ever, if all the products of elementary changes B$_{i}$B$_{j}$ are zero matrices (for example, if B$_{i}$ ’s represent the discon- nected components of the subgraph), then ˆ I$_{B}$ = ∑ i ˆ I$_{B}$$_{i}$ . Note that Eq. (22) always introduces a non-negative cor- rection to the first order approximation for modifications to undirected networks. and In this case Eq. (20) can have nonzero correction term for modification of weights on an edge other than a self loop. For undirected networks, modification must be bidirec- tional and symmetric ( b$_{ij}$ = b$_{ji}$ ), and the formulae be- come and If the change is introduced bidirectionally , that is, b$_{ij}$ is added to the weight of edge ( i, j ), and b$_{ji}$ to edge ( j, i ), then the first and second order approximations to the SI become where δ$_{ij}$ is the Kronecker delta. The second order approximation (16) introduces a cor- rection only if a modification on a self-loop is introduced, as ( B $^{2}$)$_{ij}$ is zero otherwise. Indeed, I$_{B}$$_{ij}$ can be approxi- mated at the second order as This is equivalent to Eq. (2), in the case b$_{ij}$ = − a$_{ij}$ . Δ λ = ϵv $^{T}$Cv + ϵ 2 n ∑ i =2 ( v ( i $^{)}$Cv ) 2 λ − λ$_{i}$ + o ( ϵ $^{2}$) , ( i ) ˆ I$_{B}$$_{ij}$ = b$_{ij}$u$_{i}$v$_{j}$ λu $^{T}$v . (17) ˆ I$_{B}$$_{ij}$ = b$_{ij}$u$_{i}$v$_{j}$ λu $^{T}$v (1 + δ$_{ij}$ b$_{ii}$ λ ) , (18) ˆ I$_{B}$$_{ij,ji}$ = b$_{ij}$u$_{i}$v$_{j}$ + b$_{ji}$u$_{j}$v$_{i}$ λu $^{T}$v (19) ˆ I$_{B}$$_{ij,ji}$ = b$_{ij}$u$_{i}$v$_{j}$ + b$_{ji}$u$_{j}$v$_{i}$ λu $^{T}$v + b$_{ij}$b$_{ji}$ ( u$_{i}$v$_{i}$ + u$_{j}$v$_{j}$ ) λ $^{2}$u $^{T}$v . (20) Δ λ ≈ Δ$_{1}$ = u $^{T}$Bv u $^{T}$v (13) Δ λ ≈ Δ$_{1}$ + Δ$_{2}$ ≈ u $^{T}$Bv u $^{T}$v + 1 λ u $^{T}$B $^{2}$v u $^{T}$v (14) ˆ I$_{B}$ = 1 λ u $^{T}$Bv u $^{T}$v (15) ˆ I$_{B}$ = 1 λ u $^{T}$B ( v + Bv/λ ) u $^{T}$v . (16) ˆ I$_{B}$$_{ij}$ = 2 b$_{ij}$v$_{i}$v$_{j}$ λ (21) ˆ I$_{B}$$_{ij}$ = 2 b$_{ij}$v$_{i}$v$_{j}$ λ + b 2 ij ( v 2 i + v 2 j ) λ 2 . (22) C. Modifying weight on single edge B. Adding or removing an arbitrary subgraph 3