Modularity (networks)

Modularity is a benefit function used in the analysis of networks such as computer networks or social networks. It quantifies the quality of a division of a network into modules or communities. Good divisions, which have high values of the modularity, are those in which there are dense internal connections between the nodes within modules but only sparse connections between different modules. The most common use of the modularity is as the basis for methods of detecting community structure in networks.

Definition

Consider a network composed of n nodes or vertices connected by m links or edges and let A_ij be and element of the adjacency matrix of the network, which gives the number of edges between vertices i and j. And suppose we are given a candidate division of the nodes into some number of groups. The modularity is defined to be the fraction of the edges that fall within groups minus the expected such fraction if edges are distributed at random. In the most common version of the concept, the randomization of the edges is done so as to preserve the degree of each node. In this case, the expected number of edges falling between two nodes i and j following randomization is k_i k_j /2m, and hence the actual minus expected number of edges between the same two nodes is A_ij − k_i k_j /2m. Summing over all pairs of nodes in the same group, the modularity, denoted Q, is then defined as

$Q={\frac {1}{2m}}\sum _{ij}\left[A_{ij}-{\frac {k_{i}k_{j}}{2m}}\right]\delta (c_{i},c_{j}),$

where δ(c_i,c_j) is the Kronecker delta symbol.