A cutting plane algorithm for modularity maximization problem

Yoichi Izunaga, Yoshitsugu Yamamoto

研究成果: ジャーナルへの寄稿学術誌査読

3 被引用数 (Scopus)

抄録

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.

本文言語英語
ページ(範囲)24-42
ページ数19
ジャーナルJournal of the Operations Research Society of Japan
60
1
DOI
出版ステータス出版済み - 3月 2017
外部発表はい

!!!All Science Journal Classification (ASJC) codes

  • 決定科学一般
  • 経営科学およびオペレーションズ リサーチ

フィンガープリント

「A cutting plane algorithm for modularity maximization problem」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。

引用スタイル