An Improved Artificial Bee Colony Algorithm for Community Detection in Bipartite Networks

摘要

In the past few decades, although people have conducted in-depth research on community detection in one-mode networks, community detection in bipartite networks has not been extensively researched. In this paper, we propose an improved artificial bee colony algorithm named IABC-BN, which is used to detect the communities in two-mode graphs (i.e. bipartite graphs) with two kinds of vertices in the cluster (i.e. community). Firstly, this paper proposed a novel population initialization process of artificial bee colony (ABC) method for two-mode graph cluster identification. This initialization method can improve the diversity of initial population of ABC and speed up its convergence rate. Secondly, in the employed bee search step of the algorithm, a new combinatorial search equation is proposed. This equation is guided by the global optimal solution and the better neighbour solution of the current solution. By using this combination equation and the increased parameter perturbation frequency, the exploitation ability of the algorithm is further enhanced. Thirdly, in the onlooker bees step, another new combination search equation is also proposed. This equation improves the exploitation level of the algorithm, and an opposition based studying method is employed to promote the exploitation ability of the algorithm. Lastly, in scout bee stage, a probability threshold $eta $ is introduced to enhance the exploration ability of the algorithm and improve the population diversity of the algorithm. To our knowledge, the IABC-BN method presented in this paper is the first ABC method used to cluster identification in two-mode graphs with two kinds of vertices in the cluster. For verifying the accuracy of the results of the proposed method, a large number of experiments are carried out making use of synthetic bipartite graphs and real bipartite graphs. The test outcomes show that this algorithm is an excellent algorithm for cluster discovery in two-mode graph.