Efficient modularity density heuristics for large graphs

Citation data:

European Journal of Operational Research, ISSN: 0377-2217, Vol: 258, Issue: 3, Page: 844-865

Publication Year:
2017
Usage 394
Abstract Views 392
Link-outs 2
Captures 16
Readers 14
Exports-Saves 2
Social Media 125
Shares, Likes & Comments 125
Citations 3
Citation Indexes 3
DOI:
10.1016/j.ejor.2016.10.033
Author(s):
Rafael Santiago; Luís C. Lamb
Publisher(s):
Elsevier BV
Tags:
Mathematics; Decision Sciences
article description
Modularity density maximization is a community detection optimization problem which improves the resolution limit degeneracy of modularity maximization. This paper presents seven scalable heuristics for modularity density and compares them with literature results from exact mixed integer linear programming and GAOD, iMeme-Net, HAIN, and BMD- λ heuristics. The results are also compared with CNM and Louvain, which are scalable heuristics for modularity maximization. The results suggest that our seven heuristics are faster than GAOD, iMeme-Net, HAIN, and BMD- λ modularity density heuristics. Our experiments also show that some of our heuristics surpassed the objective function value reported by iMeme-Net, Hain, and BMD- λ for some real graphs. Our seven heuristics were tested with real graphs from the Stanford Large Network Dataset Collection and the experiments show that they are scalable. This feature was confirmed by an amortized complexity analysis which reveals average linear time for three of our heuristics. Hypothesis tests suggest that four proposed heuristics are state-of-the-art since they are scalable for hundreds of thousands of nodes for the modularity density problem, and they find the high objective value partitions for the largest instances. Ground truth experiments in artificial random graphs were performed and suggest that our heuristics lead to better cluster detection than both CNM and Louvain.