Influence of assortativity and degree-preserving rewiring on the spectra of networks |
| |
Authors: | P Van Mieghem H Wang X Ge S Tang F A Kuipers |
| |
Institution: | 1. Delft University of Technology, Faculty of
Electrical Engineering, Mathematics and Computer Science, 2628 CD, Delft, The Netherlands 2. Northeastern
University, College of Information Science and Engineering, 110004, Shenyang, China
|
| |
Abstract: | Newman’s measure for (dis)assortativity, the linear degree correlation coefficient $\rho _{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 $\rho _{D}$ conform our desired objective. Spectral metrics (eigenvalues of graph-related matrices), especially, the largest eigenvalue $\lambda _{1}$ of the adjacency matrix and the algebraic connectivity $\mu _{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 $\lambda _{1}$ 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 $\lambda _{1}$ increase with $\rho _{D}$ . A new upper bound for the algebraic connectivity $\mu _{N-1}$ decreases with $\rho _{D}$ . Applying the degree-preserving rewiring algorithm to various real-world networks illustrates that (a) assortative degree-preserving rewiring increases $\lambda _{1}$ , but decreases $\mu _{N-1}$ , even leading to disconnectivity of the networks in many disjoint clusters and that (b) disassortative degree-preserving rewiring decreases $\lambda _{1}$ , but increases the algebraic connectivity, at least in the initial rewirings. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|