On Graphs with Modularity Zero or Near-Zero

Abstract

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_n$ to obtain a graph with non-zero modularity is $\lfloor n/2\rfloor +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_n$ to obtain a graph with non-zero modularity.