Theoretical analysis determines edge perturbation thresholds for non-zero modularity in dense graphs, revealing phase transitions governed by complementary graph structure.
It is known that complete graphs and complete multipartite graphs have modularity zero. We show that the least number of edges we may delete from the complete graph Kₙ to obtain a graph with non-zero modularity is n/2 +1. Similarly we determine the least number of edges we may delete from or add to a complete bipartite graph to reach non-zero modularity. We give some corresponding results for complete multipartite graphs, and a short proof that complete multipartite graphs have modularity zero. We also analyse the modularity of very dense random graphs, and in particular we find that there is a transition to modularity zero when the average degree of the complementary graph drops below 1. Finally we consider some natural variants of the definition of modularity; and investigate which graphs have corresponding modularity value 0, and the least number of edges we may delete from the complete graph Kₙ to obtain a graph with non-zero modularity.
No takes yet. Share an insight, caveat, or question.
McDiarmid et al. (2026) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: