Graph modularity is a score used in community detection to measure how strongly a graph can be divided
into communities. A graph
community is a group of vertices that are more strongly
connected to one another than expected under a specified comparison model. Let 
be a graph
with 
edges, and let 
be a set partition of its
vertex set. For a part 
, let 
be the number of edges with
both endpoints in 
,
and let 
be the sum of the vertex degrees in 
. The modularity score of 
and the modularity of 
are
 |  |  |
(1)
|
 |  |  |
(2)
|
The first term rewards edges lying within parts, while the second subtracts a degree-based null-model expectation (Newman and Girvan 2004).
For every nonempty graph, 
; by convention, an empty
graph has modularity zero.
Every complete graph and every complete multipartite graph has modularity zero. McDiarmid and Skerman (2026) proved that,
for 
,
the fewest edges that can be deleted from 
to obtain positive modularity is 
. They also found a transition for very dense random
graphs near the point where the average degree of the complementary
graph is 1.
