Efficient modularity density heuristics for large graphs

Rafael Santiago and Luís C. Lamb

European Journal of Operational Research, 2017, vol. 258, issue 3, 844-865

Abstract: 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.

Keywords: Heuristics; Clustering; Modularity density maximization; Large graphs (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221716308670
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:258:y:2017:i:3:p:844-865

DOI: 10.1016/j.ejor.2016.10.033

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().