Spectral tripartitioning of networks

We formulate a spectral graph-partitioning algorithm that uses the two leading eigenvectors of the matrix corresponding to a selected quality function to split a network into three communities in a single step. In so doing, we extend the recursive bipartitioning methods developed by Newman [M. E. J. Newman, Proc. Natl. Acad. Sci. U.S.A. 103, 8577 (2006); Phys. Rev. E 74, 036104 (2006)] to allow one to consider the best available two-way and three-way divisions at each recursive step. We illustrate the method using simple “bucket brigade” examples and then apply the algorithm to examine the community structures of the coauthorship graph of network scientists and of U. S. Congressional networks inferred from roll call voting similarities.

Figure 1

(Color online) Bisection in two dimensions (i.e., using the leading pair of eigenvectors of $\mathbf{B}$) for a small network. Solid (blue) lines with dots represent node vectors. The dotted (red) line represents a selected cut line in the plane. All nodes on one side of the line are assigned to one community and all nodes on the other side are assigned to the other community. Rotating this line about the origin yields the set of possible planar bipartitions. (This figure is adopted from one in Ref. [28].)

Figure 2

(Color online) The eight-node bucket brigade network discussed in Ref. [28] and a similar 20-node bucket brigade network. Solid lines between nodes represent connections. (a) shows the best initial bipartition (solid vertical line) of the eight-node network (no further subdivision increases modularity). (b) shows the modularity-maximizing partition (dotted lines) of the same network. Note that the three-community partition in (b) cannot be obtained directly from (a) via subsequent partitioning. (c) shows the maximum modularity partition of the 20-node network into four communities (indicated by ovals around nodes and also by colors online), compared with the partition obtained via the best initial three-way division (vertical dotted lines), which is larger than that obtained by the initial bipartition (vertical solid line). In this case, the four-way partition cannot be obtained from recursive partitioning of the initial three-way division, but it is obtained from recursive partitioning of the bipartition.

Figure 3

(Color online) Tripartitioning with vertex vectors from the leading pair of eigenvectors of $\mathbf{B}$ for a small network. Solid (blue) lines with dots represent node vectors, which have been rescaled according to the observed standard deviation of each component. The dotted (red) rays border a selected set of wedges in the plane, where each wedge indicates the set of nodes assigned to one group. One obtains the tripartitions allowed by the planar geometric constraints by rotating the boundaries of these wedges about the origin.

Figure 4

(Color online) Two-dimensional vertex vector coordinates of the 379-node largest connected component of the network scientist coauthorship graph. Colors and shapes denote the post-KL three-community partition discussed in the text.