content_image/438559.jpg content_image/438560.jpg content_image/438556.jpg content_image/438547.jpg content_image/438557.jpg content_image/438558.jpg
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. 

## V. PERTURBATION OF THE GRAPH LAPLACIAN 

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]. 

<img src='content_image/438559.jpg'>

<img src='content_image/438560.jpg'>

<img src='content_image/438556.jpg'>

<img src='content_image/438547.jpg'>

Denote by x and y the normalized eigenvectors related to µ$_{2}$ and µ$_{n}$ , respectively, 

<img src='content_image/438557.jpg'>

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 

<img src='content_image/438558.jpg'>

