Multiway spectral community detection in networks

Spectral methods are widely used for community detection in networks because of their high efficiency and amenability to formal analysis. However, spectral algorithms have been limited to the division of networks into only two or three communities. Here we present a spectral algorithm that can directly divide a network into any number of communities. The algorithm makes use of a mapping from modularity maximization to a vector partitioning problem, combined with a fast heuristic for vector partitioning. We compare the performance of this spectral algorithm with previous approaches and find it to give superior results. We also give demonstrative applications of the algorithm to real-world networks and find that it produces results in good agreement with expectations for the networks studied.