Using graph partitioning for efficient network modularity optimization

The paper reviews an approach for finding the communities of a network developed by the authors [WAW'06, Lecture Notes in Computer Science, Volume 4936/2008, 117-128, IEEE TPDS vol. PP, issue 99, 2012], which is based on a reduction of the modularity optimization problem to the minimum weighted cut problem, and gives an experimental evaluation of an implementation based on that approach on graphs from the 10th DIMACS Implementation Challenge Testbed. Specifically, we describe a reduction from the problem of finding a partition of the nodes of a graph G that maximizes the modularity to the problem of finding a partition that minimizes the weight of the cut in a complete graph on the same node set as G, and weights dependent on a random graph model associated with G. The resulting minimum cut problem can then be solved by modifying existing codes for graph partitioning. We compare the performance of our implementation based on the Metis graph partitioning tool [SIAM J. Sci. Comp. 20, 359-392] against one of the best performing algorithms described in this volume.