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

李 阳

(国家信息中心 北京 100045)

1 竞争影响力概述

1.1 研究背景

随着社交网络中应用场景的不断扩展，信息传播从最初的单一传播向发布、转发、评论以及舆论场演变，市场营销从如何挖掘有限的种子用户来最大化商品促销转变为不同商家之间产品的竞争营销，此外还有候选人在竞选中的竞争宣传、恶意信息的散布与辟谣等.这些信息在传播过程中相互作用，形成了二元甚至多元信息的竞争传播.信息的竞争传播机制与演化规律探索成为重要的研究课题.

1.2 竞争影响力问题

上述研究即是竞争影响力[1]最大化的常见应用，目前主要分为2类[2]：一类是促进己方影响力最大化传播，另一类是抑制对手影响力最小化传播.当未给定初始种子节点策略时，竞争影响力最大化问题不具备子模单调性，难以确定最优解的计算[3].以二元正负信息竞争为例，给定社交网络图结构(其中用节点代表用户，用边代表用户之间的关系)和竞争传播模型，节点可以表示为正向激活态、负向激活态和未激活态.当初始节点传播某负向信息时，竞争影响力最大化问题描述为：如何发现规模为k的节点集P(也称为种子集)竞争传播正向信息，以最大化传播正向影响力到社交网络上的其他用户，实现最大化影响力竞争传播.

2 竞争影响力传播研究进展

竞争影响力传播研究源于生物群体的种群发展；随着研究的深入，疾病模型成为研究的重点；信息模型可以量化计算后，信息模型逐渐成为微观刻画和全网评估竞争影响力传播的热点问题.

2.1 生物群体

自然环境的种群发展与人类社会的信息传播有相似之处.种群动力学作为分析生物群体与环境之间关系的重要工具，可以用来量化生态系统中种群之间以及种群与环境之间的交互关系.王云驰[4]对生态系统的反应扩散模型进行了系统梳理和全面总结，认为社交网络可以比作种群的生态系统，节点之间的信息交互可以比作种群之间的竞争，并在数据集上进行了分析和论证.本文从该研究中获得了启发.

18世纪末，英国人口学家Malthus[5]提出了人口增长指数预报模型，在理想情况下对人口规模按照指数增长进行预测，但是未考虑有限的实际条件.比利时数学家Verhulst[6]提出了阻滞增长的Logistic模型，描述了种群规模从起始缓慢增长、中间快速增长、到后期资源受限的增长过程.Geroski等人[7]通过信息传播实验验证了该模型的合理性.但Logistic模型是基于单物种的增长过程，不适用于双物种以及多物种竞争的生态环境.Anthony[8]则认为该模型没有考虑网络节点距离对反应扩散过程的影响.

乌克兰科学家Lotka[9]和意大利科学家Volterra[10]分析了食物链的种群之间多物种相互捕食关系，基于Logistic模型增加了竞争系数并提出了Lotka-Volterra模型，对生态系统中种群之间的动态竞争进行动力学分析.Zhu等人[11]和Jiang等人[12]分别在随机环境下探讨了Lotka-Volterra模型的竞争研究.Kloppers等人[13]、钟琪等人[14]、Zhang等人[15]基于Lotka-Volterra模型在社会危机和微博舆论中通过建模来分析竞争过程.对于双种群，刘咏梅等人[16]、兰月新等人[17]、姜景等人[18]针对谣言和辟谣的竞争机制进行研究，较好地刻画了这种对立的竞争关系.

Fisher[19]综合考虑了种群增长在连续时间、连续状态情形下的动力学影响，在Logistic模型的基础上扩展了反应扩散过程，提出了Fisher模型.Wang等人[20]在Fisher模型的基础上提出了2阶段的Diffusive Logistic模型，将信息源划分成一系列子网，将信息传播过程比作子网内部的增长过程与子网之间的扩散过程，对竞争过程展开模拟探讨.

综上，通过将社交网络的信息竞争过程比作生态系统的种群增长过程[4]，为社交网络中的竞争影响力传播研究提供了一个新颖的视角.虽然如此，上述模型都是建立在平均场理论的假设之上.实际生态环境的种群发展过程中，不同生物、不同种群之间的影响以及种群与环境之间的影响都可能各不相同，因此种群模型在实际环境中的应用还存在一定的局限，一些改进与应用还在继续探讨中.

2.2 疾病模型

疾病在人群中的传播过程与信息在社交网络中的传播过程存在相似之处，因此学术界也开始探索运用疾病模型对信息传播过程进行建模，研究竞争传播机理.

疾病传播研究最早从18世纪60年代对天花传播研究开始.20世纪20年代伦敦黑死病以及孟买瘟疫爆发后，研究者们提出了SIR模型[21]以及考虑重复感染的SIS模型[22].最初的疾病模型把节点分为3种状态：易感态(susceptible,S)，节点可以一定概率被感染；免疫态(recovered,R)，节点被治愈后获得免疫力；感染态(infected,I)，节点可以一定概率转成免疫态.

