•  
  •  
 

Turkish Journal of Electrical Engineering and Computer Sciences

DOI

10.3906/elk-1902-163

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

First Page

3356

Last Page

3367

Download

Share

COinS