# Degree and Principal Eigenvectors in Complex Networks

Cong Li, Huijuan Wang, Piet Van Mieghem

► To cite this version:

Cong Li, Huijuan Wang, Piet Van Mieghem. Degree and Principal Eigenvectors in Complex Networks. 11th International Networking Conference (NETWORKING), May 2012, Prague, Czech Republic. pp.149-160, 10.1007/978-3-642-30045-5_12. hal-01531136

HAL Id: hal-01531136

https://inria.hal.science/hal-01531136

Submitted on 1 Jun 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Degree and Principal Eigenvectors in Complex Networks

Cong Li, Huijuan Wang and Piet Van Mieghem

Faculty of Electrical Engineering, Mathematics and Computer Science, Delft University of Technology, P.O Box 5031, 2600 GA Delft, The Netherlands {Cong.Li, H.Wang, P.F.A.VanMieghem}@tudelft.nl

**Abstract.** The largest eigenvalue $\lambda_1$ of the adjacency matrix powerfully characterizes dynamic processes on networks, such as virus spread and synchronization. The minimization of the spectral radius by removing a set of links (or nodes) has been shown to be an NP-complete problem. So far, the best heuristic strategy is to remove links/nodes based on the principal eigenvector corresponding to the largest eigenvalue $\lambda_1$. This motivates us to investigate properties of the principal eigenvector $x_1$ and its relation with the degree vector. (a) We illustrate and explain why the average $E[x_1]$ decreases with the linear degree correlation coefficient $\rho_D$ in a network with a given degree vector; (b) The difference between the principal eigenvector and the scaled degree vector is proved to be the smallest, when $\lambda_1 = \frac{N_2}{N_1}$, where $N_k$ is the total number of walks in the network with $k$ hops; (c) The correlation between the principal eigenvector and the degree vector decreases when the degree correlation $\rho_D$ is decreased.

**Keywords:** networks; spectral radius; principal eigenvector; degree; assortativity

## 1 Introduction

Dynamic phenomena occurring on networks are affected by the structure of networks, e.g., the absence of epidemic thresholds in large scale free networks [2][3][6], the effect of the degree correlations on the percolation of networks [8]. The largest eigenvalue $\lambda_1(A)$ of the adjacency matrix $A$, called the spectral radius of the graph, has been shown to play an important role in dynamic processes on graphs, such as SIS (susceptible-infected-susceptible) virus spread [12] and the Kuramoto type of synchronization process of coupled oscillators [11] on a given network topology. For instance, in a SIS spreading model, the epidemic threshold $\tau_c \approx \frac{1}{\lambda_1(A)}$ separates two different phases of a dynamic process on a network: if the spreading rate $\tau$ is above the threshold, the infection spreads and becomes persistent in time; where $\tau < \tau_c$, the infection dies out exponentially fast [10][12]. In the past decade, researches have focused on how topological changes, such as link (or node) removal, may alter the spectral radius. Milanese et al. [7] studied the dynamical importance of the structural perturbation by removing one node or link. Van Mieghem et al. [15] have proved that to minimize
the largest eigenvalue by removing a set of links or nodes is a NP-hard problem and have shown that the best strategy so far is based on the components of the principal eigenvector $x_1$, which underlines the importance of the principal eigenvalue in characterizing the influence of link/node removal on the spectral radius. Our main objective is to investigate the topological meaning of $x_1$, which has been rarely studied. Especially, we aim to understand the relation between $x_1$ and the degree vector/sequence<fnref n="1" /> $d$, the computationally simplest and mostly studied property of a network.

The degree correlation, also called the assortativity $\rho_D$ is computed as the linear correlation coefficient of the degree of nodes connected by a link. It describes the tendency of network nodes to connect preferentially to other nodes with either similar (when $\rho_D > 0$) or opposite (when $\rho_D < 0$) properties i.e. degree [9]. The assortativity was widely studied after it was realized that the degree distribution alone provides an insufficient characterization of complex networks. Networks with the same degree distribution may still differ significantly in various topological features. Degree-preserving rewiring [13] allows us to either increase or decrease the assortativity of a network without changing the degree of each node. The relation between the principal eigenvector and the degree vector is systematically investigated in networks with various degree distributions and degree correlations.

