generally, how does the robustness of the network with respect to its spectral properties depend on the network structure, and can it be used to classify networks, simi- larly to the existing spectral classification [21]? How can we appropriately measure the “smallness” of perturba- tion B to predict the accuracy? It is also important to extend our method to the case of degenerate dominant eigenvalues, which may arise when the network evolved under constraints or under pressure to optimize its func- tions [28, 29]. Our results have several potential applications for large networks whose performance depends on their spectral properties. The approximation schemes may be used in a damage control strategy for such networks, in which sudden structural damage that cannot be immediately fixed, such as the removal of multiple edges or nodes, is compensated by changes in other parts of the network (see Ref. [30] for an example of such a compensatory perturbation in a different context). They may also be used to develop gradient-descent-like algorithms to solve the problem of designing networks that satisfy specific spectral (and thus dynamical) properties [31–33], or to develop efficient updating schemes for spectrum-based statistics of evolving networks, similar to those for lo- cal statistics reported in Ref. [12]. The ranking of sub- graphs, or motifs, according to the spectral impact in a given network and for a selected eigenvalue (not neces- sarily the largest) gives rise to interesting questions: how does this ranking depend on the subgraph, the choice of the eigenvalue, and local and global properties of the net- work? Our improved formula reflects the fact that there is a nonlinear effect: the SI of the union of two subgraphs is not simply the sum of their individual SI. How does this nonlinear effect correlate with topological structures such as communities? With the tools developed in this paper, we wish to tackle some of the above open problems and applications in our future work. In this paper, we have introduced the concept of spec- tral impact of an arbitrary link modification in a network as the relative change in the largest eigenvalue of the ad- jacency matrix induced by the modification. Based on the standard perturbation method and an approxima- tion for the second order term, we obtained an improved approximation formulae for the spectral impact that re- quires only the most dominant eigenvalue of the original network and its left and right eigenvectors. Using the Erd¨ os-R´ enyi random graph, as well as real-world exam- ples of large complex networks from biological, social, and technological applications, we confirmed the accu- racy of the formulae for the addition and/or removal of nodes, links, and triangles. We have also shown that the first iteration of a local approximation scheme based on the power method is equivalent to using the node (or subgraph) degree for ranking, and that further iterations quickly improve the accuracy by incorporating the con- nectivity structure of larger neighborhood of the node (or subgraph). The analysis leading to the approxima- tion formulae readily applies to the spectrum of other relevant matrices associated with the network, such as the Laplacian matrix treated briefly in this paper and the biased adjacency matrix studied in Ref. [27]. Some problems on the approximation schemes still re- main open. How does the network topological structures, such as the small-world, scale-free, and modular struc- tures, affect the accuracy of the approximations? More A.M. gratefully acknowledges the partial support of the MAE Department through an instructor’s assis- tantship. J.S. has been supported by the ARO grant 51950-MA. The authors would like to thank D. ben- Avraham, A. Alhakim, E. M. Bollt, and J. D. Skufca for numerous discussions. Similarly to the formula for the dominant eigenvalue of A , the above equations can be adopted to develop strate- gies for targeting the network evolution towards some desired state, for example, to enhance (or weaken) the network synchronizability. Our formalism can also be extended to other spectral quantities. Combining the two equations above and neglecting terms containing more than one Δ (either Δ µ$_{2}$ or Δ µ$_{n}$ ) the change in the eigenratio r = µ$_{2}$/µ$_{n}$ is predicted by and 8 Δ µ$_{n}$ ≈ ∑ i<j b$_{ij}$ ( y$_{i}$ − y$_{j}$ ) $^{2}$. (36) Δ r ≈ 1 µ 2 n ∑ i<j b$_{ij}$ [ µ$_{n}$ ( x$_{i}$ − x$_{j}$ ) 2 − µ$_{2}$ ( y$_{i}$ − y$_{j}$ ) $^{2}$] . (37) VI. SUMMARY AND CONCLUSIONS Acknowledgments [7] J. M. Kleinberg, J. ACM 46 , 604 (1999). [6] E. Estrada and J. A. Rodr´ıguez-Vel´ azquez, Phys. Rev. E 71 , 056103 (2005). [5] S. N. Dorogovtsev, A. V. Goltsev, and J. F. F. Mendes, Rev. Mod. Phys. 80 , 1275 (2008). [4] M. E. J. Newman, SIAM Rev. 45 , 167 (2003). [3] R. Albert and A.-L. Barab´ asi, Rev. Mod. Phys. 74 (2002). [2] A.-L. Barab´ asi and R. Albert, Science 286 , 509 (1999). [1] D. Watts and S. Strogatz, Nature 393 , 440 (1998).