Graph Modularity

Graph modularity assigns a score to a proposed set partition of the vertex set of a graph . It is used in community detection to measure how strongly the graph can be divided into communities. The maximum modularity of , also called the modularity of , is the maximum of this score over all vertex partitions. 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 maximum modularity of are

			(1)
			(2)

Any set partition satisfying is called a maximum-modularity partition. 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. In the Wolfram Language, GraphAssortativity[g, partition, "Normalized" -> False] returns for the supplied set partition. This evaluates that set partition only; is the maximum over all partitions.

Let and be two parts of a set partition, and let be the number of edges joining them. Merging the two parts changes the modularity score by

(3)

The merge improves the score exactly when . Consequently, two distinct parts in a maximum-modularity partition satisfy the reverse weak inequality, while every bipartition of one part satisfies .

If and both volumes are positive, splitting strictly improves the score. It follows that, after isolated vertices are removed, every part in every maximum-modularity partition induces a connected graph. The merge criterion also shows that no part can consist of a single nonisolated vertex, so every tree leaf belongs to the same part as its unique neighbor. Isolated vertices may be deleted or assigned arbitrarily without changing modularity (Brandes et al. 2008, Meeks and Skerman 2020).

For an exact decomposition, let be the connected components having edges, let , and define the resolution- maximum of a graph with edges by

(4)

Then the globally normalized component identity is

(5)

Indeed, after isolated vertices are removed, every optimal part lies in one connected component, and its globally normalized contribution is times its resolution- contribution. Thus the modularity of a disconnected graph is not in general a sum, maximum, or weighted mean of the ordinary values . However, if for every edge-bearing connected component, the identity simplifies to

(6)

In particular, for , the -ladder rung graph is the disjoint graph union of one-edge connected components and therefore has

(7)

Its values are 0, , , , ..., with reduced numerators 0, 1, 2, 3, ... (OEIS A001477) and denominators 1, 2, 3, 4, ... (OEIS A000027).

For the cycle graph with , a maximum-modularity partition may be chosen to consist of contiguous paths whose sizes differ by at most one (Brandes et al. 2008). Set , , and , where is the floor function. Then, for ,

(8)

At for , partitions into and parts tie. In particular,

(9)

where denotes big-O notation (McDiarmid and Skerman 2018).

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 , where is the floor function. For the binomial random graph in the very dense regime , they found a transition governed by the average vertex degree of the complementary graph. For fixed , with high probability when . At , the probability of zero modularity is , while with probability approaching the modularity is positive and of order . For fixed , if , then with high probability.