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

摘要：

影响力最大化问题是在复杂社会网络中选择一小部分用户在特定传播模型下最大化影响扩散。基于贪心的蒙特卡洛模拟方法在理论上保证近乎最优的解决方案，但算法运行效率很低。虽然已经开发出许多没有理论保证的启发式方法，但都大大降低了解决方案的质量。为解决该问题，提出局部概率解策略计算节点集的影响力，其性能近似于蒙特卡洛模拟，并且提出基于免疫遗传的影响力最大化算法。在4个真实数据集上的实验表明所提算法在解决影响力最大化问题上的高效性。在影响力传播范围上，和当前表现最好的CELF算法有极其相近的性能，且运行效率比CELF算法快大约5个数量级。

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