Community detection in networks based on minimum spanning tree and modularity

• In this paper, we introduce our method for community detection.
• Our method is designed to detect community structure for unweighted and undirected networks.
• We used the minimum spanning tree and nodes dissimilarity to construct communities (create disconnected groups of nodes).
• We used the modularity in the merging process to find the final community structure.
• Our method was tested on both artificial and real networks.

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.