A note on graphs whose largest eigenvalue of the modularity matrix equals zero

Abstract

Informally, a community within a graph is a subgraph whose vertices are more connected to one another than to the vertices outside the community. One of the most popular community detection methods is the Newman’s spectral modularity maximization algorithm, which divides a graph into two communities based on the signs of the principal eigenvector of its modularity matrix in the case that the modularity matrix has positive largest eigenvalue. Newman defined a graph to be indivisible if its modularity matrix has no positive eigenvalues. It is shown here that a graph is indivisible if and only if it is a complete multipartite graph.