TY - JOUR
T1 - A cutting plane algorithm for modularity maximization problem
AU - Izunaga, Yoichi
AU - Yamamoto, Yoshitsugu
N1 - Publisher Copyright:
© The Operations Research Society of Japan.
PY - 2017/3
Y1 - 2017/3
N2 - Modularity proposed by Newman and Girvan is the most commonly used measure when the nodes of a graph are grouped into communities consisting of tightly connected nodes. We formulate the modularity maximization problem as a set partitioning problem, and propose an algorithm for the problem based on the linear programming relaxation. We solve the dual of the linear programming relaxation by using a cutting plane method. To mediate the slow convergence that cutting plane methods usually suffer, we propose a method for finding and simultaneously adding multiple cutting planes.
AB - Modularity proposed by Newman and Girvan is the most commonly used measure when the nodes of a graph are grouped into communities consisting of tightly connected nodes. We formulate the modularity maximization problem as a set partitioning problem, and propose an algorithm for the problem based on the linear programming relaxation. We solve the dual of the linear programming relaxation by using a cutting plane method. To mediate the slow convergence that cutting plane methods usually suffer, we propose a method for finding and simultaneously adding multiple cutting planes.
UR - http://www.scopus.com/inward/record.url?scp=85014415731&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85014415731&partnerID=8YFLogxK
U2 - 10.15807/jorsj.60.24
DO - 10.15807/jorsj.60.24
M3 - Article
AN - SCOPUS:85014415731
SN - 0453-4514
VL - 60
SP - 24
EP - 42
JO - Journal of the Operations Research Society of Japan
JF - Journal of the Operations Research Society of Japan
IS - 1
ER -