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 firstname.lastname@example.org - b email@example.com - c firstname.lastname@example.org
Revised: 29 April 2011
Published online: 12 September 2011
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(Gc) of its complement Gc. Both ρD(G) and ρD(Gc) 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 Gp(N), its complementary graph Gpc(N) = G1-p(N) follows a binomial degree distribution as in the Erdős-Rényi random graphs G1-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(Gc)–ρmin(Gc) 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.
© EDP Sciences, Società Italiana di Fisica, Springer-Verlag, 2011