A cutting plane algorithm for modularity maximization problem

Yoichi Izunaga, Yoshitsugu Yamamoto

Research output: Contribution to journalArticlepeer-review

3 Citations (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.

Original languageEnglish
Pages (from-to)24-42
Number of pages19
JournalJournal of the Operations Research Society of Japan
Issue number1
Publication statusPublished - Mar 2017
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • General Decision Sciences
  • Management Science and Operations Research


Dive into the research topics of 'A cutting plane algorithm for modularity maximization problem'. Together they form a unique fingerprint.

Cite this