关键词: 社会网络, 影响力最大化, 蒙特卡洛模拟, 免疫遗传

Abstract:

The problem of influence maximization is to select a small number of users in a complex social network to maximize the diffusion of influence under a specific propagation model. The greedy Monte Carlo simulation approach theoretically guarantees a near-optimal solution, but it is very inefficient. Although many heuristics appro-aches have been developed without any theoretical guarantee, they greatly reduce the quality of the solution. In order to solve this problem, this paper presents a local probabilistic solution strategy to calculate the in?uence spread of a node set. The performance of this strategy is similar to Monte Carlo simulation. And this paper proposes immune genetic algorithm based influence maximization. Experiments on four real datasets demonstrate the efficiency of the proposed algorithm in solving the influence maximization problem. In terms of influence spread, it has extremely similar performance with the current best performing CELF (cost-effective lazy forward) algorithm, and the running time is about 5 orders of magnitude faster than CELF algorithm.

Key words: social network, influence maximization, Monte Carlo simulation, immune genetic