首页 | 本学科首页   官方微博 | 高级检索  
     


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
Affiliation: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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号