An Overlapping Community Detection Based Multi-Objective Evolutionary Algorithm for Diversified Social Influence Maximization

摘要

Influence maximization refers to selecting a group of nodes from a social network, which obtains the largest influence spread under a cascade model. However, most of the existing works only focused on the influence and ignored the diversity of influenced crowd. Thus, scholars have raised the issue of diversified social influence maximization recently, using the category information of nodes to design diversity indicator and introducing a trade-off parameter to balance the two objectives influence and diversity as one single objective for optimization. In fact, the category information of nodes in the network is usually difficult to be collected, thus the definition of diversity based on nodes’ categories is not very general and accurate. In addition, it is very difficult to set the trade-off parameter, especially when there is no prior knowledge in real applications. To this end, we employ overlapping community structure information to design the diversity of nodes without any node’s additional (e.g. category) information. Due to the two objectives of influence and diversity may be conflicting, a multi-objective evolutionary algorithm named MOEA-DIM is proposed to optimize the two objectives simultaneously, which does not need to set the tradeoff parameter between the two objectives. In MOEA-DIM, a network reduction strategy based on overlapping community structure is suggested to greatly reduce the search space. In addition, a population initialization strategy based on random walk is designed to accelerate the convergence of the algorithm. Experiments on six real-world datasets show that the proposed algorithm MOEA-DIM has promising performance in terms of both effectiveness and efficiency.