2012/2013
Revealing network communities with a nonlinear programming method
Information Sciences, 229: 18-28
| Author(s) | Wenye Li |
|---|---|
| Summary | 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.
|