Modularity value range

🚨 This page is a work in progress.

🕑 TL;DR: Modularity $Q\in [-0.5,1]$.

Going through the examples, you may have wondered what a “good” or “bad” modularity value really is. Here, we will discuss the value range of the modularity measure.

Modularity is zero if the fraction of edges within communities is no different from the respective fraction we would expect in a random graph. We get a positive value if this fraction is higher than expected on the basis of chance. This directly results from our definition of modularity. In the simple network presented here, $Q$ was around $0.13$ which is still slightly better than at random but nevertheless worse than the best result of $Q\approx 0.46$ for that particular graph.

Upper limit $1$

In theory, the maximum possible modularity value is $1$ for a graph with infinitely many communities, such that $a_c^2\to 0$. We show this property for a graph with $t:=|\mathcal{C}|$ communities, each forming a $K_2$ graph, i. e. two vertices sharing one edge.

This graph has $t$ communities as well as $m=t$ edges. When $t$ approaches infinity, we obtain:

$$\begin{array}{rl}Q& =\underset{t\to \infty }{\lim }\frac{1}{2t}\sum _{c=1}^t\sum _{u\in c}\sum _{v\in c}\left(A_{uv}-\frac{k_u{k}_v}{2t}\right)\\ & =\underset{t\to \infty }{\lim }\frac{1}{2t}\sum _{c=1}^t(2\cdot 1-4\cdot \frac{1\cdot 1}{2t})\\ & =\underset{t\to \infty }{\lim }\frac{1}{2t}\sum _{c=1}^{t}2=\underset{t\to \infty }{\lim }\frac{2t}{2t}=1\end{array}$$

As ${\sum }_{c\in Cs}{\sum }_{u\in c}{\sum }_{v\in c}{A}_{uv}\le 2m$ and ${\sum }_{c\in Cs}{\sum }_{u\in c}{\sum }_{v\in c}\frac{k_u{k}_v}{2m}\ge 0$ for every graph partitioning, $Q=1$ is indeed the upper limit of modularity.

Lower limit $-\frac{1}{2}$

The lower limit of modularity is $-\frac{1}{2}$ which is achieved using any bipartite graph $G(U,V,E)$ with the clustering $C=\{c_U,c_V\}$ (see here), that is, each cluster encompasses all the vertices of one bipartition of $G$ (the vertex sets $U$ or respectively $V$). The following figure shows the bipartite graph $G(U,V,E)$ with $U=\{0,1\}$, $V=\{2,3,4,5\}$ and $E=\{\{0,2\},\{0,3\},\{1,4\}\}$. The given community assignment yields a modularity of $-\frac{1}{2}$, while the maximum modularity for this particular graph is $Q\approx 0.44$.

Common values

A rigorous proof that $-0.5\le Q(\mathcal{C})\le 1$ holds true for any undirected and unweighted graph $G$ and any community assignment (clustering) $\mathcal{C}$ is presented here. Note however, that for a given graph, the maximum achievable modularity is oftentimes not $1$. Newman and Girvan claim that a typical range for modularity values is from $0.3$ to $0.7$ (see here) with values above $0.3$ indicating a “significant community structure in a network” (see here). Whether values above $0.3$ really indicate a good community structure depends on the application and the particular graph.