社交网络中延迟竞争传播的研究进展

李 阳

(国家信息中心 北京 100045)

1 时延竞争影响力概述

1.1 研究背景

现实世界中2种及2种以上实体(如产品或观点)竞争传播的情况普遍存在，社交网络中二元甚至多元竞争研究在市场营销、谣言抑制、病毒传播等场景中得到了深化应用.例如，某公司发布了新款手机，一段时间后另一家公司也开发了新款手机参与市场竞争；谣言信息传播一段时间后，辟谣机制展开竞争传播以消除负向影响.这种竞争传播过程往往是存在时滞的，称为时延竞争.如何开展时延竞争下的影响力传播研究，在社交网络应用中具有重要的现实意义.

1.2 时延竞争影响力问题

以上研究即是时延竞争的影响力最大化问题.以二元正负信息竞争为例，给定社交网络图结构(其中用节点代表用户，用边代表用户之间的关系)和竞争传播模型，节点可以表示为正向激活态、负向激活态和未激活态.问题可以描述为：当负向信息传播时间t(或已形成一定规模的负向节点集kN)，如何发现一个规模为kP的正向节点集(也称为种子集)竞争传播，将影响力最大化到社交网络上的其他用户，实现抑制负向影响力的效果.

2 时延竞争影响力研究进展

有关时延竞争影响力传播的研究最初从经济领域展开；随着理论聚焦的逐渐深入，疾病模型、信息模型得到广泛的研究，在理论建模和量化计算方面取得了一系列的研究成果.

2.1 经济模型

时延竞争研究源于经济学领域的斯塔克尔伯格领导模型[1-2]，出自1934年德国经济学家斯塔克尔伯格的著作“Marktform und Gleichgewicht”.该模型主要描述的是商业市场中，主导企业(Leader)占据市场先发位置，跟随企业(Follower)根据Leader对于己方决策的反应调整至最优决策以便最大化收益.这比较符合时延竞争传播场景中，面对先行启动的信息传播，后序启动的节点集如何选择策略以符合己方最大化传播.之后，Bharathi等人[3]提出一种适用于后序启动节点集的近似算法以解决信息竞争传播问题.Kostka等人[4]基于定位理论概念探讨了确定性扩展模型，认为先行节点的发现算法是一个NP-Hard问题.Clark等人[5]采用马尔可夫扩散模型对时序竞争问题进行研究，表明基于马尔可夫扩散模型的目标函数具有子模特性.Hemmati等人[6]在一个双层规划模型上考虑时序竞争的2类节点，这需要采用确定性线性阈值扩散模型进行研究.Taninmis等人[7]提出采用双层模型解决时序竞争问题.

经济模型给时延竞争研究带来了新颖参考，对于研究后序节点的竞争策略提供了应用视角和案例借鉴，也为研究方向的拓展提供了基础.

2.2 疾病模型

一些研究者聚焦于病毒传播机制的拓展研究，目前比较常用的是采用免疫策略控制疾病的传播：Pastor-Satorras等人[8]基于无标度网络特性分析了目标免疫策略；Cohen等人[9]依靠局部信息提出熟人免疫策略.部分研究者从节点免疫的角度出发进行研究：Kitsak等人[10]认为最有影响力的节点位于网络的核心层，随后提出了基于中心免疫的策略[11-12]；Zhang等人[13-14]研究如何选择一个节点集，使得疾病传播过程中网络中被感染的节点最小化；Lü等人[15]对网络拓扑中关键节点的识别进行梳理回顾，为节点免疫提供了思路.还有研究者采用轻量级的免疫方式，通过对网络中的特定边进行阻断来有效降低节点之间的交互和传播速度：Kimura等人[16-17]、Tong等人[18]和Kuhlman等人[19]研究面向边级别的免疫策略对抗疾病传播、计算机病毒的扩散以及谣言的传播；Khalil等人[20]通过剪枝网络结构来抑制恶意信息的传播.

随着网络的动态变化，一些跟进的免疫策略也在不断拓展.Gómez等人[21]采用微观马尔可夫链方法构建动力学方程，分析了疾病传播过程中的关键特性.Wu等人[22]与Yang等人[23]基于传播模型研究了动态免疫方法，但是他们的研究主要聚焦于优化动态系统的参数，而非对网络结构中的最优节点进行免疫.

疾病模型在竞争传播研究中得到广泛应用，面向节点和面向边的免疫策略被持续提出，相关实验成果为时延竞争的趋势分析提供了支撑，如何继续下沉节点之间的交互成为难点所在.

2.3 信息模型

在竞争影响力最大化研究[24]中，自身影响力最大化的竞争传播不一定导致对手影响力最小化.尤其在未给定先行种子节点策略的情况下，竞争影响力最大化问题不具备子模单调性，难以确定最优解的计算[25].

在最初的时延竞争最大化研究中，Carnes等人[26]基于独立级联(independent cascade, IC)模型进行扩展，分别提出距离模型和波传播模型来刻画2个产品在网络中的竞争传播.研究显示对于Leader节点的最优选择策略是具有高度数的节点，对于Follower节点的选择策略证明属于NP-Hard问题，但是这2个拓展模型均假设节点间距为1，限制了实际场景中的应用范围.Bharathi等人[27]基于IC模型进行扩展提出了CP(competing processes)模型，在模型中引入积极影响和消极影响2个对立的传播过程，但文献提出的先行者最优的动态规划方法仅适用于树状图，给实践应用带来一定的局限性.

