Community detection in complex networks using a new agglomerative approach

Abstract

Complex networks are used for the representation of complex systems such as social networks. Graph analysiscomprises various tools such as community detection algorithms to uncover hidden data. Community detection aims todetect similar subgroups of networks that have tight interconnections with each other while, there is a sparse connectionamong different subgroups. In this paper, a greedy and agglomerative approach is proposed to detect communities. Theproposed method is fast and often detects high-quality communities. The suggested method has several steps. In thefirst step, each node is assigned to a separated community. In the second step, a vertex is selected randomly and then itsneighbors are determined. Then the selected node and its best neighbor will be merged if their merging brings positivegain. The merging of the selected vertex and its best neighbor has more gain than other neighbors. Whenever the mergingoccurs, 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 vertexesand edges, respectively. In addition, our proposed method is compared with the Girvan–Newman algorithm and thefast divisive method for community detection. Results show that the proposed method is much faster than them andcan detect high-quality communities. Finally, the accuracy of the proposed method is evaluated by using four differentmeasures of purity, F-measure, NMI, and ARI.