Community detection in complex networks using a new agglomerative approach

Authors: MAJID ARASTEH, SOMAYEH ALIZADEH

Abstract: Complex networks are used for the representation of complex systems such as social networks. Graph analysis comprises various tools such as community detection algorithms to uncover hidden data. Community detection aims to detect similar subgroups of networks that have tight interconnections with each other while, there is a sparse connection among different subgroups. In this paper, a greedy and agglomerative approach is proposed to detect communities. The proposed method is fast and often detects high-quality communities. The suggested method has several steps. In the first step, each node is assigned to a separated community. In the second step, a vertex is selected randomly and then its neighbors are determined. Then the selected node and its best neighbor will be merged if their merging brings positive gain. The merging of the selected vertex and its best neighbor has more gain than other neighbors. Whenever the merging occurs, the graph will be updated and this process will be continued until all the vertexes are assessed. Furthermore, the computational complexity of the proposed method is $O(nm)$, where $n$ and $m$ refer to the total number of vertexes and edges, respectively. In addition, our proposed method is compared with the Girvan--Newman algorithm and the fast divisive method for community detection. Results show that the proposed method is much faster than them and can detect high-quality communities. Finally, the accuracy of the proposed method is evaluated by using four different measures of purity, F-measure, NMI, and ARI.

Keywords: Complex networks, social networks, community detection, agglomerative approach

Full Text: PDF