ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2016, Vol. 53 ›› Issue (3): 601-610.doi: 10.7544/issn1000-1239.2016.20148341

• 人工智能 • 上一篇    下一篇

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

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

  1. 1(云南大学软件学院 昆明 650091); 2(云南省软件工程重点实验室 昆明 650091); 3(云南大学信息学院 昆明 650091) (lijin@ynu.edu.cn)
  • 出版日期: 2016-03-01
  • 基金资助: 
    国家自然科学基金项目(61562091,61472345,61263043);云南省自然科学基金项目(2014FA023,201501CF00022);云南大学骨干教师培养计划基金项目(XT412003);云南大学创新团队建设项目(XT412011)

Robust Influence Blocking Maximization in Social Networks

LiJin1,2,YueKun2,3,ZhangDehai1,2,LiuWeiyi3   

  1. 1(School of Software, Yunnan University, Kunming 650091); 2(Key Laboratory of Software Engineering of Yunnan Province, Kunming 650091); 3(School of Information Science and Engineering, Yunnan University, Kunming 650091)
  • Online: 2016-03-01

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

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

Abstract: Influence 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 words: social networks, influence blocking maximization, minmax principle, approximation algorithms, submodular function

中图分类号: