Eur. Phys. J. B (2013) 86: 302
https://doi.org/10.1140/epjb/e2013-40006-7

Regular Article

Computing an upper bound of modularity

¹ Graduate School of Decision Science and Technology, Tokyo Institute of Technology, Ookayama 2-12-1, Meguro-ku, 152-8552 Tokyo, Japan
² Faculty of Science and Technology, Sophia University, Kioi-cho 7-1, Chiyoda-ku, 102-8554 Tokyo, Japan

^a e-mail: miyauchi.a.aa@m.titech.ac.jp

Received: 4 January 2013
Received in final form: 9 May 2013
Published online: 1 July 2013

Abstract

Modularity proposed by Newman and Girvan is a quality function for community detection. Numerous heuristics for modularity maximization have been proposed because the problem is NP-hard. However, the accuracy of these heuristics has yet to be properly evaluated because computational experiments typically use large networks whose optimal modularity is unknown. In this study, we propose two powerful methods for computing a nontrivial upper bound of modularity. More precisely, our methods can obtain the optimal value of a linear programming relaxation of the standard integer linear programming for modularity maximization. The first method modifies the traditional row generation approach proposed by Grötschel and Wakabayashi to shorten the computation time. The second method is based on a row and column generation. In this method, we first solve a significantly small subproblem of the linear programming and iteratively add rows and columns. Owing to the speed and memory efficiency of these proposed methods, they are suitable for large networks. In particular, the second method consumes exceedingly small memory capacity, enabling us to compute the optimal value of the linear programming for the Power Grid network (consisting of 4941 vertices and 6594 edges) on a standard desktop computer.