李　劲　岳　昆　张德海　刘惟一

1(云南大学软件学院　昆明　650091)

2(云南省软件工程重点实验室　昆明　650091)

3　　　(云南大学信息学院　昆明　650091)

(lijin@ynu.edu.cn)



社会网络中影响力传播的鲁棒抑制方法

李劲1,2岳昆2,3张德海1,2刘惟一3

1(云南大学软件学院昆明650091)

2(云南省软件工程重点实验室昆明650091)

3(云南大学信息学院昆明650091)

(lijin@ynu.edu.cn)

Robust Influence Blocking Maximization in Social Networks

Li Jin1,2, Yue Kun2,3, Zhang Dehai1,2, and Liu Weiyi3

1(SchoolofSoftware,YunnanUniversity,Kunming650091)

2(KeyLaboratoryofSoftwareEngineeringofYunnanProvince,Kunming650091)

3(SchoolofInformationScienceandEngineering,YunnanUniversity,Kunming650091)

AbstractInfluence blocking maximization is currently a problem of great interest in the research area of social networks. Existing influence blocking methods assume negative influence sources are definitely known or non-adversarial. However, in real applications, it is hard to obtain the accurate information of influence sources. In addition, adversarial spreader may strategically select the seeds to maximize negative spread. In this paper, we aim to tackle the problems of influence blocking maximization with uncertain and strategic negative influence sources respectively. First, in order to increase the efficiency of the algorithms for mining blocking seeds, we discuss approximate estimation of the influence spread of negative seeds under the competitive linear threshold model. Based on the estimation, we propose a blocking seeds mining algorithm under the situation of finite uncertain and negative influence sources to maximize the expected influence blocking utility. In adversarial influence spread situations, one entity strategically attempts to maximize negative influence spread while the other one tries to block the negative propagation of its competing entity as much as possible by selecting a number of seed nodes that could initiate its own influence propagation. We model the interaction as a game and propose a polynomial time approximate algorithm for solving random blocking strategy based on min-max principle to decrease the worst negative influence spread. Finally, we make experiments on real data sets of social networks to verify the feasibility and scalability of the proposed algorithms.

Key wordssocial networks; influence blocking maximization; minmax principle; approximation algorithms; submodular function

摘要社会网络中影响力传播的有效抑制是当前社会网络影响力传播机制研究关注的问题之一.针对不确定性、策略性负影响源的影响力传播抑制，讨论社会网络中影响力传播的鲁棒抑制问题.首先，作为提高算法运行效率的有效途径，讨论在竞争性线性阈值传播模型下，负种子集传播能力的近似估计方法，以此为基础，提出不确定性负影响源情况下，期望抑制效果最大化的抑制种子集挖掘算法.然后，对于策略性传播源，以最小化最坏情况下的影响力传播范围为目标，基于极小极大优化作为抑制决策准则，提出了一个随机抑制策略的多项式时间近似求解算法.最后，在真实的社会网络数据集上，通过实验验证了所提出方法的有效性.

关键词社会网络；影响力抑制最大化；极小极大原理；近似算法；次模函数

近年来，许多学者针对面向多信息源发布的信息全局传播机制及其预测模型，以影响力传播范围及传播速度最大化为目标的关键结点集选取等问题开展了积极探索，并取得了一系列成果，极大地促进了社会网络影响力传播机制问题的研究[1-7].

然而，由……