Section 2 illustrates the importance of the principal eigenvector in characterizing the influence of link/node removal on the spectral radius by two key theories developed in our early work and further simulations. Subsequently, we explore the properties of the principal eigenvector and the relation between the (normalized) degree vector and the principal eigenvector in networks with different degree correlation and with the degree distribution derived from the Erdős-Rényi random graphs<fnref n="2" /> [4], the Bárabasi-Albert graphs<fnref n="3" /> [1], and real-world networks (see Section 3). Our major contributions are: (a) the average of the components in the principal eigenvector $E[x_1]$ is shown and explained to decrease with the assortativity $\rho_D$; (b) the difference between the principal eigenvector and the degree vector is proved to be the smallest, when $\lambda_1 = \frac{N_2}{N_1}$, where $N_k$ is the total number of walks with $k$ hops in a network and (c) the correlation between principal eigenvector and the degree vector decreases as the assortativity $\rho_D$ is decreased. These finds provide essential inspiration on when the degree vector well approximates the principal eigenvector. Finally, we illustrate the possibility to approximate the principal eigenvector based strategy to minimize the largest

<footnote n="1">¹ The degree vector/sequence is composed of the degree of each node, following the same ordering as the principal eigenvector.</footnote>

<footnote n="2">² An Erdős-Rényi random graph can be generated from a set of $N$ nodes by randomly assigning a link with probability $p$ to each pair of nodes.</footnote>

<footnote n="3">³ A Bárabasi-Albert graph starts with $m$ nodes. At every time step, we add a new node with $m$ links that connect the new node to $m$ different nodes already present in the graph. The probability that a new node will be connected to node $i$ in step $t$ is proportional to the degree $d_i(t)$ of that node. This is referred to as preferential attachment.</footnote>
eigenvalue by removing links/nodes by its corresponding degree based strategy (see Section 4), which can be well explained by the findings in early sections.

## 2 The decrease of the spectral radius

We consider a network as a graph $G = (\mathcal{N}, \mathcal{L})$, where $\mathcal{N}$ is the set of nodes and $\mathcal{L}$ is the set of links. The number of nodes is denoted by $N = |\mathcal{N}|$ and the number of links is represented by $L = |\mathcal{L}|$. The graph $G$ can be represented by the $N \times N$ adjacency matrix $A$, consisting of elements $a_{ij}$ that are either one or zero depending on whether there is a link between nodes $i$ and $j$. The eigenvalues of the adjacency matrix are ordered as $\lambda_N \le \lambda_{N-1} \le \cdots \le \lambda_1$, where $\lambda_1$ is the spectral radius and the corresponding eigenvector $x_1$ is called the principal eigenvector. Let $\mathcal{L}_m$ (or $\mathcal{N}_m$) denote the set of the $m$ links (or nodes) that are removed from $G$, and $G_m(\mathcal{L}) = G\setminus\mathcal{L}_m$ (or $G_m(\mathcal{N}) = G\setminus\mathcal{N}_m$) is the resulting graph after the removal of $m$ links (or nodes) from $G$. We denote the adjacency matrix of $G_m(\mathcal{L})$ (or $G_m(\mathcal{N})$) by $A_m(\mathcal{L})$ (or $A_m(\mathcal{N})$), which is still a symmetric matrix.

**Theorem 1.** For any graph $G$ and graph $G_m(\mathcal{L}) = G\setminus\mathcal{L}_m$, by removing $m$ links from $G$, it holds that

$$2 \sum_{l \in \mathcal{L}_m} (w_1)_{l+} (w_1)_{l-} \le \lambda_1(A) - \lambda_1(A_m(\mathcal{L})) \le 2 \sum_{l \in \mathcal{L}_m} (x_1)_{l+} (x_1)_{l-} \quad (1)$$