研究者们基于疾病模型提出了一系列的改进方法.Ahn等人[23]基于SIS模型提出了一种不对称耦合的疾病模型.Kitsak等人[24]认为最有效的传播者是位于网络核心位置的节点，并且基于SIS模型展开了相关的实验分析.Karrer和Newman[25]采用渗流理论对2种病毒传播过程进行分析，发现在较大网络范围内感染性强的病毒能够存活下来，即“赢家通吃”.Prakash等人[26]认为一个节点在面临2种病毒竞争时只能被一种较强的病毒感染，也即“赢家通吃”.Beutel等人[27]基于SIS模型进行改进，提出了一种部分交叉免疫的病毒竞争模型，且采用平均场的方法对2种病毒共存传播的竞争阈值进行了分析.但是该模型采用的是完全连接图，实际网络大多是无标度网络，在实际场景中的作用有限.Tsai等人[28]基于博弈论的方法分析了传染病控制问题，提出一种启发式方法来解决抑制影响力最小化问题.

还有研究者将疾病模型应用到谣言的传播与抑制场景中并取得了一系列的进展.Singh等人[29]讨论了如何使用合适的机制来抑制谣言的传播，发现网络的平均度数越小，采用随机或者目标免疫的效果越好.Zhang等人[30]在SIR模型的基础上提出了谣言传播模型，认为存在2种谣言传播态.Xia等人[31]基于SIR模型提出了SEIR模型，发现谣言信息的吸引力不能影响社交网络中的传播阈值.在竞争传播过程中，Liu等人[32]基于SIR模型增加了节点犹豫态，并提出SHIR模型研究二元信息的竞争关系，认为转移概率大的信息将占绝对优势.Xiao等人[33]提出了SKIR模型，其中K状态表示该节点传播辟谣信息，可以用来描述社交网络谣言与辟谣的并行传播过程.

综上，研究者们借助经典的疾病模型对信息的竞争传播、尤其是谣言的扩散与抑制进行了理论分析和实验探讨，形成了一系列有益的尝试和研究成果.但是，基于疾病模型以及扩展模型的竞争传播研究主要还是从趋势层面进行宏观刻画，在现实世界中的二元乃至多元信息竞争机理的细粒度计算上比较受限.

2.3 信息模型

随着信息模型理论与应用的拓展，研究者们开始在竞争传播中进行探索.Bharathi等人[34]最先提出竞争条件下的影响力最大化问题，随后研究者们在独立级联(independent cascade,IC)模型和线性阈值(linear threshold,LT)模型中进行拓展.Borodin等人[35]聚焦多竞争者的影响力问题，基于LT模型提出一种OR模型(original model)，研究节点在竞争情况下如何决策选择其中一方的影响力，并证明了该问题属于NP-Hard问题，可以用贪心算法获得近似最优解.Chen等人[36]考虑到商品本身的质量问题会产生消极影响，提出IC-N模型研究如何竞争传播：当节点受到邻居节点的激活影响时，以概率q转入积极状态，以概率1-q转入消极状态；当网络图是树结构时，采用动态规划的方法给出了近似最优解.还有研究者从抑制负向影响力最小化出发实现竞争传播的目标.He等人[37]考虑到LT模型下的企业产品竞争因素，通过让己方企业选择合适的初始节点集使其最大化传播，进而抑制对手企业使其最小化传播，该问题也被称为影响阻塞最大化(influence blocking maximization,IBM)问题.He等人认为负面信息容易被人们所接受，因而在传播阶段谣言信息比其他信息获得更高优先级，为了提升可扩展性提出了CLDAG算法，使得运行时间提升了2个数量级.Bozorgi等人[38]和Liu等人[39]利用社区划分算法划分网络，计算每个节点在所属社区中的影响力，并提出基于LT模型扩展的抑制扩散模型(diffusion containment model,DCM).Zhu等人[40]通过分析竞争环境中初始节点集的规模选择问题，研究如何抑制竞争信息的影响力传播.

为了获得竞争影响力的量化计算和近似最优解，研究者们从贪心算法入手开展竞争影响力传播研究，形成了一系列的改进和优化成果.Nguyen 等人[41]证明使用贪心算法可以得到近似最优解.Khalil等人[42]基于预删边的方式提出一个贪心算法解决影响力最小化传播，其目标函数在LT模型下具有超模特性，可以获得一个近似最优解.Li等人[43]认为社交网络中的节点关系可以划分为正向关系和负向关系，提出了极性相关的影响力最大化问题，并采用贪心算法获得近似最优解.Lin等人[44]提出了面向偏好信息的竞争传播问题，通过采用概率参数估计和节点选择的2阶段贪心算法而具有子模性和单调性，与距离模型、波传播模型等相比，在传播范围和计算时间之间取得了较好的平衡.Kimura等人[45]通过采用贪心算法来预删边的方式解决影响力最小化问题，但不能保证近似最优解.Ju等人[46]采用IC-N模型进行研究，通过引入一个质量因子q来转换负向影响力和正向影响力对扩散的影响，进一步优化提升传播范围.Ni等人[47]从社区角度来筛选种子节点并提出贪心算法，通过抑制负向节点的传播实现正向影响力的最大化，但是在子社区内展开的贪心算法计算评估限制了可扩展性的提升.Tong等人[48]针对竞争环境下的影响力最大化问题，通过采用主题建模、社区划分等方法来计算节点的影响概率.

