• people have, it appears, a strong tendency to associate with others whom they perceive as being similar to themselves in some way
• this tendency is called homophily or assortative mixing
• more rarely, we also encounters heterophily, or disassortative mixing, the tendency of people to associate with others who are unlike them
• the most familiar example of disassortativity is mixing by gender in sexual contact networks
• assortative mixing is mainly a property of social networks, although not exclusively.

• assortative mixing can be distinguished in mixing by enumerative or scalar characteristics
• an enumerative characteristic has a finite, not sorted set of possible values (examples are gender, race, and nationality)
• given an enumerative characteristic, each node of the network can be assigned to a type according to the value of the characteristic for the node
• the network is assortative if a significant fraction of the edges run between vertices of the same type

What is a measure of assortativity for enumertive properties?

A measure of assortativity is modularity, that we already encountered in community detection.

\[Q = \frac{1}{2m} \sum_{i,j} \left(a_{i,j} - \frac{k_i k_j}{2m}\right) \delta(c_i, c_j)\]

The modularity takes positive values if there are more edges between same-type vertices than expected, and negative values if there are less.

When is modularity maximum and what is its maximum value?

The maximum value is the modularity of a perfectly mixed network, which is a network where all edges run between nodes of the same type.

In this network, the actual number of edges with nodes of the same type is of course \(m\), hence the modularity results:

\[Q_{max} = \frac{1}{2 m} \left( 2m - \sum_{i,j} \frac{k_i k_j}{2m} \delta(c_i, c_j) \right)\]

We can normalize modularity by dividing it by the maximum value it can have, that is the modularity of a perfectly mixed network.

The normalized modularity is:

\[\frac{Q}{Q_{max}} = \frac{\sum_{i,j} (a_{i,j} - k_i k_j / 2m) \delta(c_i, c_j)}{2m - \sum_{i,j} (k_i k_j / 2m) \delta(c_i, c_j)}\]

• we can also investigate homophily according to scalar characteristics
• these are features whose values can be sorted, like age or salary
• if network nodes with similar values of a scalar characteristic tend to be connected together more often that those with different values then the network is assortatively mixed according to such characteristic.

A measure of assortative mixing according to a scalar characteristic is the covariance.

In probability theory and statistics, covariance is a measure of how much two random variables \(X\) and \(Y\) change together. Variance is a special case of the covariance when the two variables are identical. It is:

\[cov(X,Y) = E[(X - E[X]) (Y - E[Y])]\]

where \(E[\cdot]\) is the expected value of the random variable.

If the variables change together (both above or below their means), then the covariance is positive, otherwise (one above the mean and the other below) it is negative.

The idea is to assign one variable \(L\) (left) to one end of the edges of the network, and another variable \(R\) (right) to the other end of the edges.

These variables assume the values of the scalar quantity for the nodes at the ends of the edges (both edges \((i,j)\) and \((j,i)\) are considered in the undirected case).

Consider the following example:

Let \(x_i\) be the value for vertex \(i\) of the scalar quantity:

\[L = (x_1, x_1, x_1, x_2, x_2, x_3, x_4, x_3) \\ R = (x_2, x_3, x_4, x_3, x_1, x_1, x_1, x_2)\]

Notice that both lists \(L\) and \(R\) contain each value \(x_i\) a number of times equal to the degree \(k_i\) of node \(i\). In fact \(L\) and \(R\) are permutations of each other.

Hence the means \(\mu_L\) of \(L\) and \(\mu_R\) of \(R\) are equal. Similarly, the standard deviations \(\sigma_L\) of \(L\) and \(\sigma_R\) of \(R\) are the same.

The covariance of \(L\) and \(R\) measures if the scalar quantities associated by the edge relationship vary in the same direction or in opposite directions. This is given by:

\[cov(L,R) = \frac{\sum_{i,j} a_{i,j} (x_i - \mu) (x_j - \mu)}{\sum_{i,j} a_{i,j}}\]

where the mean \(\mu = \mu_L = \mu_R\) is computed over the edges as follows:

\[\mu = \frac{\sum_{i,j} a_{i,j} x_i}{\sum_{i,j} a_{i,j}} = \frac{\sum_{i} x_i \sum_j a_{i,j}}{\sum_{i} \sum_j a_{i,j}} = \frac{\sum_{i} k_{i} x_i}{\sum_{i} k_i}\]

