Discovering the Maximum Clique in Social Networks Using Artificial Bee Colony Optimization Method

摘要

Social networks are regarded as a specific type of social interactions which include activities such as making somebody’s acquaintance, making friends, cooperating, sharing photos, beliefs, and emotions among individuals or groups of people. Cliques are a certain type of groups that include complete communications among all of its members. The issue of identifying the largest clique in the network is regarded as one of the notable challenges in this domain of study. Up to now, several studies have been conducted in this area and some methods have been proposed for solving the problem. Nevertheless, due to the NP-hard nature of the problem, the solutions proposed by the majority of different methods regarding large networks are not sufficiently desirable. In this paper, using a meta-heuristic method based on Artificial Bee Colony (ABC) optimization, a novel method for finding the largest clique in a given social network is proposed and simulated in Matlab on two dataset groups. The former group consists of 17 standard samples adopted from the literature whit know global optimal solutions, and the latter group includes 6 larger instances adopted from the Facebook social network. The simulation results of the first group indicated that the proposed algorithm managed to find optimal solutions in 16 out of 17 standard test cases. Furthermore, comparison of the results of the proposed method with Ant Colony Optimization (ACO) and the hybrid PS-ACO method on the second group revealed that the proposed algorithm was able to outperform these methods as the network size increases. The evaluation of five DIMACS benchmark instances reveals the high performance in obtaining best-known solutions.