A CUTTING PLANE ALGORITHM FOR MODULARITY MAXIMIZATION PROBLEM

• Izunaga Yoichi

  The Institute of Behavioral Sciences

• Yamamoto Yoshitsugu

  Shizuoka University

Abstract

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.

Journal

• Journal of the Operations Research Society of Japan

  Journal of the Operations Research Society of Japan 60 (1), 24-42, 2017

  The Operations Research Society of Japan

Keywords

• Combinatorial optimization
• community detection
• modularity maximization
• set partitioning
• cutting planes

Details

• CRID: 1390282679086925824
• NII Article ID: 130005316100
• NII Book ID: AA00703935
• DOI: 10.15807/jorsj.60.24
• ISSN: 21888299
• ISSN: 04534514
• HANDLE: 2324/4755266
• NDL BIB ID: 027850694
• Web Site: https://ndlsearch.ndl.go.jp/books/R000000004-I027850694
• Web Site: https://www.jstage.jst.go.jp/article/jorsj/60/1/60_24/_pdf
• Text Lang: en
• Data Source:
  • JaLC
  • IRDB
  • NDL
  • Crossref
  • CiNii Articles
• Abstract License Flag: Disallowed