The covariance is positive if values \(x_i\) and \(x_j\) for vertices connected by an edge tend to be both large (larger than the mean) or small (smaller than the mean), and negative if they vary in opposite directions.

When is covariance maximum and what is its maximum value?

The covariance is maximum when all edges fall between nodes with precisely the same values of \(x_i\).

Hence, putting \(x_i = x_j\) in the covariance formula we have:

\[cov_{max}(L,R) = \frac{\sum_{i,j} a_{i,j} (x_i - \mu)^2}{\sum_{i,j} a_{i,j}}\] Notice that this quantity is the variance \[\sigma^{2}_{L} = \sigma^{2}_{R} = \sigma_{L} \sigma_{R}\] of values \(x_i\) over the edges of the network.

Just as with the modularity measure, it is convenient to normalize the covariance so that it takes value one in a perfectly mixed network.

The normalized assortativity measure is defined as the ratio:

\[cor(L,R) = \frac{cov(L, R)}{\sigma_{L} \sigma_{R}} = \frac{\sum_{i,j} a_{i,j} (x_i - \mu) (x_j - \mu)}{\sum_{i,j} a_{i,j} (x_i - \mu)^2}\]

But this ratio is precisely the Pearson correlation coefficient for the scalar characteristic computed over the edges of the network.

In this context, it is called assortativity coefficient. It varies between:

• a maximum of 1 for perfectly assortative networks
• a minimum of -1 for perfectly disassortative ones
• avalue of 0 implies uncorrelation of the values of the characteristic over the nodes of the edges

• a special and important case of assortative mixing according to a scalar characteristic is mixing by degree. That is, the scalar property is the degree of a node
• in a network with assortative mixing by degree the high-degree nodes will be preferentially connected to other high-degree nodes, and the low to low
• in a social network, for example, we have assortative mixing if the gregarious people are friends with other gregarious people and the hermits with other hermits
• the reason this particular case is interesting is that degree is itself a property of the network structure. Hence one property of the network (degree) influences another (positions of edges)
• an assortative network by degree has a core-periphery structure, with a core of high-degree nodes surrounded by a less dense periphery of nodes with low degrees
• on the other hand, if a network is disassortative mixed, it contains star-like structures

Consider again the dolphin social network:

• A CSV with names and sex of dolphins
• A CSV with ties among dolphins

1. Is the network assortative by sex?
2. Is the network assortative by node degree?

library(igraph)
library(readr)
library(dplyr)

edges = read_csv("dolphin_edges.csv")
nodes = read_csv("dolphin_nodes.csv")
nodes = mutate(nodes, id = row_number()) %>% select(id, everything())
g = graph_from_data_frame(edges, directed = FALSE, vertices = nodes)

# assortativity by sex
male = V(g)$sex == "M"
names(male) = V(g)$name
# absolute modularity
modularity(g, membership = male + 1)

## [1] 0.1779795

# assortativity by degree
d = degree(g)
edge = as_edgelist(g)
l = c(edge[,1], edge[,2])
r = c(edge[,2], edge[,1])
dl = d[l]
dr = d[r]
cor(dl, dr)

## [1] -0.04359403

1. create a function assortative_degree that computes the assortativity by degree of a graph;
2. check the assortativity by degree of some graphs generated with the preferential attachment model increasing the parameter m (number of edges of a new node).

assortative_degree = function(g) {
  d = degree(g)
  edge = as_edgelist(g)
  l = c(edge[,1], edge[,2])
  r = c(edge[,2], edge[,1])
  dl = d[l]
  dr = d[r]
  cor(dl, dr)
}

g = sample_pa(100, m = 1, directed = FALSE)
assortative_degree(g)

## [1] -0.226309

g = sample_pa(100, m = 2, directed = FALSE)
assortative_degree(g)

## [1] -0.1946724

g = sample_pa(100, m = 3, directed = FALSE)
assortative_degree(g)

## [1] -0.09510921

g = sample_pa(100, m = 10, directed = FALSE)
assortative_degree(g)

## [1] -0.06268478