Title: Mod-Müllner: an efficient algorithm for hierarchical community analysis in large networks

Authors: Brieuc Conan-Guez; Manh Cuong Nguyen

Addresses: Laboratory of Theoretical and Applied Computer Science (LITA), Université de Lorraine, EA 3097, Ile du Saulcy, 57045 Metz, France ' Laboratory of Theoretical and Applied Computer Science (LITA), Université de Lorraine, EA 3097, Ile du Saulcy, 57045 Metz, France

Abstract: In this work, we propose a new efficient agglomerative algorithm for hierarchical clustering analysis (HCA) of large networks. This algorithm, called Mod-Müllner, is an adaptation of an existing algorithm proposed by Müllner in 2011 and initially dedicated to HCA of pairwise dissimilarities. Mod-Müllner performs a greedy optimisation of the modularity, a widely used measure for network partitioning. We show that thanks to adapted data structures, Mod-Müllner achieves lower running times than other agglomerative algorithms, while producing comparable solutions. Finally, Mod-Müllner is compared to the Louvain method on simulated and real-world datasets. For both methods, the improved solutions obtained through single-level and multilevel refinements are studied.

Keywords: meta-graphs; network partitioning; community detection; modularity; hierarchical clustering analysis; HCA; social networking; large networks; greedy optimisation; network communities.

DOI: 10.1504/IJSNM.2015.072301

International Journal of Social Network Mining, 2015 Vol.2 No.2, pp.133 - 157

Accepted: 27 Mar 2015
Published online: 08 Oct 2015 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article