Finding good nearly balanced cuts in power law graphs

Kevin Lang (langkoverture.com)

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

Keywords: graph partitioning, power law graphs, semidefinite programming, spectral method, flow-based rounding, social graphs

Category 1: Combinatorial Optimization (Graphs and Matroids )

Citation: Technical Report YRL-2004-036 Yahoo! Research Labs North Pasadena Avenue, 3rd Floor Pasadena, CA 91103 November 2004

Download: [PDF]

Entry Submitted: 12/20/2004
Entry Accepted: 12/21/2004
Entry Last Modified: 12/20/2004

Modify/Update this entry