Logo NGI
nl
en
Zoeken

infrabase >

publicaties >

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

 
Titel
Influence of Assortativity and Degree-preserving Rewiring on the Spectra of Networks
Type
artikel vakblad
Referentie

Van Mieghem, Piet; HuijuanWang; Xin Ge; Siyu Tang and Fernando Kuipers: Influence of Assortativity and Degree-preserving Rewiring on the Spectra of Networks, pp. pp. 643-652. In: European Physical Journal B, vol. 76, no. 4, 2010.

Auteurs
Fernando Kuipers
 
Piet van Mieghem
Document
Beschrijving

Newman’s measure for (dis)assortativity, the linear degree correlation coefficient ?D, is reformulated in terms of the total number Nk 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 ?1 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 ?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 ?1 increase with ?D. An 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 ?1, but decreases ?N−1, even leading to disconnectivity of the networks in many disjoint clusters and that (b) disassortative degree-preserving rewiring decreases ?1, but increases the algebraic connectivity, at least in the initial rewirings.

Projecten
Robustness and Survivability of Complex Networks

Logo NGI

Bouwcampus
Van der Burghweg 1
2628 CS Delft
secretariaat@nginfra.nl
telefoon: 015 303 0900

© 2016 Next Generation Infrastructures