A New overlapping community detection algorithm based on similarity of neighbors in complex networks

Çetin, Pelin ; Emrah Amrahov, Sahin

Kybernetika, Tome 58 (2022) no. 2, pp. 277-300.

Résumé

Community detection algorithms help us improve the management of complex networks and provide a clean sight of them. We can encounter complex networks in various fields such as social media, bioinformatics, recommendation systems, and search engines. As the definition of the community changes based on the problem considered, there is no algorithm that works universally for all kinds of data and network structures. Communities can be disjointed such that each member is in at most one community or overlapping such that every member is in at least one community. In this study, we examine the problem of finding overlapping communities in complex networks and propose a new algorithm based on the similarity of neighbors. This algorithm runs in $ O(m \textit{lg} m) $ running time in the complex network containing $ m $ number of relationships. To compare our algorithm with existing ones, we select the most successful four algorithms from the Community Detection library (CDlib) by eliminating the algorithms that require prior knowledge, are unstable, and are time-consuming. We evaluate the successes of the proposed algorithm and the selected algorithms using various known metrics such as modularity, F-score, and Normalized Mutual Information. In addition, we adapt the coverage metric defined for disjoint communities to overlapping communities and also make comparisons with this metric. We also test all of the algorithms on small graphs of real communities. The experimental results show that the proposed algorithm is successful in finding overlapping communities.

Détail

DOI : 10.14736/kyb-2022-2-0277

Classification : 94C15
Keywords: overlapping community detection; complex networks; graph approach; similarity approach; community metrics