  With invaluable theoretical and practical benefits, the problem of
partitioning networks for community structures has attracted significant
research attention in scientific and engineering disciplines. In literature,
Newman's modularity measure is routinely applied to quantify the quality of a
given partition, and thereby maximizing the measure provides a principled way
of detecting communities in networks. Unfortunately, the exact optimization of
the measure is computationally NP-complete and only applicable to very small
networks. Approximation approaches have to be sought to scale to large
networks. To address the computational issue, we proposed a new method to
identify the partition decisions. Coupled with an iterative rounding strategy
and a fast constrained power method, our work achieves tight and effective
spectral relaxations. The proposed method was evaluated thoroughly on both real
and synthetic networks. Compared with state-of-the-art approaches, the method
obtained comparable, if not better, qualities. Meanwhile, it is highly suitable
for parallel execution and reported a nearly linear improvement in running
speed when increasing the number of computing nodes, which thereby provides a
practical tool for partitioning very large networks.
