Network Science & Graph Analytics
Newman-Girvan Network Modularity Q Partition Formula
Evaluate graph community clustering via Mark Newman and Michelle Girvan’s (2004) Modularity Q = SUM_c(e_cc - a_c^2) comparing intra-community edge share against the degree-preserving configuration null model.
Why raw internal edge percentage fails — and how Newman-Girvan Modularity Q subtracts the random null!
If you merge EVERY node of a social, transaction, or microservice dependency graph into a single giant cluster, 100% of edges fall "inside" the cluster — proving why raw internal edge share SUM(e_cc) cannot evaluate community detection! Mark Newman and Michelle Girvan (2004) solved this with Modularity Q = SUM_{c=1}^K (e_cc - a_c^2) in [-0.5, 1), where m is total undirected edges (2*m edge stubs), e_cc = L_in_c / m is the fraction of edges with BOTH endpoints inside community c, and a_c = D_c / (2*m) = (2*L_in_c + L_ext_c) / (2*m) is community c’s share of total degree stubs (so a_c^2 is the expected fraction of internal edges under random degree-preserving rewiring)! Merging everything into 1 cluster yields e_11 = 1 and a_1 = 1 -> Q = 1 - 1^2 = 0.0000!
Verify on an exact m = 10-edge graph partitioned into 3 communities (Rows 2..4): Cluster_1 (Internal_Edges L_in = 4, External_Cross_Stubs L_ext = 1 -> Degree_Sum D_1 = 9), Cluster_2 (L_in = 3, L_ext = 2 -> D_2 = 8), and Cluster_3 (L_in = 1, L_ext = 1 -> D_3 = 3; check: Internal = 8 edges + Cross = (1+2+1)/2 = 2 edges -> m = 10 total edges, 2*m = 20 total stubs = 9 + 8 + 3!). Internal Edge Shares e_cc = [0.40, 0.30, 0.10] sum to 0.8000 (80% internal), Stub Shares a_c = [0.45, 0.40, 0.15] yield Null Expected Shares a_c^2 = [0.2025, 0.1600, 0.0225] summing to 0.3850, and Newman-Girvan Modularity is Q = 0.8000 - 0.3850 = 0.4150 (strong community structure, Q > 0.30)!
| Community Partition Metric (m = 10 Edges, 2m = 20 Stubs) | Formula | Verified Output |
|---|---|---|
| Observed Intra-Community Edge Fraction | SUM(L_in) / m = 8 / 10 | 0.8000 (80.0% Internal Edges) |
| Degree-Preserving Null Expectation | SUM((D_c / 2m)^2) = 0.45^2 + 0.40^2 + 0.15^2 | 0.3850 (38.5% Random Baseline) |
| Newman-Girvan Modularity (Q) | SUM(e_cc - a_c^2) | 0.4150 (Strong Partition!) |
| Single-Cluster Degenerate Merge Check | 1.0000 - 1.0000^2 | 0.0000 (Zero Modularity Gain) |
Total Undirected Edge Count m = SUM(L_in) + 0.5 * SUM(L_ext) Formula
Every internal edge contributes 2 stubs to D_c, while every cross-community edge contributes 1 stub to each endpoint cluster (so SUM(L_ext) must be an even non-negative integer).
=IF(OR(MIN(B2:B4) < 0, MIN(C2:C4) < 0, MOD(SUM(C2:C4), 2) <> 0, SUM(B2:B4) + 0.5 * SUM(C2:C4) <= 0), "Invalid Partition Stubs", SUM(B2:B4) + 0.5 * SUM(C2:C4))Exact Newman-Girvan Modularity Q = SUM(e_cc) - SUM(a_c^2) Formula
Use SUMPRODUCT(D2:D4, D2:D4) / (4 * m^2) to evaluate SUM(a_c^2) cleanly without array broadcasting!
=LET(m_ed, SUM(B2:B4) + 0.5 * SUM(C2:C4), IF(OR(MIN(B2:B4) < 0, MIN(C2:C4) < 0, MOD(SUM(C2:C4), 2) <> 0, m_ed <= 0), "Invalid Partition Stubs", ROUND((SUM(B2:B4) / m_ed) - (SUMPRODUCT(D2:D4, D2:D4) / (4 * (m_ed ^ 2))), 4)))Try the example
Use the original values or change them to test your understanding.