Revealing network communities with a nonlinear programming method

The detection of network communities has attracted significant research attention lately. To discover such structures, a mathematical measure known as modularity is often used for optimization. Unfortunately, the optimization is NP-hard, and approximated solutions have to be sought for large networks. In this paper, we propose a nonlinear programming method for optimization that is based on the augmented Lagrangian technique. We further identify the inherent connection between the proposed method and positive semi-definite programming and its low-rank reduction, which helps to justify the performance of the method. Compared with previously published approaches, the proposed method is empirically efficient and effective at detecting underlying network communities.