Multiobjective Immune Algorithm For Community Detection In Dynamic Networks

Nowadays, as the emergence of social network research, the community detection for social network becomes the focus of research gradually. Community structure is one of the most important topology attributes of social network, which reveals its hidden rules and behavioral characteristics. However, most of the social networks are dynamic in real world, and their community structure may evolve over time so that pose more challenging tasks than in static ones. The research of community detection for dynamic social network is still in its initial stage, so the proposed algorithms are rare at present. In order to overcome the drawbacks of the traditional methods, which can’t identify the number of community automatically, and need to fix the weight parameter to trade off the two objectives, three new community detection algorithms based on the Multiobjective Immune Algorithm are proposed in this paper to deal with the community detection for dynamic networks. The main works in this paper are as follows:(1) Based on the artifical immune system’s multiobjective optimization algorithm, i.e. Nondominated Neighbor Immune Algorithm(NNIA), a new community detection algorithm for dynamic network is proposed in this paper. In order to overcome the drawbacks of the traditional algorithms, the proposed algorithm takes the Modularity and Normalized Mutual Information as the objective functions to be optimized, moreover, adopts the Community Score(CS) as the best solution selection criterion. The new algorithm can not only find the better solution and detect the more accurate community structure, but also the obtained results will be more steadily than the compared algorithms.(2) According to the shortcoming of the Nondominated Neighbor Immune Algorithm which can’t search the individuals in the sparse area completely, Lamarckian learning is introduced into it, a community detection algorithm for dynamic network based on the Lamarckian multiobjective immune algorithm is proposed. The local search strategy is added to NNIA in the procedure of the nondominated population produced. Thereafter, the new algorithm can strengthen the global optimization ability and accelerate convergence rapidly. Through the simulation test, it proves the new algorithm which added the local search can further improve the performance of the algorithm.(3) In order to overcome the defects of the locus-based encoding method and the un-control of the local search direction, a new community detection algorithm based on multiobjective memetic algorithm for dynamic network is proposed in this paper. The new algorithm adopts the direct encoding method and pre-proccess the initial population using the simple heuristic research. Moreover, according to the character of the direct encoding method, the new algorithm adopts the two-way crossing over and one-point mutation method to replace the recombination and hypermutation. In order to improve the performance of the new algorithm, the local search procedure based on multiobjective memetic algorithm is added to it. When select the best solution, we use the modularity density as the criterion to make up for the modularity. Through a series of experiments, it proves the new method can not only find the true community structure, but also capture the evolution of the particular community. In addition, it is more steadily than the compared algorithms.