where $x_1$ and $w_1$ are the principal eigenvectors of $A$ and $A_m(\mathcal{L})$ corresponding to the largest eigenvalues $\lambda_1(A)$ and $\lambda_1(A_m(\mathcal{L}))$, respectively, and where a link $l$ joins the nodes $l^+$ and $l^-$.

*Proof.* [15] □

<figure><img src="image_2.png" /></figure>

The decrease of the largest eigenvalue $\lambda_1(A) - \lambda_1(A_m(\mathcal{L}))$ tends to be larger if the upper bound $2 \sum_{l \in \mathcal{L}_m} (x_1)_{l+} (x_1)_{l-}$ is larger. This motivates the principal eigenvector strategy to minimize the largest eigenvalue: removing the set of links that maximizes $2 \sum_{l \in \mathcal{L}_m} (x_1)_{l+} (x_1)_{l-}$. Moreover, when only one link is removed, removing the link with the maximum $(x_1)_{l+} (x_1)_{l-}$, maximizes not only the upper bound of (1), but likely the lower bound as well, since $w_1$ is close to $x_1$ in this case. This eigenvector strategy performs almost optimally in this situation.

**Theorem 2.** For any graph $G$ and graph $G_m(\mathcal{N}) = G\setminus\mathcal{N}_m$, by removing $m$ nodes from $G$, it holds that

$$0 \le \lambda_1(A) - \lambda_1(A_m(\mathcal{N})) \le 2 \sum_{n \in \mathcal{N}_m} (x_1)_n^2 \lambda_1(A) - \sum_{j \in \mathcal{N}_m} \sum_{i \in \mathcal{N}_m} a_{ij}(x_1)_i (x_1)_j \quad (2)$$

where $x_1$ is the principal eigenvectors of $A$ corresponding to the largest eigenvalues $\lambda_1(A)$. In particular, if $m = 1$, then

$$0 \le \lambda_1(A) - \lambda_1(A_1(\mathcal{N})) \le 2(x_1)_n^2 \lambda_1(A) \quad (3)$$

where $n$ is the node removed.
Proof. [5]

□

Theorem 2 implies that the decrease of spectral radius by removing a node or a set of nodes is strongly related to the principal eigenvector components corresponding to the removed nodes. Motivated by Theorem 2, the eigenvector based one node removal strategy to minimize the largest eigenvalue simply removes the node with the largest principal eigenvector component $(x_1)_n$.

<figure><img src="image_3.png" /><figcaption>Fig. 1. The spectral radius of graphs by removing a link (or node) as a function of corresponding components in principal eigenvector (a), (b)in Binomial graphs,(c), (d) in power-law graphs.</figcaption></figure>

We perform further simulations to illustrate the importance of the principal eigenvector components in characterizing the influence of the link/node removal on $\lambda_1$. We deduce networks with different assortativities but with a given degree vector, which may follow a binomial or power-law degree distribution. Upon each network, we try all possible one link (or node) removal and examine the largest eigenvalue $\lambda_1(G\setminus(l))$ (or $\lambda_1(G\setminus(n))$) after removing one link (or node) as a function of $(x_1)_{l+} (x_1)_{l-}$ (or $(x_1)_n^2$) corresponding to the link (or node) removed. By the Perron-Frobenius theorem [14], all components of $x_1$ and $w_1$ are non-negative (positive if the corresponding graph is connected). Interestingly, $\lambda_1(G\setminus(l))$ (or $\lambda_1(G\setminus(n))$) decreases linearly as a function of increasing $(x_1)_{l+} (x_1)_{l-}$ (or $(x_1)_n^2$),
as shown in Fig. 1. In other words, the spectral radius will be decreased more if
the link (or node) removed has a larger $(x_1)_{l+} (x_1)_{l-}$ (or $(x_1)_n^2$).

