Graph Assortativity

Graph assortativity, also called assortative mixing, is the tendency of adjacent vertices in a graph to have similar attributes. The attributes may be numerical or categorical. For an undirected graph with edges, let be its adjacency matrix, let be the vertex degree of graph vertex , and assign the numerical scalar value to . The mean value at the end of a uniformly chosen edge and, when the corresponding variance is nonzero, the assortativity coefficient for these attributes are

			(1)
			(2)

Thus, is the correlation coefficient of the values at the two ends of a randomly oriented edge. Positive, zero, and negative values indicate assortative, neutral, and disassortative mixing, respectively (Newman 2003).

For an unlabeled simple graph, the standard choice is . The resulting is the degree assortativity coefficient: the Pearson correlation coefficient of the vertex degrees at the two ends of an edge (Newman 2002). The Wolfram Language function GraphAssortativity[g] returns . This degree-based scalar is not the graph modularity of . Newman's equivalent formula uses the excess degrees (Newman 2003). Subtracting the same constant at both ends does not change a correlation coefficient.

Categorical assortativity, also called discrete assortative mixing, is different. Let be a set partition of the vertex set. Its mixing matrix and marginal fractions are

			(3)
			(4)

where is the sum of the vertex degrees in . When its denominator is nonzero, the categorical assortativity coefficient is

			(5)
			(6)

Here, is the number of edges with both endpoints in . For categorical data specified by a set partition, GraphAssortativity[g, partition, "Normalized" -> False] returns , exactly the graph modularity score of the supplied set partition. The default GraphAssortativity[g, partition] returns , dividing this score by its available maximum for the fixed marginal fractions .