Assortativity

Homophily

tendency of individuals to associate disproportionately with others who are similar (e.g. ethnicity, age, profession, religion, etc) to themselves.

• Lazarsfeld, P.F. “Friendship as a social process: A substantive and methodological analysis.” Freedom and Control in Modern Society (1954)

The tendency of individuals to associate with others who are similar to themselves is known as homophily or assortative mixing. On the other hand, disassortative mixing, the tendency of individuals to associate with others who are unlike them, is also widely observed in information, technological, and biological networks [@newman2018Networks].

Modularity

To talk about assortativity, we need to specify the characteristic that defines the similarity between nodes. When such characteristics are unknown, the Unsupervised Learning task of grouping nodes into clusters is called community detection.

The idea of a community is that nodes in the same community have a higher probability of being connected than those in different communities. To capture this idea, modularity of a division is defined as

$$Q=\frac{|{\mathcal{E}}_{\mathrm{comm}}|-{\mathbb{E}}_{\mathrm{unif}}|{\mathcal{E}}_{\mathrm{comm}}|}{m},$$

where ${\mathcal{E}}_{\mathrm{comm}}$ is the set of edges within communities, and ${\mathbb{E}}_{\mathrm{unif}}$ places all $m$ edges uniformly at random. A large modularity means a low entropy, which further suggests a strong community structure.

More formally, suppose $g_i$ returns the community index of node $i$. Then,

$$|{\mathcal{E}}_{\mathrm{comm}}|=\frac{1}{2}\sum _{ij}{A}_{ij}1\{g_i=g_j\}.$$

If we break the network into stubs and reconnect the stubs uniformly at random, the expected number of edges within communities is

$$\mathbb{E}|{\mathcal{E}}_{\mathrm{comm}}|=\frac{1}{2}\sum _{ij}\mathbb{E}[1\{(i,j)\in \mathcal{E}\}]\cdot 1\{g_i=g_j\}=\frac{1}{2}\sum _{ij}\frac{d_i{d}_j}{2m}\cdot 1\{g_i=g_j\}.$$

Thus,

$$Q=\frac{1}{2m}\sum _{ij}\left(A_{ij}-\frac{d_i{d}_j}{2m}\right)1\{g_i=g_j\}.\text{\hspace{1em}(1)}$$

Let $\Delta =(1\{g_i=g_j\}{)}_{ij}$. The matrix form of modularity is

$$Q=\frac{1}{2m}{1}^T\left(A-\frac{d{d}^T}{2m}\right)\odot \Delta 1.$$

Modularity Maximization

Modularity can serve as an objective function for community detection. The discrete optimization problem is NP-hard in general. Consider a partition into two communities with index $-1$ and $1$. Then,

$$1\{g_i=g_j\}=\frac{1}{2}(1+g_i{g}_j).$$

Note that ${\sum }_{ij}(A_{ij}-d_i{d}_j/(2m))=2m-2m=0$. Thus, for this binary partition, we have

$$Q=\frac{1}{4m}{g}^T(A-d{d}^T/(2m))g,$$

recovering the ^spectral-partition with the graph Laplacian replaced by the modularity matrix $A-d{d}^T/(2m)$. However, here we can directly let the relaxed real-valued $g$ be the leading eigenvector of the modularity matrix, without degenerating to the trivial case where all nodes are in the same community. This method is also referred to as the spectral modularity maximization.

Assortative Mixing

Now suppose nodes have a scalar characteristic. If nodes with similar values tend to be connected together more often than those with different values, then the network is considered assortatively mixed according to that characteristic.

To see if links are formed based on a scalar characteristic $x$, we calculate the covariance between the characteristic values of the two endpoints of a randomly chosen edge:

$$\mathrm{Cov}(x_i,x_j)=\frac{{\sum }_{ij}{A}_{ij}(x_i-\mu )(x_j-\mu )}{{\sum }_{ij}{A}_{ij}},$$

where the marginal mean $\mu$ is defined as

$$\mu =\frac{{\sum }_{ij}{A}_{ij}{x}_i}{{\sum }_{ij}{A}_{ij}}=\frac{{\sum }_i{d}_i{x}_i}{2m}.$$

Thus,

$$\mathrm{Cov}(x_i,x_j)=\frac{{\sum }_{ij}{x}_i{x}_j}{2m}-\frac{{\sum }_{ij}{d}_i{x}_i{d}_j{x}_j}{(2m{)}^2}=\frac{1}{2m}\sum _{ij}\left(A_{ij}-\frac{d_i{d}_j}{2m}\right)x_i{x}_j,$$

which recovers ^eq-mod by replacing the community indicator with the characteristic value. In matrix form, we have

$$\mathrm{Cov}(x_i,x_j)=\frac{1}{2m}{x}^T\left(A-\frac{d{d}^T}{2m}\right)x.$$

Note that

$$\mathrm{Var}(x_i)=\mathrm{Cov}(x_i,x_i)=\frac{1}{2m}\sum _{ij}\left(d_i{\delta }_{ij}-\frac{d_i{d}_j}{2m}\right)x_i{x}_j=\frac{1}{2m}{x}^T\left(D-\frac{d{d}^T}{2m}\right)x.$$

We define the assortativity coefficient as the correlation:

$$r=\frac{x^T(A-d{d}^T/(2m))x}{x^T(D-d{d}^T/(2m))x}.$$

$r=1$ means perfect assortative mixing, $r=0$ means no assortative mixing, and $r=-1$ means perfect disassortative mixing.

Degree Correlation

When the characteristic is the degree, associative mixing gives core-periphery structures, where high-degree nodes tend to stick together to form a core surrounded by a periphery of low-degree nodes, commonly observed in social networks. Disassortative mixing by degree tend to give hub-and-spoke structures, where high-degree nodes are hubs that connect many low-degree nodes that connect to other hubs. Replacing $x$ with the degree vector $d$ gives the assortativity coefficient by degree.