Universal lower bound for community structure of sparse graphs

Vilhelm Agdur, Nina Kamčev, Fiona Skerman

We prove new lower bounds on the modularity of graphs. Specifically, the modularity of a graph $G$ with average degree $\bar{d}$ is $\Omega ({\bar{d}}^{-1/2})$, under some mild assumptions…