7 The second iteration of the power method returns in- formation about the number of connections that these neighbors have. For an undirected unweighted graph, the k th component of u (2) and v (2) is proportional to the sum of the degrees of the direct neighbors (where the same node can be counted several times, and node k itself is always included in the count). If the graph is di- rected or weighted, the proper weights need to be added and the directions of the connections considered. Subse- quent iterations provide better approximations of the k th eigenvector component, involving larger neighborhood of node k . Combing these with Eq. (15), we obtain successive ap- proximations to the SI. For edge ( i, j ) in an undirected unweighted network, for example, the first two iterations give Figure 3 shows the results of the local computation for the Erd¨ os-R´ enyi graph G$_{1}$ . Similar results can be ob- tained for the networks G$_{2}$ , G$_{3}$ , and G$_{4}$ , which allow ac- curate prediction of edge- and node-ranking, as shown in Table II. Analogously to the effect of the order of approx- imation, increasing the number of iterations for the local method improves the accuracy for all cases, except for G$_{4}$ (due to the same large fluctuation of the approximation error among different nodes). The accuracy of this local approximation also depends on the ratio | λ$_{2}$/λ | , since it dictates the convergence rate of the method. Denote by x and y the normalized eigenvectors related to µ$_{2}$ and µ$_{n}$ , respectively, Perturbation results, based on either global or local information, can analogously be derived for eigenvalues and eigenvectors associated with the graph Laplacian L , defined as L = D − A , where D is the diagonal matrix of node in-degrees. For simplicity, only connected and undirected graphs are considered, so that the associated graph Laplacians are positive-semidefinite matrices. The spectrum of L is assumed to satisfy so that µ$_{2}$ and µ$_{n}$ are non-degenerate. The second small- est eigenvalue, µ$_{2}$ , and the largest one, µ$_{n}$ , are often used to characterize properties of the underlying graph. In particular, µ$_{2}$ is known as the algebraic connectivity of the graph [24] and quantifies the connectedness of the graph ( µ$_{2}$ = 0 if the graph is disconnected). The alge- braic connectivity, as well as the eigenratio µ$_{2}$/µ$_{n}$ , are closely related to the stability of synchronized states in coupled dynamical systems [25, 26]. If an arbitrary subgraph (assumed to be symmetric and with no self loop) is added to or removed from the original graph, then the adjacency matrix changes from A to A + B . The change in µ$_{2}$ and µ$_{n}$ can then be approximated, at the first order, by FIG. 3: (Color online) Convergence of local SI approxima- tion for edge removal in the Erd¨ os-R´ enyi network G 1 . (a) The eigenvector components sorted in the increasing order of their corresponding values computed globally [red (light gray) line]. LM1 denotes the approximation by the normalized de- gree (black cross symbols), while LM2 denotes the approxi- mation by the normalized sum of the degrees of the neighbors [blue (dark gray) dots]. (b) The SI for edge removal estimated using the approximations of the eigenvector in (a), showing quick convergence to the SI computed using the globally com- puted eigenvector. The first order formula (21) was used to estimate the SI. 0 = µ$_{1}$ < µ$_{2}$ < µ$_{3}$ ≤ ... ≤ µ$_{n}$$_{−}$$_{1}$ < µ$_{n}$, (33) Lx = µ$_{2}$x, Ly = µ$_{n}$y, ‖ x ‖ 2 = ‖ y ‖ 2 = 1 . (34) Δ µ$_{2}$ ≈ ∑ i<j b$_{ij}$ ( x$_{i}$ − x$_{j}$ ) 2 (35) ˆ I (1) B$_{ij}$ ∼ d in i d out j (31) ˆ I (2) B$_{ij}$ ∼ ( n ∑ k =1 a$_{ki}$d in k )( n ∑ k =1 a$_{jk}$d out k ) . (32) V. PERTURBATION OF THE GRAPH LAPLACIAN