2 and where u$_{i}$ and v$_{i}$ denote the i -th component of the vectors u and v , respectively. In this paper, the notion of dynamical importance is extended to measure the spectral impact [34] of a struc- tural perturbation in which an arbitrary set of links are removed or added, or their weights are modified. We define the spectral impact (SI) as where A denotes the adjacency matrix of the original graph, λ | A is the corresponding spectral radius, while B is the adjacency matrix of the graph consisting of all the n nodes and the links that are removed, added, or modified. Here a positive value of I$_{B}$ corresponds to an increase in λ , and a negative value to a decrease. Note that in the case of removing a subgraph of A , the entries of B will be non-positive. In this framework, the edge and vertex importance can be treated as special cases. To enable ef- ficient estimations of the spectral impact, formulae based on the first and improved first order approximations are presented and discussed in detail. These formulae lead to the observation that the degree centrality, as a local measure, can be viewed as a first order approximation to the eigenvector centrality. The rest of the paper is organized as follows. Section II reports first and second order perturbation results to ap- proximate the SI using global information on the graph; in particular, the special cases of changing the weight on an edge and removing a node are addressed. In Sec- tion III, applications to synthetic and real-world graphs are presented. Section IV deals with estimating the SI using local information on the network. While the ma- jority of the results concerns the spectral radius of the adjacency matrix of the graph, Section V deals with an extension of our method to the graph Laplacian. Suppose a graph is modified so that its adjacency ma- trix A becomes A + ϵC . Let λ be the largest eigenvalue of A , and λ + Δ λ the largest eigenvalue of A + ϵC . The change Δ λ can be estimated, when ϵ ≪ 1, using a first- order perturbation result [13–16], as where λ $^{′}$| A denotes the derivative of λ +Δ λ as a function of ϵ , evaluated at ϵ = 0. Equation (5) shows that— at the first order—the change in the largest eigenvalue The above formulae take advantage of the fact that in many situations the eigenvector does not change much having neglected terms containing Δ u and Δ v in the de- nominator, and the product Δ u $^{T}$C Δ v in the numerator. Thus, an improved approximation for Δ λ is given by Therefore, the derivative λ $^{′}$| A + ϵC can be approximated as Similarly, it can be found that where ϵ terms in the denominator have been neglected. Thus The term λ $^{′}$| A + ϵC takes into account the change in u and v , to u +Δ u and v +Δ v , respectively. It is proposed here to estimate v +Δ v by means of one iteration of the power method [35], starting from the unperturbed eigenvector v , as Computing the second derivative term using known per- turbation results would require knowledge of all the eigenvalues and eigenvectors of A [14]. This is impracti- cal. Hence, a further approximation is introduced, as For more accurate approximation, we can use a second- order perturbation result: is obtained from the derivative λ $^{′}$| $_{A}$, which depends on both A and C but can be computed using the vectors u and v , and the matrix C . If A is symmetric, u = v and Eq. (5) is of the Rayleigh quotient form [16]. ¯ I$_{k}$ = u$_{k}$v$_{k}$ u $^{T}$v , (3) I$_{B}$ ≡ λ | A + B − λ | A λ | A , (4) Δ λ ≈ Δ$_{1}$ + Δ$_{2}$ = ϵ λ $^{′}$| A + ϵ 2 2 λ $^{′′}$| $_{A}$. (6) λ $^{′′}$| A ≈ λ $^{′}$| A + ϵC − λ $^{′}$| A ϵ . (7) v + Δ v ≈ ( A + ϵC ) v ‖ ( A + ϵC ) v ‖ 2 = λv + ϵCv ‖ λv + ϵCv ‖ 2 = = λv + ϵCv √$_{λ}$ $^{2}$v $^{T}$v + 2 ϵλv $^{T}$Cv + ϵ $^{2}$v $^{T}$C$^{T}$Cv ≈ λv + ϵCv λ , (8) Δ v ≈ ϵ λ Cv. (9) Δ u ≈ ϵ λ C $^{T}$u. (10) λ $^{′}$| A + ϵC = ( u + Δ u ) T C ( v + Δ v ) ( u + Δ u ) T ( v + Δ v ) ≈ ≈ u $^{T}$Cv u $^{T}$v + u $^{T}$C Δ v u $^{T}$v + Δ u $^{T}$Cv u $^{T}$v ≈ ≈ u $^{T}$Cv u $^{T}$v + 2 ϵ λ u $^{T}$CCv u $^{T}$v , (11) Δ λ ≈ Δ$_{1}$ + Δ$_{2}$ ≈ u $^{T}$ϵCv u $^{T}$v + 1 λ u $^{T}$ϵ $^{2}$C$^{2}$v u $^{T}$v . (12) Δ λ ≈ Δ$_{1}$ = ϵ λ $^{′}$| A = u $^{T}$ϵCv u $^{T}$v , (5) II. APPROXIMATING SPECTRAL IMPACT USING GLOBAL INFORMATION A. Perturbation results