Universal lower bound for community structure of sparse graphs
A figure from the paper.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 on the degree sequence of $G$ . The lower bound $\Omega(\bar{d}^{-1/2})$ applies, for instance, to graphs with a power-law degree sequence or a near-regular degree sequence.
It has been suggested that the relatively high modularity of the Erdős-Rényi random graph $G_{n,p}$ stems from the random fluctuations in its edge distribution, however our results imply high modularity for any graph with a degree sequence matching that typically found in $G_{n,p}$ .
The proof of the new lower bound relies on certain weight-balanced bisections with few cross-edges, which build on ideas of Alon [Combinatorics, Probability and Computing (1997)] and may be of independent interest.
When applying community detection in practice, one of the most commonly used methods is to try to find a partition that achieves a high modularity. Unfortunately, this is not a statistically justified method, and so it is in general unclear how to determine if the partition one finds is actually significant, or just the product of random noise.
In this paper, we improve the best known bounds on the modularity that are agnostic to actual structure of the graph – so, in essence, we prove that even when there is no significant community structure, there will still be a partition with non-zero modularity. While not a statistical test, this does give some way of heuristically evaluating a partition, since if it does not achieve a much better value than our bound, it is likely just detecting noise in the data.
This paper is joint work with my supervisor, Fiona Skerman, and our collaborator Nina Kamčev. I presented this paper at NetSci 2023, and it is currently under review for journal publication.
