Abstract We examine two greedy heuristics — wiring and rewiring — for constructing maximum assortative graphs over all simple connected graphs with a target degree sequence. Counterexamples show that natural greedy rewiring heuristics do not necessarily return a maximum assortative graph, even though it is known that the meta-graph of all simple connected graphs with given degree is connected under rewiring. Counterexamples show an elegant greedy graph wiring heuristic from the literature may fail to achieve the target degree sequence or may fail to wire a maximally assortative graph.
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. 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 ?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. A network is said to show assortative mixing if the nodes in the network that have many connections tend to be connected to other nodes with many connections. Here we measure mixing patterns in a variety of networks and find that social networks are mostly assortatively mixed, but that technological and biological networks tend to be disassortative. We propose a model of an assortatively mixed network, which we study both analytically and numerically. Within this model we find that networks percolate more easily if they are assortative and that they are also more robust to vertex removal.  Represented as graphs, real networks are intricate combinations of order and disorder. Fixing some of the structural properties of network models to their values observed in real networks, many other properties appear as statistical consequences of these fixed observables, plus randomness in other respects. Here we employ the dk-series, a complete set of basic characteristics of the network structure, to study the statistical dependencies between different network properties. We consider six real networks—the Internet, US airport network, human protein interactions, technosocial web of trust, English word network, and an fMRI map of the human brain—and find that many important local and global structural properties of these networks are closely reproduced by dk-random graphs whose degree distributions, degree correlations and clustering are as in the corresponding real network. We discuss important conceptual, methodological, and practical implications of this evaluation of network randomness, and release software to generate dk-random graphs.