A CUTTING PLANE ALGORITHM FOR MODULARITY MAXIMIZATION PROBLEM

• Izunaga Yoichi

  The Institute of Behavioral Sciences

• Yamamoto Yoshitsugu

  Shizuoka University

抄録

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.

収録刊行物

• 日本オペレーションズ・リサーチ学会論文誌

  日本オペレーションズ・リサーチ学会論文誌 60 (1), 24-42, 2017

  公益社団法人 日本オペレーションズ・リサーチ学会

キーワード

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

詳細情報

• CRID: 1390282679086925824
• NII論文ID: 130005316100
• NII書誌ID: AA00703935
• DOI: 10.15807/jorsj.60.24
• ISSN: 21888299
• ISSN: 04534514
• HANDLE: 2324/4755266
• NDL書誌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
• 本文言語コード: en
• データソース種別:
  • JaLC
  • IRDB
  • NDL
  • Crossref
  • CiNii Articles
• 抄録ライセンスフラグ: 使用不可