3 Relation between the principal eigenvector and the degree vector

In view of the importance of the principal eigenvector in characterizing the in-
fluence of link/node on the spectral radius, in this section, we explore how the
average $E[x_1]$ as well the variance of $x_1$ changes with the assortativity $\rho_D$ when
the degree vector, which may follow the degree distribution of network models
or of real-world networks, remains the same. Moreover, we explore the difference
and the linear correlation coefficient between the principal eigenvector and the
degree vector, the simplest and mostly studies network metric, which as well pro-
vides important insights on under which condition the degree vector/sequence
well approximates the principal eigenvector.

3.1 Properties of the principal eigenvector

Two types of degree distributions have been so far widely studied: the bino-
mial and power-law degree distribution. The binomial degree distribution is
a characteristic of an Erdős-Rényi random graph $G_p(N)$, which has $N$ nodes
and any two nodes are connected independently with a probability $p$. Such
a random construction leads to a zero assortativity as proved in [13]. How-
ever, the class of graphs $G(N,p)$ with the same binomial degree distribution
$\Pr[D_G = k] = \binom{N-1}{k} p^k (1-p)^{N-1-k}$ as Erdős-Rényi random graphs $G_p(N)$
and obtained, for instance, by degree-preserving rewiring feature an assorta-
tivity that may vary within a wide range. The power-law degree distribution
$\Pr[D = k] = ck^{-\alpha}$, where $c = 1/\sum_{k=1}^{N-1} k^{-\alpha}$ has been widely observed in real-
world networks. Similarly, graphs with a given power-law degree distribution,
for example, generated by the Barabási-Albert power model [1] can be altered
by the degree-preserving rewiring to obtain different assortativity.

We explore the principal eigenvector components (see Figure 2) as well as
its average $E[x_1]$ (see Figure 3) in graphs with the same degree distribution
(i.e. binomial or power-law) but with different assortativities $\rho_D$ obtained by
degree-preserving rewiring. Figure 2 shows that the variance of the principal
eigenvector increases with assortativity $\rho_D$. Furthermore, as shown in Figure 3,
$E[x_1]$ decreases with the increase of assortativity $\rho_D$. Similarly, we consider a
set of 11 real-world networks. We apply degree-preserving rewiring to each real-
world network to derive network instances with different assortativity. In other
words, we derive a class of networks that possess the same degree distribution as
a real-world network but different assortativities. Interestingly, we observe the
same, $E[x_1]$ decreases with increasing assortativity (see Figure 3(b)).

The decrease of $E[x_1]$ and the increase of the variance of the principal eigen-
vector components with increasing assortativity can be qualitatively explained
<figure><img src="image_4.png" /><figcaption>**Fig. 2.** The components of the principal eigenvector in increasing order. Images (a) (linear) (b) (semilogarithmic) are binomial graphs with different assortativity. Images (c) (linear) (d) (semilogarithmic) are power-law graphs with different assortativity.</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>**Fig. 3.** The average of the components of the principal eigenvector versus the assortativity. (a) in binomial and power-law graphs (b) in network instances derived from real-world networks via degree-preserving rewirings.</figcaption></figure>
as follows. As defined, the principal eigenvector $x_1$ corresponds to the largest eigenvalue $\lambda_1$ follows

$$ \lambda_1(x_1)_j = \sum_{q=1}^{N} a_{jq}(x_1)_q, \qquad (4) $$

