Multiway spectral community detection in networks

One of the most widely used methods for community detection in networks is the maximization of the quality function known as modularity. Of the many maximization techniques that have been used in this context, some of the most conceptually attractive are the spectral methods, which are based on the eigenvectors of the modularity matrix. Spectral algorithms have, however, been limited, by and large, to the division of networks into only two or three communities, with divisions into more than three being achieved by repeated two-way division. 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, particularly in cases where community sizes are unbalanced. We also give demonstrative applications of the algorithm to two real-world networks and find that it produces results in good agreement with expectations for the networks studied.

Figure 1

Depiction of the operation of our vector partitioning heuristic for, in this case, a set of two-dimensional vectors being divided into three groups. The blue lines and dots denote the individual vectors. The red lines are the group vectors. (The magnitudes of the group vectors have been rescaled to fit into the figure—normally they would be much larger, since they are the sums of the individual vectors in each group.) The dashed lines indicate the borders between communities, which are determined both by the angles and relative magnitudes of the group vectors. For example, the vector labeled ${\mathbf{r}}_1$ will be assigned to group 1 in this case because it has its largest inner product with ${\mathbf{R}}_1$.

Figure 2

Normalized mutual information (NMI) as a function of the parameter $\delta$ for communities detected in randomly generated test networks using the vector partitioning algorithm of this paper (red squares) and the $k$-means method (blue triangles). The networks consist of $n=3600$ vertices each, divided into three communities thus: (a) equally sized communities of 1200 vertices each; (b) communities of sizes 1800, 1200, and 600; (c) communities of sizes 2400, 900, and 300. Each data point represents the highest NMI found over 20 runs of the relevant algorithm with different random initializations, averaged over 100 networks. The vertical dashed line in (a) indicates the position of the detectability threshold below which all methods must fail [28].

Figure 3

Illustration of the division of a synthetic three-group network using (a) the algorithm of this paper and (b) the $k$-means algorithm. Shapes indicate the planted communities while colors indicate the communities found by the two algorithms. Observe how the $k$-means algorithm assigns a significant portion of vertices belonging to the red and green communities incorrectly to the blue one, while the vector partitioning approach does not have this problem. The network in this case has $n=4000$ vertices with communities of size 3000, 500, and 500.

Figure 4

Four-way division into communities of a collaboration network of scientists at the Santa Fe Institute. Different colors and shapes indicate the communities discovered by the vector partitioning algorithm of this paper. The communities split roughly along lines of research topic.

Figure 5

The 21 communities found in a collaboration network of network scientists using the algorithm proposed in this paper.