Optimization Online


A doubly nonnegative relaxation for modularity density maximization

Yoichi Izunaga (s1130131***at***sk.tsukuba.ac.jp)
Tomomi Matsui (matsui.t.af***at***m.titech.ac.jp)
Yoshitsugu Yamamoto (yamamoto***at***sk.tsukuba.ac.jp)

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. However, some authors pointed out drawbacks of the modularity, the main issue of which is resolution limit. Resolution limit refers to the sensitivity of the modularity to the total number of edges in the graph, which leaves small communities not identified and hidden inside larger ones. To overcome this drawback, Li {•it et al.}• have proposed a new measure called modularity density. In this paper, introducing a variant of the semidefinite programming called •mbox{0-1SDP}, we show that the modularity density maximization can be modeled as •mbox{0-1SDP} equivalently. Then we solve a relaxation problem of •mbox{0-1SDP} to obtain an upper bound on the modularity density, and propose a lower bounding algorithm based on the combination of spectral heuristics and dynamic programming.

Keywords: Community detection, Modularity density, 0-1semidefinite programming, Doubly nonnegative relaxation

Category 1: Combinatorial Optimization

Category 2: Linear, Cone and Semidefinite Programming

Citation: Discussion Paper Series No.1339, Department of Social Systems and Management, University of Tsukuba. Accepted in Discrete Applied Mathematics on 16 Sep. 2018.

Download: [PDF]

Entry Submitted: 03/10/2016
Entry Accepted: 03/11/2016
Entry Last Modified: 10/10/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society