Eur. Phys. J. B 76, 643-652 (2010)
https://doi.org/10.1140/epjb/e2010-00219-x

Influence of assortativity and degree-preserving rewiring on the spectra of networks

¹ Delft University of Technology, Faculty of Electrical Engineering, Mathematics and Computer Science, 2628 CD Delft, The Netherlands
² Northeastern University, College of Information Science and Engineering, 110004 Shenyang, China

Corresponding author: ^a h.wang@tudelft.nl

Received: 4 May 2010
Published online: 2 July 2010

Abstract

Newman's measure for (dis)assortativity, the linear degree correlation coefficient ρ_D, is reformulated in terms of the total number N_k of walks in the graph with k hops. This reformulation allows us to derive a new formula from which a degree-preserving rewiring algorithm is deduced, that, in each rewiring step, either increases or decreases ρ_D conform our desired objective. Spectral metrics (eigenvalues of graph-related matrices), especially, the largest eigenvalue λ₁ of the adjacency matrix and the algebraic connectivity μ_N-1 (second-smallest eigenvalue of the Laplacian) are powerful characterizers of dynamic processes on networks such as virus spreading and synchronization processes. We present various lower bounds for the largest eigenvalue λ₁ of the adjacency matrix and we show, apart from some classes of graphs such as regular graphs or bipartite graphs, that the lower bounds for λ₁ increase with ρ_D. A new upper bound for the algebraic connectivity μ_N-1 decreases with ρ_D. Applying the degree-preserving rewiring algorithm to various real-world networks illustrates that (a) assortative degree-preserving rewiring increases λ₁, but decreases μ_N-1, even leading to disconnectivity of the networks in many disjoint clusters and that (b) disassortative degree-preserving rewiring decreases λ₁, but increases the algebraic connectivity, at least in the initial rewirings.