where $a_{jq} = 1$ if $q$ is a neighbor of node $j$, or else $a_{jq} = 0$. The $j$-th component of the principal eigenvector $(x_1)_j$ tends to be large if node $j$ has a large degree (number of neighbors) or if the components corresponding to its neighbors are large. When $\rho_D$ is large, high degree nodes prefer to link with other high degree nodes. In this case, a high degree node possesses a large number of neighbors, whose corresponding eigenvector components are again likely to be large, whereas a low degree node connects to a small number of neighbors, whose corresponding components tend to be small. Both a large variance in degree and a large assortativity $\rho_D$ contribute to a large variance $Var[x_1]$ of the principal eigenvector $x_1$. This explains why variance $Var[x_1]$ of $x_1$ increases with $\rho_D$ and with a given assortativity, the power-law graphs have a larger $Var[x_1]$ than the binomial graphs (see Figure 2). Furthermore, since $Var[X] = E[X^2] - (E[X])^2$ and $x_1^T x_1 = 1$,

$$ E[x_1] = \sqrt{\frac{1}{N} - Var[x_1]}, \qquad (5) $$

Correspondingly, both a large variance in degree and a large assortativity $\rho_D$ contribute to a small $E[x_1]$ of the principal eigenvector $x_1$. Hence, $E[x_1]$ decreases with increasing $\rho_D$ and tends to be smaller when the degree variance is larger. Moreover, considering Eq. (5), we can deduce the upper bound $E[x_1] \le \frac{1}{\sqrt{N}}$.

Figure 2 compares as well the principal eigenvector $x_1$ with the normalized degree vector $\bar{d} = \frac{d}{\sqrt{d^T d}}$ in binomial graphs and power-law graphs ($N = 500$, $L = 1984$) with different assortativities. The components of $x_1$ and $\bar{d}$ are plotted in the order of increasing magnitude. The difference between $x_1$ and $\bar{d}$ is affected by $\rho_D$, which will be further explored in the following part.

## 3.2 Relation between degree vector and principal eigenvector

In this section, we investigate the relation between the principal eigenvector and the degree vector by their difference and linear correlation coefficient. The degree vector has to be first normalized to quantify its difference with the principal eigenvector. We propose two scalings of the degree vector $\bar{d} = \frac{d}{\sqrt{d^T d}}$ and $\tilde{d} = \frac{\alpha}{\lambda_1} d$, where $\alpha$ is a constant. The corresponding difference vector between $x_1$ and the scaled degree vector is $w = x_1 - \frac{d}{\sqrt{d^T d}}$ and $y = x_1 - \frac{\alpha}{\lambda_1} d$, respectively. The overall difference can be quantified by either the relative difference $u^T w$ (or $u^T y$) or the absolute difference $w^T w$ (or $y^T y$), actually, the square sum or the sum of the components in the difference vector respectively. The first scaling of the degree vector $\bar{d} = \frac{d}{\sqrt{d^T d}}$ aims to obtain the same norm for the degree vector and the principal eigenvector: $\sqrt{d^T d} = \sqrt{x_1^T x_1} = 1$. The other $\tilde{d} = \frac{\alpha}{\lambda_1} d$ is motivated by $(x_1)_j = \frac{1}{\lambda_1} \sum_{r=1}^{N} a_{jr} (x_1)_r \le \frac{d}{\lambda_1}$ and the constant $\alpha$ is determined (see Theorem
3) as the one minimize the absolute difference $y^Ty$. Note that both linear scalings of the degree vector will not change the linear correlation coefficient between the principal eigenvector and the degree vector.

**Theorem 3.** The absolute difference $w^T w$ (or $y^Ty$) between the principal eigenvector and the degree vector is the smallest ($w^T w = 0$ or $y^Ty = 0$) when the spectral radius follows $\lambda_1 = \frac{N_2}{N_1}$, where $N_k$ is the total number of k hop walks between any two nodes which can be the same.

*Proof.* The absolute difference

$$w^T w = \left(x_1 - \frac{d}{\sqrt{d^T d}}\right)^T \left(x_1 - \frac{d}{\sqrt{d^T d}}\right) = x_1^T x_1 - 2 \frac{d^T x_1}{\sqrt{d^T d}} + \frac{d^T d}{\left(\sqrt{d^T d}\right)^2} = 2 - 2 \frac{d^T x_1}{\sqrt{d^T d}} \quad (6)$$

