Eur. Phys. J. B 83, 203-214 (2011)
https://doi.org/10.1140/epjb/e2011-20118-x

Assortativity of complementary graphs

Faculty of Electrical Engineering, Mathematics, and Computer Science, Delft University of Technology, P.O. Box 5031, 2600 GA Delft, Netherlands

Corresponding authors: ^a h.wang@tudelft.nl - ^b w.winterbach@tudelft.nl - ^c p.f.a.vanmieghem@tudelft.nl

Received: 15 February 2011
Revised: 29 April 2011
Published online: 12 September 2011

Abstract

Newman's measure for (dis)assortativity, the linear degree correlationρ_D, is widely studied although analytic insight into the assortativity of an arbitrary network remains far from well understood. In this paper, we derive the general relation (2), (3) and Theorem 1 between the assortativity ρ_D(G) of a graph G and the assortativityρ_D(G^c) of its complement G^c. Both ρ_D(G) and ρ_D(G^c) are linearly related by the degree distribution in G. When the graph G(N,p) possesses a binomial degree distribution as in the Erdős-Rényi random graphs G_p(N), its complementary graph G_p^c(N) = G_1-p(N) follows a binomial degree distribution as in the Erdős-Rényi random graphs G_1-p(N). We prove that the maximum and minimum assortativity of a class of graphs with a binomial distribution are asymptotically antisymmetric: ρ_max(N,p) = -ρ_min(N,p) for N → ∞. The general relation (3) nicely leads to (a) the relation (10) and (16) between the assortativity range ρ_max(G)–ρ_min(G) of a graph with a given degree distribution and the range ρ_max(G^c)–ρ_min(G^c) of its complementary graph and (b) new bounds (6) and (15) of the assortativity. These results together with our numerical experiments in over 30 real-world complex networks illustrate that the assortativity range ρ_max–ρ_min is generally large in sparse networks, which underlines the importance of assortativity as a network characterizer.