New math proof reveals exact edge deletion threshold for modularity in graphs
Complete graphs need only ⌊n/2⌋+1 edge removals to gain non-zero modularity—a precise limit found.
Modularity measures how well a graph can be partitioned into communities—a key concept in network science. It is known that complete graphs and complete multipartite graphs have modularity zero, meaning they lack any community structure. In a new paper on arXiv, mathematicians Colin McDiarmid and Fiona Skerman (University of Oxford) present precise thresholds for when graphs transition from zero to non-zero modularity. For a complete graph on n vertices, they prove that the minimum number of edges you must delete to obtain a graph with non-zero modularity is exactly ⌊n/2⌋+1. For complete bipartite graphs, they determine the smallest number of edge deletions or additions needed to break zero modularity.
The paper also analyzes very dense random graphs. The authors find a sharp transition: when the average degree of the complement graph (the set of missing edges) drops below 1, the modularity of the original dense graph becomes zero. This result has practical implications for community detection algorithms, which often fail on extremely dense networks. The work complements earlier results on sparse random graphs and extends to natural variants of the modularity definition. By pinning down exact edge counts, the research provides rigorous boundaries for when communities can—and cannot—emerge from network structure.
- Deleting at least ⌊n/2⌋+1 edges from K_n yields non-zero modularity; fewer edges keep modularity at zero.
- For complete bipartite graphs, minimum edge deletions or additions for non-zero modularity are also determined.
- Very dense random graphs have zero modularity if the complement graph's average degree < 1; above that threshold, modularity becomes positive.
Why It Matters
Exact thresholds like these help algorithm designers know when community detection will work on dense networks.