Title: Overlapping community detection with a novel hybrid metaheuristic optimisation algorithm

Authors: Imane Messaoudi; Nadjet Kamel

Addresses: LRIA Laboratory, Department of Computer Science, Universite de Sciences et de la Technology Houari Boumediene, BP 32 El alia 16111 Bab ezzouar, Algiers, Algeria ' Department of Computer Science, Faculty of Sciences, Université Ferhat Abbas Setif 1, Setif, Algeria

Abstract: Social networks are ubiquitous in our daily life. Due to the rapid development of information and electronic technology, social networks are becoming more and more complex in terms of sizes and contents. It is of paramount significance to analyse the structures of social networks in order to unveil the myth beneath complex social networks. Network community detection is recognised as a fundamental tool towards social networks analytics. As a consequence, numerical community detection methods are proposed in the literature. For a real-world social network, an individual may possess multiple memberships, while the existing community detection methods are mainly designed for non-overlapping situations. With regard to this, this paper proposes a hybrid metaheuristic method to detect overlapping communities in social networks. In the proposed method, the overlapping community detection problem is formulated as an optimisation problem and a novel bat optimisation algorithm is designed to solve the established optimisation model. To enhance the searchability of the proposed algorithm, a local search operator based on tabu search is introduced. To validate the effectiveness of the proposed algorithm, experiments on benchmark and real-world social networks are carried out. The experiments indicate that the proposed algorithm is promising for overlapping community detection.

Keywords: overlapping community; modified density; Tabu search; TS; Bat algorithm; BA; link clustering; social network.

DOI: 10.1504/IJDMMM.2020.105601

International Journal of Data Mining, Modelling and Management, 2020 Vol.12 No.1, pp.118 - 139

Accepted: 08 Oct 2018
Published online: 03 Mar 2020 *

Full-text access for editors Access for subscribers Purchase this article Comment on this article