A multi-objective bat algorithm for community detection on dynamic social networks

摘要

Many evolutionary algorithms have been proposed to deal with the problem of community detection in social dynamic networks. Some algorithms need to fix parameters in advance; others use a random process to generate the initial population and to apply the algorithm operators. These drawbacks increase the search space and cause a high spatial and temporary complexity. To overcome these weaknesses, we propose in this paper a novel multi-objective Bat Algorithm that uses Mean Shift algorithm to generate the initial population, to obtain solutions of high quality. In our proposal, Bat Algorithm simultaneously optimizes the modularity density and the normalized mutual information of the solutions as objective functions. The operators of the algorithm are applied to the problem of community detection in social dynamic networks by giving another sense to the velocity, frequency, loudness and the pulse rate of natural Bat. The algorithm keeps the principal of the Mean Shift algorithm to generate new solution and avoid the random process by defining a new mutation operator. The algorithm does not need to the non-dominated sorted approach or the crowding distance, but it attributes a weight to each objective function. The method is tested on artificial and real dynamic networks and the experiments show satisfactory results in terms of normalized mutual information, modularity and error rate.