为了更好地提升算法的可扩展性，一些研究者从启发式算法入手，进一步降低竞争传播的计算时间.Tong等人[49]提出通过预删边的方式解决最小化影响力问题，采用邻接矩阵的特征值来确定感染阈值.Ding等人[50]通过对IC模型进行扩展来研究竞争传播问题，根据影响力增益自适应地筛选种子节点集，但是正向优先的激活方式限制了应用的实用性.Zhu等人[51]提出使用最低代价的种子集选择问题来研究竞争影响力问题.Luo等人[52]通过同时考虑用户观点以及竞争者策略，提出迭代推断的启发式算法来抑制负向观点传播，在竞争影响力的同时也降低了运行时间.Cheng等人[53]针对传染病爆发的免疫问题进行了研究，论证了疾病免疫最小化问题和正向影响力最大化问题的转换，并通过实验验证了有效性，在可扩展性上也取得较好的平衡.

社交网络规模日益增大，研究视角更加细化和下沉[54-55].部分研究者围绕竞争传播模型的约束条件、传播路径、图结构等基础理论[56-60]不断深化，从深度学习[61-64]的角度出发，通过对局部网络特性的学习来预测推断全网传播[65-66]，这样就避开了局部信息有限的情况下无法开展全网评估计算的现实挑战.与早期的生物群体、疾病模型相比，基于信息模型的竞争研究深化了微观机制的刻画、竞争机制的构建以及宏观量化的统计，但是实际场景的需求也趋于更加复杂和多变，不断对理论验证和场景实证进行迭代成为研究的热点和优化方向.

3 总结与展望

3.1 总 结

社交网络在信息传播、政务发布、市场营销等方面发挥着重要的作用.从一元信息的最大化传播到二元信息、多元信息的竞争传播，结合复杂网络、社会计算、心理学等多学科理论，研究者们利用生物群体、疾病模型、信息模型对竞争影响力传播的传播表象、传播机理、传播规律进行剖析，取得了一系列的研究成果.但是，当前研究还存在一定的挑战：一方面，研究多聚焦于单方竞争影响力的最大化，多方竞争的整体影响力最大化面临越来越多的场景需求；另一方面，研究多聚焦于双方竞争对抗的影响力量化计算，但从竞争传播的作用机制来看更是一个双方博弈的过程.

3.2 展 望

未来围绕影响力的竞争传播还存在继续深入的研究点，如多元建模的深度刻画、竞争与互促的耦合、博弈论的应用等.

1) 多元建模的深度刻画.

在目前的信息模型构建过程中，主要围绕经典的IC模型和LT模型进行优化.由于模型带有先天的假设，与实际场景存在距离，需要融入更多场景需求来解决实际问题：一是随着多元竞争的应用越来越广泛，二元竞争环境中影响力传播问题的子模性和单调性可能不再适用；二是展开多关系[67]对影响力研究的探讨，对节点间的链接关系进行分类梳理，细化其对竞争模型的影响机理.

2) 竞争和互促的耦合.

当前竞争影响力传播研究主要围绕促使一方影响力最大化或者抑制一方影响力最小化展开，即围绕纯粹的竞争关系展开.随着研究场景的扩展与应用，互促关系越来越受到重视：一是对竞争环境的互促机理[68]进行深化研究，尤其是对互促关系对竞争传播的影响机理进行量化评估；二是在有限的预算条件[69-70]下，面向竞争主体的互促影响力最大化问题的建模论证成为深入研究的重点.

3) 博弈论的应用.

在目前的竞争传播过程中，主要聚焦于一方影响力最大化或者最小化传播的研究，但在实际场景中，不一定是单方的竞争胜出.影响力传播与抑制的本质是传播方与抑制方在系统层面的博弈[71-73]：一方面，在信息模型构建过程中，信息的传播过程常常以概率或者累计影响力进行计算，随着竞争传播中博弈现象的研究，博弈行为及环境反馈被纳入节点的交互过程，需要对竞争传播模型进行优化[74-75]；另一方面，从演化博弈[76-79]的角度提出可扩展性的近似算法[80-81]，对于竞争博弈的平衡以及成本控制具有现实意义.