Community detection in complex networks using a new agglomerative approach

Majid ARASTEH; Somayeh ALIZADEH

Makale detayları

Community detection in complex networks using a new agglomerative approach

Yazarlar:

Majid ARASTEH | Somayeh ALIZADEH

Yayıncı:

TUBITAK

Dergi:

Turkish Journal of Electrical Engineering and Computer Science 2019 Vol.27 Issue 5, pp.3356-3367

Belge Tipi:

Makale

Yayın Tarihi:

9/2019

Belge Dili:

İngilizce

Document ID (Org No.):

2000733589

Sıklık:

İki Aylık

eISSN:

1303-6203

pISSN:

1300-0632

Özet:

 

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)O(nm)O(nm), where nnn and mmm 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.

Makale detayları

Community detection in complex networks using a new agglomerative approach

Yazarlar: Majid ARASTEH | Somayeh ALIZADEH

Yayıncı: TUBITAK

Dergi: Turkish Journal of Electrical Engineering and Computer Science 2019 Vol.27 Issue 5, pp.3356-3367

Belge Tipi: Makale

Yayın Tarihi: 9/2019

Belge Dili: İngilizce

Document ID (Org No.): 2000733589

Sıklık: İki Aylık

eISSN: 1303-6203

pISSN: 1300-0632

Sayı

Yazarlar:

Majid ARASTEH | Somayeh ALIZADEH

Yayıncı:

TUBITAK

Dergi:

Turkish Journal of Electrical Engineering and Computer Science 2019 Vol.27 Issue 5, pp.3356-3367

Belge Tipi:

Makale

Yayın Tarihi:

9/2019

Belge Dili:

İngilizce

Document ID (Org No.):

2000733589

Sıklık:

İki Aylık

eISSN:

1303-6203

pISSN:

1300-0632