Modularity

🚨 This page is a work in progress.

Motivation

We are often faced with networks whose underlying community structure is not known in advance, yet still, we need a measure to evaluate how good our proposed partition of the network into communities is. This is especially important when dealing with algorithms requiring an objective function to maximize (e.g. genetic algorithms). Newman and Girvan proposed a measure called modularity in 2003, which was adopted broadly and successfully in the network research community. Modularity $Q$ is maximized for divisions of a graph when many edges fall within the proposed communities (intra-community edges) as compared to edges between communities (inter-community edges).

The following figure depicts a contrived network with different vertex-community assignments. The intuitive grouping of vertices into communities in (a) leads to the maximal achievable modularity value of $Q\approx 0.46$ for this particular graph. This grouping is characterized by only sparse connections between communities which are in themselves densely connected. In contrast, figure (b) results in a lower value of just $Q\approx 0.13$. We will discuss the possible range of modularity values later on.

Configuration model & modularity formula

In the following, we assume a graph $G$ with $\mid V(G)\mid =n$ vertices and $\mid E(G)\mid =m$ edges. The edge set $E(G)$ is determined by the adjacency matrix¹ $A$ with entries:

$$A_{uv}=\{\begin{array}{ll}1,& \text{if }u\text{ and }v\text{ are neighbors},\\ 0,& \text{otherwise}\end{array}$$

Of all the edges, a high fraction of edges that connect vertices in the same community should give a good partition. For a specific community $c$, this fraction is given by

$$e_c=\frac{1}{2m}\sum _{u\in c}\sum _{v\in c}{A}_{uv}$$

where we iterate over all edges $u,v$ with both ends in community $c$. We divide by $m$ to retrieve the fraction of all edges. The factor $2$ comes from the assumption that we only deal with undirected edges, so every edge occurs twice for every order of arguments ($A_{uv}$ and $A_{vu}$). We call this term $e_c$ in accordance with here. Aiming for

$$\max \sum _{c\in \mathcal{C}}{e}_c$$

with $\mathcal{C}$ being the set of all proposed communities, makes sure a high fraction of edges is within communities (and not between). However, the trivial case with all vertices in the same community yields a maximum value of $1$. Therefore, we cannot use this measure alone, but instead compare this fraction of intra-community edges with the expected number of intra-community edges if edges were distributed at random in our graph. Note that “random” does not mean any arbitrary graph, instead, the following properties should be preserved to allow for a fair comparison:

1. The number of nodes $n$
2. The number of edges $m$
3. The vertex degree $k_v$ for all vertices $v\in V(G)$.

We employ the configuration model as null model (as seen here). A new, “empty” graph with $n$ nodes is constructed and $m$ edges are randomly inserted between vertices whilst ignoring their (potentially known) community structure.

In order to analyze the expected fraction of edges between any nodes $u$ and $v$ in a community, we cut every edge into two halves, leaving only edge stubs on the vertices as shown in the next figure. Since we have $m$ edges in our graph, we end up with $2m$ edge stubs. There are $k_v$ ways to connect one edge stub of vertex $u$ (marked in red) to any edge stub of $v$ (marked in blue). Randomly, we could connect this one edge stub of $u$ to any of the $2m-1$ edge stubs in the entire graph ². Hence, the probability that one edge stub of $u$ connects to any edge stub of $v$ in our random graph is given by $\frac{k_v}{2m-1}$. As vertex $u$ has $k_u$ edge stubs, the probability that vertex $u$ connects to vertex $v$, i. e. any edge stub of $u$ connects to any edge stub of $v$, is given by

$$p(u,v)=\frac{k_u{k}_v}{2m-1}$$

This yields the equation for the expected number of edges that fall within a community $c$ if edges were distributed randomly in the graph while preserving node degrees:

$$\boxed{a_c^2:=\frac{1}{2m}\sum _{u\in c}\sum _{v\in c}\frac{k_u{k}_v}{2m}}$$

The same reasoning as before applies here for the term $\frac{1}{2m}$. Since we are dealing with big networks where $2m\gg 1$, it is reasonable to drop the aforementioned “$-1$” in the denominator, which is common in literature (see here and here). Again, to show the connection to the original definition of modularity by Newman and Girvan, we refer to this term as $a_c^2$, where for any community $c$, we define $a_c$ as:

$$a_c=\frac{1}{2m}\sum _{v\in c}{k}_v$$

This denotes the fraction of edge stubs (out of all $\approx 2m$ edge stubs in the graph) that are attached to vertices in community $c$. One could also refer to this as the total vertex degree of vertices in community $c$ divided by twice the number of edges in the graph $2m$.

By combining $e_c$ with $a_c^2$ and by iterating over all communities $c\in \mathcal{C}$, we get: $$\begin{array}{rl}Q(\mathcal{C})& :=\left(\text{fraction of edges that fall within the proposed communities}\right)\\ & -\left(\text{expected fraction of such edges in a random graph}\right)\\ & =\sum _{c\in \mathcal{C}}(e_c-a_c^2)\\ & =\sum _{c\in \mathcal{C}}\left(\frac{1}{2m}\sum _{u\in c}\sum _{v\in c}{A}_{uv}-\frac{1}{2m}\sum _{u\in c}\sum _{v\in c}\frac{k_u{k}_v}{2m}\right)\end{array}$$

This gives us the definition of modularity that is often found in literature. We can use this measure as quality function for algorithms, rendering the problem of community detection into that of modularity optimization. Note that the variable $Q$ stands for “quality” ³.

$$\boxed{Q(\mathcal{C})=\frac{1}{2m}\sum _{c\in \mathcal{C}}\sum _{u\in c}\sum _{v\in c}\left(A_{uv}-\frac{k_u{k}_v}{2m}\right)}$$

While we only consider undirected (and possibly weighted) graphs here, modularity can be extended to directed graphs as well, as seen here and here.

Alternative formulation

An alternative formulation of modularity is used here. Both variants are equal as we can transform them into each other. We will use the following identity to get from the first to the second line:

$$\sum _{i=1}^n\sum _{j=1}^n{x}_i{x}_j={\left(\sum _{k=1}^n{x}_k\right)}^2$$

$$\begin{array}{rl}Q(\mathcal{C})& =\sum _{c\in \mathcal{C}}\left(\sum _{u\in c}\sum _{v\in c}\frac{A_{uv}}{2m}-\sum _{u\in c}\sum _{v\in c}\frac{k_u{k}_v}{2m}\frac{1}{2m}\right)\\ & =\sum _{c\in \mathcal{C}}\left(\sum _{u\in c}\sum _{v\in c}\frac{A_{uv}}{2m}-{\left(\frac{{\sum }_{v\in c}{k}_v}{2m}\right)}^2\right)\\ & =\sum _{c\in \mathcal{C}}\left(\frac{{\Sigma }_c}{2m}-{\left(\frac{{\Sigma }_{\hat{c}}}{2m}\right)}^2\right)\\ & =\frac{1}{2m}\sum _{c\in \mathcal{C}}\left({\Sigma }_c-\frac{{\left({\Sigma }_{\hat{c}}\right)}^2}{2m}\right)\end{array}$$

$$\boxed{Q(\mathcal{C})=\frac{1}{2m}\sum _{c\in \mathcal{C}}\left({\Sigma }_c-\frac{{\left({\Sigma }_{\hat{c}}\right)}^2}{2m}\right)}$$

with ${\Sigma }_c={\sum }_{u\in c}{\sum }_{v\in c}{A}_{uv}$ and ${\Sigma }_{\hat{c}}={\sum }_{v\in c}{k}_v$. Here, ${\Sigma }_{\hat{c}}$ is the sum of the weights of edges incident to vertices in $c$ (including self-loops), while ${\Sigma }_c$ is the sum of the weights of edges inside the community⁴. This is the actual formula used in the code.

“This reveals an inherent trade-off: To maximize the first term [inside the parantheses], many edges should be contained in clusters, whereas the minimization of the second term is achieved by splitting the graph into many clusters with small total degrees each.” ~ from here

🎈 Task: We motivated the introduction of a negative term in the modularity formula by this observation: “However, the trivial case with all vertices in the same community yields a maximum value of 1.” Make sure you understand why this is the case. Take a look at the definition of $e_c$.