In power law graphs, cut quality varies inversely with cut balance. Using some million node social graphs as a test bed, we empirically investigate this property and its implications for graph partitioning. We use six algorithms, including Metis and MQI (state of the art methods for finding bisections and quotient cuts) and four relaxation/rounding methods. We find that an SDP relaxation avoids the Spectral method's tendency to break off tiny pieces of the graph. We also find that a flow-based rounding method works better than hyperplane rounding.
Citation
Technical Report YRL-2004-036 Yahoo! Research Labs North Pasadena Avenue, 3rd Floor Pasadena, CA 91103 November 2004