Moreover, the generalized form of (4) for the k-th largest eigenvalue $\lambda_k$ and the corresponding eigenvector $x_k$ follow $(x_k)_j = \frac{1}{\lambda_k} \sum_{r=1}^N a_{jr} (x_k)_r = \alpha \frac{d_j}{\lambda_k} - \frac{1}{\lambda_k} \sum_{r=1}^N a_{jr} (\alpha - (x_k)_r)$, we will determine $\alpha$ so that $y_k = x_k - \frac{\alpha}{\lambda_k} d$ has minimum norm. Hence,

$$y_k^T y_k = \left( x_k - \frac{\alpha}{\lambda_k} d \right)^T \left( x_k - \frac{\alpha}{\lambda_k} d \right) = 1 - 2 \frac{\alpha}{\lambda_k} d^T x_k + \frac{\alpha^2}{\lambda_k^2} d^T d, \quad (7)$$

is minimized with respect to $\alpha$ if $-\frac{2}{\lambda_k} d^T x_k + 2 \frac{\alpha}{\lambda_k^2} d^T d = 0$ or $\frac{\alpha}{\lambda_k} = \frac{d^T x_k}{d^T d}$. Let $y = y_1$, we obtain

$$y^T y = 1 - \frac{(d^T x_1)^2}{d^T d}, \quad (8)$$

using the $\alpha$ derived in the last step. In both Eq. (6) and Eq. (8), $w^T w = 0$ and $y^T y = 0$ if $d^T x_1 = \sqrt{d^T d}$. In other words, when the principal eigenvector is proportion to degree vector, $w = \mathbf{0}$ (or $y = \mathbf{0}$). Since $Ax_1 = \lambda_1 x_1$, $d^T x_k = \lambda_1 u^T x_1$. The condition $d^T x_1 = \sqrt{d^T d}$ implies

$$\lambda_1 u^T x_1 = \sqrt{d^T d} = \sqrt{N_2}$$

where $N_2 = d^T d$. Since $x_1 = \frac{d}{\sqrt{d^T d}}$, and $u^T d = N_1$, Lemma 3 follows. $\square$

<figure><img src="image_6.png" /></figure>

Notice that in some approximate mean-field models for virus spreading [10], $\tau_c \sim \frac{N_1}{N_2} = \frac{1}{\lambda_1}$. Furthermore, $w^T w = 0$ (or $y^T y = 0$) is a special case of $u^T y_k = 0$, when $\lambda_1 = \frac{N_2}{N_1}$.

The relative difference $w^T u = u^T x_1 - \frac{d^T u}{\sqrt{d^T d}} (y^T u)$ is zero when the absolute difference is zero. We explore the relative difference in general cases by considering the binomial graphs as an example. The sum of the principal eigenvector $u^T x_1$ and the relative difference $w^T u$ as a function of the assortativity are shown in Figure 4 to follow exactly the same trend, since the degree of each node, thus, $\frac{d^T u}{\sqrt{d^T d}}$ remains the same when we change the assortativity by degree-preserving
<figure><img src="image_7.png" /><figcaption>Fig. 4. The difference between the principal eigenvector and degree vector as a function of the assortativity $\rho_D$.</figcaption></figure>

rewiring. When the assortativity $\rho_D = 0$, the binomial graphs are actually Erdős-Rényi random graphs, for which $\lambda_1 \approx \frac{N_2}{N_1}$ when the network size is large [14]. Hence, both the absolute and relative difference are zero when the assortativity is around zero. The sum of the principal eigenvector $u^T x_1$ decreases with the assortativity $\rho_D$, as explained in Subsection 3.1.

### 3.3 Correlation between the principal eigenvector and the degree vector

