View article

Newman’s measure for (dis)assortativity, the linear degree correlation coefficient , 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 conform our desired objective. Spectral metrics (eigenvalues of graph-related matrices), especially, the largest eigenvalue of the adjacency matrix and the algebraic connectivity (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  …