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.
Citation
Discussion Paper Series No.1339, Department of Social Systems and Management, University of Tsukuba. Accepted in Discrete Applied Mathematics on 16 Sep. 2018.