Recall that so far the best strategy to minimize the spectral radius by links/nodes removal is based on the principal eigenvector. When the correlation $\rho(x_1, d)$ between the principal eigenvector and the degree vector is positively strong, we may use the degree vector instead of the principal eigenvector to determine which links/nodes to remove, which will be further illustrated in Section 4. Here, we investigate the linear correlation coefficient $\rho(x_1, d)$ between the principal eigenvector and the degree vector as a function of $\rho_D$. Linear scaling of the degree vector will not change the linear correlation coefficient. Hence, we consider the original degree vector. When the absolute difference between the principal eigenvector and the scaled degree vector is zero, the principal eigenvector is proportion to degree vector. In this case, $\rho(x_1, d) = 1$, which seldom occurs in real-world networks. A strong positive correlation, not necessarily to be one, is already interesting with respect to approximate the eigenvector strategy by the corresponding degree vector strategy in minimizing the spectral radius.

Figure 5(a) depicts that $\rho(x_1, d)$ is mostly positively strong in the Erdős-Rényi random graphs and Bárabasi-Albert graphs. However, $\rho(x_1, d)$ decreases dramatically when the assortativity is decreased, actually around the minimal assortativity. Similarly, we derive networks with different assortivities by applying degree preserving rewiring to each of the 11 real-world networks. As in Figure 5(b), We are interested in how $\rho(x_1, d)$ changes with the assortativity $\rho_D$ in real-world networks. Figure 5(b) illustrates that, the correlation $\rho(x_1, d)$ creases as the assortativity is decreased, especially around the minimal assortativity, which is the same as observed in network models. In the simulations
<figure><img src="image_8.png" /><figcaption>**Fig. 5.** The linear correlation coefficient between the degree vector and the principal eigenvector as a function of the assortativity (a) in both binomial graphs (red marks and line) and power-law graphs(blue marks and line); (b) in network instances derived from real-world networks via degree-preserving rewirings.</figcaption></figure>

of both network models and real-world networks, the most evident decrease is observed in networks with a power-law degree distribution such as the C. elegans neural network, the Gnutella 3 network and the WordAdj network.

These observations can be explained similarly as we explain the average/variance of the principal eigenvector versus assortativity in Section 3.1. In general, if a node has a large degree, its corresponding principal eigenvector component tends to be large even when the assortativity is zero, due to (4). A large positive assortativity implying large (or small) degree nodes tend to connect to other large (or small) degree nodes, further enforces a large degree node to have more likely a even larger principal eigenvector component compared to a small assortativity. Hence, a negative assortativity will weaken the correlation $\rho(x_1, d)$. Note that the correlation coefficient is not necessarily the maximum at the maximal assortativity as shown in Figure 5, because here we examine the linear correlation coefficient but not the rank correlation.

# 4 Application: degree vs. principal eigenvector strategy in minimizing the spectral radius

In this section, we illustrate the possibility to replace the principal eigenvector strategy by the degree vector in minimizing the spectral radius $\lambda_1$ via an example of node removal in power-law networks with different assortivities. As mentioned in Section 2, so far the best node removal strategy removes the node with the largest principal eigenvector component $(x_1)_j$. A widely applied strategy to minimize $\lambda_1$ by removing $m$ nodes (a) removes the set of $m$ nodes with the highest component in the principal eigenvector of the original graph. The corresponding degree vector strategy (b) removes the set of $m$ nodes with the highest degree in the original graph. We compare these two strategies in remov-
ing $m \in [1, 200]$ nodes in graphs with positive, zero and negative assortativity (see Fig. 6) but with the same power-law degree distribution as in Fig. 5(a).

<figure><img src="image_9.png" /><figcaption>**Fig. 6.** The decrease of the spectral radius by successively removing $m$ nodes in power-law networks. The square and circle dot dash lines show the decrease of the spectral radius by strategies (a) and (b) separately.</figcaption></figure>

Figure 6 shows that the decreases of $\lambda_1$ by removing nodes with strategy (a) and (b) are almost same when $\rho_D$ is large. The eigenvector strategy (a) decreases the spectral radius more thus performs better than the degree vector strategy (b) when the assortativity is small. When the assortativity is large, the degree vector is positively and strongly correlated with the principal eigenvector. In such a case, the degree vector strategy, the simplest to compute, well approximates the principal eigenvector strategy in minimizing the spectral radius.

