Finding a maximum clique in social networks using a modified differential evolution algorithm

摘要

The relationships of the individuals in social networks give rise to interesting and important features in various fields, such as graph mining and communication networks. Among those useful features are clique structures which represent fully connected relations between members, and the maximum cliques which identify the highest-connected subgroups. In this work, we propose the modified differential evolution algorithm (moDE) for finding a maximum clique in social networks. The moDE solves the constrained continuous optimization problem which is transformed from the discrete maximum clique problem. It uses a new mutation strategy to generate and adjust mutant vectors, mixes two important crossover rates in crossover, and incorporates the extracting and extending clique procedure to increase the performance of clique finding. The algorithm is tested on several social network problems and compared with the previously developed method. The results show that moDE is effective for finding a maximum clique and outperforms the compared method.