Modularity

As an example of how math is used in network science, several popular community detection algorithms (including those discussed in Chapter 7, In-Between – Communities) work by maximizing a mathematical property called modularity. Modularity is the difference between the fraction of internal edges and how many you'd expect if edges were assigned randomly (without changing vertex degrees).

Let's assume an undirected network. Given a set of vertex labels c, with corresponding vertex degrees k_i for i∊c, the expected fraction of internal edges can be approximately written as follows:

∑_i∊c ∑_j∊c k_ik_j / (2 |E|)²,

Here, |E| is the total number of edges. The true number of edges between vertices i and j is given by element A_i,j of the adjacency matrix. Summing over all communities c in partition C, the modularity Q, can be written...