Efficient modularity density heuristics for large graphs

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.