Community detection in networks based on minimum spanning tree and modularity

摘要

In this paper we propose a novel splitting and merging method for community detection in which a minimum spanning tree (MST) of dissimilarity between nodes in graph is employed. In the splitting process, edges with high dissimilarity in the MST are removed to construct small disconnected subgroups of nodes from the same community. In the merging process, subgroup pairs are iteratively merged to identify the final community structure maximizing the modularity. The proposed method requires no parameter. We provide a general framework for implementing such a method. Experimental results obtained by applying the method on computer-generated networks and different real world networks show the effectiveness of the proposed method. (C) 2016 Elsevier B.V. All rights reserved.