D. Removing a node Removing a node k in a graph corresponds to remov- ing all edges touching it. In this case, the entries of B are b$_{ij}$ = − a$_{ij}$ ( δ$_{ik}$ + δ$_{jk}$ − δ$_{ik}$δ$_{jk}$ ) and the first order ap- proximation reads $^{a}$The data was retrieved from P. Tsaparas’ web- page on data sets and codes for complex networks, at http://www.cs.helsinki.fi/u/tsaparas/MACN2006/data-code.html . while the second order one yields In the case that there is no self-loop connecting node k with itself, the above formulae simplify to and The summation term in the last equation represents an improvement over the previous result, Eq. (3). If, furthermore, the network is undirected and un- weighted, first and second order approximations become and The last two equations show well that, in the case of removing a node, first and second order approxima- tions yield rather different results, with the estimate from Eq. (27) more than double that from Eq. (28). This dif- ference comes from the fact that, in the case of removing node k , the k -th component of the new dominant eigen- vector becomes zero, regardless of its previous value, and thus the change in u and v is not negligible. where d out k ≡ ∑ n i =1 a$_{ki}$ is the out-degree of vertex k . The impact on λ of the removal of various subgraphs of G$_{1}$ is analyzed next: the results from the first and second order approximations are plotted versus the ac- tual SI. In Fig. 1(b), the removal of edges is considered; the maximum reduction in λ is about 0.1% and it is sat- isfactorily predicted by both the first and second order formulae: the former has a tendency of overestimating the change, while the latter is more accurate. As ex- pected, there are edges that have a greater impact on λ than others. In particular, the impact of edge ( i, j ) is dictated by the components v$_{i}$ and v$_{j}$ of v , as given in Eqs. (21) and (22). The effect of removing a simple motif is shown in Fig. 1(c), where the 171 triangles occurring in G$_{1}$ are individually removed. The observed Δ λ is higher in this case, though the approximations are still satis- factory. Figure 1(d) investigates the removal of nodes, comparing Eqs. (27), (28) and (3): while the first order approximation is off by a factor of about 2, the second order formula with the d$_{k}$/λ 2 term is the most accurate. Note that for both the first and second order estimates the plots are almost monotonic, indicating that the rela- tive ranking of nodes, edges, and triangles defined by the SI are accurately estimated by these formulae. Indeed, for a randomly chosen pair of nodes or edges, the esti- mate is correct with probability close to one (Table II). In this section, the accuracy of various approximations are assessed using both synthetic and real-world graphs. The true dominant eigenvalue and corresponding eigen- vector are estimated in double precision using the MAT- LAB function eigs [17] and compared to the estimates obtained by implementing our approximation formulae. As an example of artificial networks, the Erd¨ os-R´ enyi random graph [18] is used, with n = 1000 nodes and the probability of connection p = 0 . 01. The particular real- ization used is labelled G$_{1}$ for convenience and has 5004 undirected links, without self-loops. The largest degree is d$_{max}$ = 20, the minimum is d$_{min}$ = 2, and the av- erage is d$_{mean}$ = 10 . 01. The largest three eigenvalues (in magnitude) of the corresponding adjacency matrix are computed to be λ = 11 . 0741, λ$_{2}$ = − 6 . 53518, and λ$_{3}$ = 6 . 50196. The components of the eigenvector v are shown in increasing order in Fig. 1(a). We also analyze three real-world networks, which we refer to as G$_{2}$ , G$_{3}$ , and G$_{4}$ for convenience. The basic properties of these net- works are reported in Table I, along with the pertinent references. G$_{2}$ is a biological example, G$_{3}$ is a social inter- action network, while G$_{4}$ can be regarded as an instance having both an engineering and social character. ˆ I$_{k}$ = ( − 1 + d out k λ 2 ) v 2 $_{k}$, (28) ˆ I$_{k}$ = − 2 v 2 k (27) ˆ I$_{k}$ = ( − 1 + 1 λ 2 n ∑ i =1 a$_{ik}$a$_{ki}$ ) u$_{k}$v$_{k}$ u $^{T}$v . (26) ˆ I$_{k}$ = − 2 u$_{k}$v$_{k}$ u $^{T}$v (25) ˆ I$_{k}$ = ( − 1 + a$_{kk}$ λ − a 2 kk λ 2 + 1 λ 2 n ∑ i =1 a$_{ik}$a$_{ki}$ ) u$_{k}$v$_{k}$ u $^{T}$v . (24) ˆ I$_{k}$ = ( − 2 + a$_{kk}$ λ ) u$_{k}$v$_{k}$ u $^{T}$v , (23) TABLE I: Examples of real world networks. G 2 , yeast protein interaction network [19] 2361 vertices, 13828 edges d$_{min}$ = 1, d$_{mean}$ = 5 . 86, d$_{max}$ = 65 λ = 19 . 4861, λ 2 = 16 . 1340, λ 3 = 14 . 3339 G 3 , network of e-mail interchanges [20] 1133 vertices, 5451 edges d$_{min}$ = 1, d$_{mean}$ = 9 . 62, d$_{max}$ = 71 λ = 41 . 4940, λ 2 = 33 . 9272, λ 3 = 30 . 0687 G 4 , US power grid a 4941 vertices, 6594 edges d$_{min}$ = 1, d$_{mean}$ = 2 . 67, d$_{max}$ = 19 λ = 7 . 4831, λ 2 = 6 . 6092, λ 3 = 5 . 5728 4 III. APPLICATIONS