之后，研究者们逐渐加大了在实践方面的探索，在数据场景中进行定量分析，取得了一系列的研究成果：Chen等人[28]根据真实网络中信息扩散存在的时滞现象，提出面向竞争传播的IC-M模型，该模型在IC模型的基础上给每条边(v,w)引入1个相遇概率m，该概率值决定了节点v与w相遇的频度；Lin等人[29]考虑到种子节点选择的多轮次场景需求，提出基于Q学习模型计算竞争方的最优策略，通过评估最终激活节点规模来筛选获胜的竞争方；Bozorgi等人[30]基于竞争型线性阈值(linear threshold, LT)模型进行扩展，通过计算每个节点的影响力增益并基于社区划分的方法选择后序启动节点集；Li等人[31]考虑到时间限制和时间延迟对信息传播的影响，提出基于CELF策略的贪心算法降低蒙特卡洛的模拟次数，在真实数据集上的实验显示该算法优于常见的启发式算法；Pham等人[32]在时间限制下提出基于轮询的近似算法，实验显示该算法在竞争影响力问题上具有较好的可扩展性；Chen[33]等人基于竞争型转移概率提出最低代价的影响力最大化算法，通过对每个节点设置一维向量来标记竞争选择的概率，实验显示该算法具有极好的传播范围，同时也维持了合理的运行时间.

一些研究者从抑制对方影响力传播的角度出发展开竞争传播研究工作.加州大学的Budak等人[34]于 2011年首先基于IC模型进行扩展，研究如何选择最优策略传播权威信息来抑制已存在谣言的扩散问题.他们认为早期传播范围的模拟计算缺乏约束条件，将导致全网模拟并消耗大量的运行时间，并证明了抑制谣言传播问题可以采用贪心算法获得近似最优解.Nguyen等人[35]面向社交网络研究错误信息的抑制传播问题，即如何在时间t内找到1个初始节点集传播正确信息，使得最终错误消息的传播范围小于给定比例.Wang等人[36]研究了动态阻断算法，且分析了信息扩散阶段的动态特征，但在实验中仍采用了原始信息传播模型.Rawale等人[37]在贪心算法的基础上提出1种动态阻断算法，并给每个节点分配1个可容忍的时间阈值，该算法可以在每个轮次对筛选的节点集进行增量式阻断.Yan等人[38]认为在Follower节点先行启动的情况下，选择后序节点集需要考虑阈值限定下的最小代价问题.

还有一些研究者聚焦时间因素对竞争传播的影响机理：Gomez-Rodriguez等人[39]认为以往工作较少考虑影响策略选择的相关因素，研究时间因素在信息扩散中的作用，提出基于连续时间的影响力传播模型，对时延竞争传播模型研究提供了较好的借鉴；Ribeiro等人[40]主要研究竞争信息的延迟传播问题，分析处于激活状态的节点如何被竞争信息再次激活，并提出在此情况下影响力传播计算不再具有子模特性和单调性；Yuan等人[41]提出部分反馈模型(partial-feedback model)，认为在时间间隔内持续选择种子节点可以最小的节点规模实现最大化的影响力传播；Wang等人[42]提出基于流体扩散的影响力传播模型，通过运用流体动力学理论揭示扩散过程的时间演化.

针对基于信息模型的时延竞争，研究者们从微观交互机理和宏观趋势分析2方面进行了理论探讨和实验测试，并结合时间因素对竞争传播进行对比分析.随着场景需求的不断扩展，需要更多的启发式方法来进行深入研究.

3 未来展望

3.1 总 结

社交网络中的时延竞争在市场营销、谣言抑制等领域具有现实需求，尤其在二元甚至多元信息的竞争传播中，后序启动的竞争传播往往存在滞后性.研究者们从经济模型、疾病模型、信息模型等角度展开时延竞争影响力传播分析，在理论模型、方法验证、场景应用等方面取得了一系列的研究成果.但是，当前研究还存在一定的挑战：一方面当前研究多聚焦于根据先行者的策略来选择后序节点集，这些都是确定性的信息源，很多场景中先行者的策略是未知的、不确定的；另一方面当前研究多聚焦于单一网络的竞争传播，但往往时滞的竞争传播会跨网跨域传播，涉及传播模型的竞争机制更新等.

3.2 展 望

未来围绕影响力的时延竞争传播还存在继续深入的研究点，如时延建模的刻画、不确定信息源策略选择、跨网跨域传播的协同等.

1) 时延建模的刻画.

目前的时延建模过程主要基于IC模型和LT模型的扩展应用.随着研究的深入：一方面，当前研究聚焦于时序状态下先行传播的固化扩散，实际场景中信息传播存在级联的动态衰减，不是恒定不变的；另一方面，研究者们已经对考虑时延因素[43-44]的影响力传播进行分析，下一步还需立足节点之间的拓扑距离、社区距离等拓扑变化，分析时间因素对传播概率以及传播模型的影响机理[45-46]，进一步提升面向实际场景的适应性.

2) 不确定信息源策略选择.

目前主要围绕先行者预知的传播策略，研究后序节点如何开展竞争传播.但实际场景中先行者的传播策略大多是未知的.随着研究的深入：一方面，在探索未知的先行者传播源时，如何利用网络局部拓扑的先验知识进行学习，对于网络关键节点的推断至关重要；另一方面，如何提出自适应的后序竞争策略来提升竞争传播的针对性和时效性，都需要进一步的场景化探索与验证.

3) 跨网跨域传播的协同.

目前的信息传播过程主要围绕单一网络结构进行，但实际场景中的信息传播是跨网跨域传播[47-48].随着研究的深入：一方面，跨网跨域的网络结构可能是同质的，也可能是异质的，异质网络结构对竞争传播的影响机理还需要进一步量化计算；另一方面，跨网跨域的网络结构也在不断生长和演化，多重网络演化对传播机理、传播模式、传播规律等的影响问题需要进一步的统计和探索.