"Spectral Tripartitioning of Networks"

The published version of another one of my papers just came out. This paper is a methods paper:

Title: Spectral Tripartitioning of Networks

Authors: Thomas Richardson, Peter J. Mucha, and Mason A. Porter

Abstract: 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.


There are a couple of vignettes worth mentioning:

1. One of the referee reports for the original version of the paper complained that we cited Mark Newman too much. (This is, to date, the only time a referee has ever complained to me about citing someone else too much.)

2. This is the first time I have ever gotten a networks paper into a Physical Review journal. (I have gotten such papers in other good journals, but upon submitting networks papers, PR has usually tended to just tell me that they don't consider the paper to be physics. It's a crapshoot, though I have since gotten one of the Physical Review E editors to indicate conditions (or at least his opinion of what they should be) for whether or not something is "physics" that are much more precise than what APS, the publisher of these journals, has posted on the Web. (I can pass this along if you ask me privately. It's public information, but I just don't want to get into it in this blog entry.)