# 5 Conclusions

The principal eigenvector is essential in characterizing the influence of link/node on the spectral radius, whereas its topological meaning is far from well understood. This work, via both theoretical analysis and systematic simulations,
contributes to the following aspects: (a) the average $E[x_1]$ (or variance) of the
principal eigenvector is shown and explained to decrease (or increase) with the
assortativity $\rho_D$; (b) the difference between the principal eigenvector and the
degree vector is proved to be the smallest, when $\lambda_1 = \frac{N_2}{N_1}$ and (c) we illustrate
and explain why the correlation between principal eigenvector and the degree
vector decreases as $\rho_D$ is decreased. In general, both a large variance (heterogene-
ity) in nodal degree and a large degree correlation (homogeneity in connection)
contribute to a large average and a small variance of the principal eigenvector
and a strong correlation between the degree and the principal eigenvector. As a
straightforward application of these finds, we illustrate that when the assorta-
tivity is large, we could approximate the well performance principal eigenvector
based strategy (to minimize $\lambda_1$ by removing links/nodes) by the corresponding
degree vector, which is the simplest network property to compute.

References

1. A.-L. Barabasi and R. Albert, *Emergency of Scaling in Random Networks*, Science **286**, 509-512, 1999.

2. M. Barthélemy, A. Barrat, R. Pastor-Satorras and A. Vespignani, *Velocity and Hierarchical Spread of Epidemic Outbreaks in Scale-Free Networks*, Phys. Rev. Lett. **92**, 178701, 2004.

3. M. Boguñá, R. Pastor-Satorras and A. Vespignani, *Absence of Epidemic Threshold in Scale-Free Networks with Degree Correlations*, Phys. Rev. Lett. **90**, 028701, 2003.

4. P. Erdös, A. Rényi, *On Random Graphs*. I, Publicationes Mathematicae **6**: 290-297, 1959.

5. C. Li, H. Wang and P. Van Mieghem, *Bounds for the spectral radius of a graph when nodes are removed*, accepted, Linear Algebra and its Applications.

6. R. M. May and A. L. Lloyd, *Infection dynamics on scale-free networks*, Phys. Rev. E **64**, 066112, 2001.

7. A. Milanese, J. Sun and T. Nishikawa, *Approximating spectral impact of structural perturbations in large networks*, Physical Review E **81**, 046112, 2010.

8. M. E. J. Newman, *Assortative Mixing in Networks*, Physic Rev. Lett. **89**, 208701, 2002.

9. M. E. J. Newman, *Mixing patterns in networks*, Phys. Rev. E **67**, 026126, 2003.

10. R. Pastor-Satorras and A. Vespignani, *Epidemic dynamics and endemic states in complex networks*, Phys. Rev. E **63**, 066117, 2001.

11. J. G. Restrepo, E. Ott and B. R. Hunt, *Onset of synchronization in large networks of coupled oscillators*. Physical Review E **71**, 036151, 1-12, 2005.

12. P. Van Mieghem, J. Omic and R.E. Kooij, *Virus spread in networks*, IEEE/ACM Transactions on Networking **17**, 1(February), pp. 1-14, 2009.

13. P. Van Mieghem, H. Wang, X. Ge, S. Tang and F.A. Kuipers, *Influence of assortativity and degree-preserving rewiring on the spectra of networks*, The European Physical journal B, pp. 643-652, 2010.

14. P. Van Mieghem, *Graph Spectra for Complex Networks*, Cambridge University Press, Cambridge, U.K., 2011.

15. P. Van Mieghem, D. Stevanović, F. Kuipers, C. Li, R. van de Bovenkamp, D. Liu and H. Wang, *Optimally decreasing the spectral radius of a graph by link removals*, Physical Review E **84**, 016101, 2011.