高级检索
    李劲, 岳昆, 张德海, 刘惟一. 社会网络中影响力传播的鲁棒抑制方法[J]. 计算机研究与发展, 2016, 53(3): 601-610. DOI: 10.7544/issn1000-1239.2016.20148341
    引用本文: 李劲, 岳昆, 张德海, 刘惟一. 社会网络中影响力传播的鲁棒抑制方法[J]. 计算机研究与发展, 2016, 53(3): 601-610. DOI: 10.7544/issn1000-1239.2016.20148341
    LiJin, YueKun, ZhangDehai, LiuWeiyi. Robust Influence Blocking Maximization in Social Networks[J]. Journal of Computer Research and Development, 2016, 53(3): 601-610. DOI: 10.7544/issn1000-1239.2016.20148341
    Citation: LiJin, YueKun, ZhangDehai, LiuWeiyi. Robust Influence Blocking Maximization in Social Networks[J]. Journal of Computer Research and Development, 2016, 53(3): 601-610. DOI: 10.7544/issn1000-1239.2016.20148341

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

    Robust Influence Blocking Maximization in Social Networks

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

       

      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.

       

    /

    返回文章
    返回