9.3 识别信息传播中有影响力的传播者
1.摘要
识别信息传播动力学的影响因素是网络科学领域的热门话题。为了确定有影响力的传播者，以前的大多数研究都是基于网络的全部信息。在本节中，提出了一种从随机选择初始种子节点识别有影响力的传播者策略。种子连接成链并定位在初始种子上。有偏随机游走是基于有影响力的传播者识别策略，步行者的运动由邻居的度值进行调整。种子是步行者曾经访问过的那些节点。通过在人工网络和四个现实世界网络上进行的大量数值模拟，发现优先选择较大度值的节点更有可能找到最具影响力的传播者。当优先选择某地的活动中心时，暴发阈值会降低。实验结果为确定最具本地化影响力的传播者提供了一些启示。
2.介绍
许多现实世界的系统都可以用复杂的网络来描述，节点代表元素，边代表不同元素之间的关系[35，122-125]。信息、疾病、健康行为和社会系统创新的扩散可以映射到研究复杂网络上的传播动力学上，这引起了数学、物理学和网络科学领域的广泛关注[7，53，126-131]。一方面，研究人员研究了传播动力学和网络拓扑之间的相互作用，并获得了一些有趣的结果。例如，对于具有SF 度分布的网络来说，一些活动中心（即度值较大的节点）导致暴发阈值消失[2，5，44，132，133]。此外，权重分布的异质性会增加暴发阈值[9，134-136]。最近，一些学者发现网络的复杂性和时间性显著改变了传播动力学和暴发阈值，并开发了一些新颖的理论方法[22，20，137-139]。另一方面，已经研究了选择某些节点来抑制或促进传播动力学的策略[140-146]。对于前一种情况，研究人员将其称为网络免疫。在这种情况下，研究人员通常会提出一些策略去测量结点的重要性，例如度、中间性、特征向量中心性和k-核，对得分高的节点进行免疫[137]。对于后一种情况，称为影响力最大化[148]。通常来讲，会使用一些测量方法（例如k-核、特征向量中心性、H-索引和迭代算法）来定位有影响力的传播者[149-153]。最近，Morone和Makse通过最优渗流研究了复杂网络中的影响最大化，发现一些弱连接节点也是最佳影响者[154]。考虑到环的密度和不同节点度的异质性，Wu等人[153]基于参考文献[154]中提出的策略，提出了一种有效的有影响力识别策略。We等人通过对真实世界网络的大量数值模拟验证了他们提出策略的有效性。Hu 等人揭示了一个节点的影响取决于节点的特征数量[155]。
实际上，找到最具影响力种子的成本很高。例如，当为产品做广告时，应该寻找一些城市和明星来推广它。对于明星来说，宣传推广价格总是很昂贵。实际上，资本预算是有限的，如何在这种情况下发挥最大影响力是这项工作的目的。受到参考文献[156，157]的启发，希望找到一种便利的方法从随机选择的“初始种子”中定位最具影响力的传播者。本节提出了一种本地化有影响力的种子选择策略。通过在人工网络和现实世界网络上的大量数值模拟发现，当优先选择具有较大度值节点时，这种策略可以有效地促进信息传播动力学。如果优先选择活动中心，则暴发阈值会降低。
3.模型描述
将网络表示为G=（V，E），其中V 是节点集，E 是边集。网络规模N 是集合V 的元素数，即N=|V|。同理，边的数量为M=|E|。本节使用易感态-感染态-恢复态（SIR）模型[25]描述复杂网络上的信息传播动力学。在每个时间步长点，每个节点只能处于易感态、感染态和恢复状态之一。对于处于易感态的节点，它没有从邻居那里得到任何信息。被感染的节点表示它已掌握信息并愿意与他人共享。处于恢复状态的节点表示它对信息失去了兴趣。
为了触发信息传播，应该根据一些策略（稍后定义）选择一些节点作为种子（传播者）。W 表示种子数。在每个时间步长点，每个受感染的节点将以概率λ将该信息传输到每个易感态的邻居，然后以概率μ 进行恢复。为了不失一般性，在这里设置μ=1。一旦没有处于感染态的节点，信息传播动态将终止。在这种情况下，将信息传播规模表示为R，对于给定的种子选择策略，R 值越大该策略越有效。
4.理论分析
实际上，获得有关网络拓扑的全局信息既困难又昂贵。相反，现实中有关网络拓扑的本地信息更易于访问。因此，种子的选择来自于网络中随机选择的“初始种子”节点。当为一些小型商店和企业做广告时，对于给定的预算，这样的策略选择更有效。为了有效地促进信息传播动力学，本文基于随机行走策略提出了一种有影响力的传播者选择策略。
（1）随机初始化第一个“初始种子”节点i，并将传播者的数量设置为W。将节点i放入传播者集合S 中。在初始种子节点中设置开始的步行者。
（2）步行者的运动是根据一系列的功能由邻居的度值进行调整：
式中，种子集S 的非种子（没有被选作种子的节点）邻居的集合是Ns，ki是节点i 的度，-∞＜α＜+∞是优先选择的指数。α=0时，节点被随机选择。α＞0时，更可能选择活动中心作为传播者。α＜0时，具有小度值的节点更有可能被选为传播者。当行走者移动到节点i，会将其设置为有影响力的传播者（即种子），并把它放进传播者集合S 中。
（3）重复步骤（2），直到选择了W 个传播者为止。
图9-15中显示了具有8个节点10条边的网络G 的种子选择策略。对于随机选择策略（即α=0），所有传播者随机的来自初始种子节点4，如图9-15（a）所示。对于α=-1（α=1）时，最大概率选择度值小（度值大）的节点，如图9-15（b）和图9-15（c）所示。
5.数值模拟与结果分析
在本节中，在人工网络和现实网络上进行了大量的数值模拟。通过研究平均信息暴发规模
评估有影响力的传播者选择策略的效果，其中j是数值模拟的数量，Rj是第j 次模拟的暴发规模。＜R＞值越大该策略越有效。为了获得＜R＞，所有模拟至少要进行5 000次以上进行平均，即J≥5 000。
图9-15 具有8个节点10条边的网络G 上局部有影响力的传播者选择策略示例图。（a）随机选择（即α=0）3个种子来自初始种子节点4，选择（b）中种子度值小的节点（例如α=-1）和（c）中度值大的节点（例如α=1）(https://www.daowen.com)
首先研究策略在无标度（SF）网络上的性能。SF 网络的度分布为P（k）～ζk-γD，其中
γD 是指数。由于在仿真时希望对具有异质性和同质性度分布的人工网络验证策略的有效性，在这里仅选择两个不同的度指数，即γD=2.1和γD=3.5。对于具有γD=2.1的网络，度分布是异构的。对于具有γD=3.5的网络，度分布是均匀的。为了确定数值临界点，文中采用相对方差，其定义为
式中，＜.＞是平均值。χ 在暴发阈值点上出现一个峰值[88]。当信息的传输概率小于暴发阈值λc，即λc≤λc时，获得信息的节点较少。否则，当λc＞λc时，就可能发生全局信息暴发。
在图9-16 中，首先研究了信息在具有强度异质性分布的SF 网络上的传播，度指数γD=2.5设置度分布遵循结构截止值，即
网络规模设置为N=10 000，种子大小为W=50。对于任何α值，＜R＞随λ逐渐增加。文中发现选择具有较大度的节点作为有影响力的传播者的偏好有利于信息传播。比较α=0和α=1的情况，当α=1时＜R＞值较大，如图9-16（a）所示。此现象表明本地有影响力的传播者是活动中心。重要的是，文中发现当α=1 时，＜R＞随λ呈指数增加，即＜R＞～exp（μ0λ），其中μ0为常数。在图9-16（b）中，表现出相对方差χ 作为λ 的函数。当α=-1时，相对方差相对较大，并且峰值较高。暴发阈值随α降低。
为了了解不同策略的有效性，文中调查了种子的累积度分布Q（k），如图9-17所示。累积度分布计算为
其中G（k′）是所选种子的度分布。随着α的增加，度分布的异质性降低，活动中心更有可能被选为种子。活动中心会通知更多邻居，因此，最终的通知规模在暴发阈值附近更大。
文中进一步研究了较少的异构度网络上有影响力的传播者选择策略的性能，其中度指数γD=3.5，如图9-18所示，类似于图9-16，如果选择度值较大的节点作为种子，则最终已知＜R＞的大小在暴发阈值附近更大。与选择度值小的策略相比，选择活动中心时暴发阈值较小。
图9-16 在SF网络上阶指数为γD=2.5时的传播动力学示例图。在α取值不同的情况下传播者选择策略，（a）平均暴发规模＜R＞；（b）相对方差χ 对信息传播概率λ 的影响
图9-17 不同局部影响力传播者选择策略的累积度分布Q（k）图
图9-18 γD=3.5时，α取值不同的情况下，平均暴发规模＜R＞与信息传播概率λ的关系演示图
最后，文中在四种真实世界的网络上执行了局部种子选择策略，其中包括ar Xiv astroph[158]，Facebook Friendships[159]，Flickr[160]和Route views[158]网络。如图9-19所示，网络的更多统计特征如表9-1所示，包括网络规模（N）、边的数量（E）、度的最大值（kmax）、一阶（＜k＞）度分布、二阶（＜k2＞）度分布、度-度相关性（r）[161]、聚类（c）[162，163]模块化（Q）[164]和由DMP方法
预测的理论阈值。（
），其中B 是网络的非回溯矩阵。由于本节希望检查策略在暴发阈值附近的性能，在这里考虑最准确的理论阈值
1/∧B。对于四个真实世界的网络，本节发现最终的已知＜R＞规模对于α=1时是最大的，即更倾向于选择度值较大的节点作为最具影响力的活动中心。
图9-19 对于真实世界的网络传播动力学，平均暴发规模＜R＞与信息传播概率λ的关系图示（a）ar Xiv astro-ph；（b）Facebook Friendships；（c）Flickr和（d）Route views networks
表9-1 真实世界网络的统计特征表
包括：网络规模（N）、边的数量（E）、度的最大值（kmax）、一阶（＜k＞）度分布、二阶（＜k2＞）度分布、度-度相关性（r）、聚类（c）、模块化（Q）和由DMP方法
预测的理论阈值。
6.结论
实际上，确定最有影响力的传播者总是要付出代价的。以前的许多研究在全局范围定位最有影响力的传播者，这可能会极大地限制其应用，特别是在资金有限的情况下。例如，一个小商店想做商品广告，由于其资本预算有限，它总是从当地的广告商中挑选广告商，如何在这种情况下最大限度地发挥影响力就是本节研究的目的。在这里提出了一个简单的局部影响传播者识别策略——基于优先随机游走策略。具体来说，步行者一开始是随机的，然后根据邻居的度值优先走向度值大的邻居。有影响力的传播者是那些步行者曾经造访过的节点。通过这个简单的有影响力传播者选择策略，在人工网络和四个真实网络上进行了大量的数值模拟。发现当度值较大的节点优先被访问时，这样的策略可以有效地确定最有影响的传播者。这个结论可以为更有效的局部传播者选择策略提供一些启示，例如包括kcore、H-指数、节点的特征向量中心性。设计有效战略的另一个思路应考虑全局和本地网络拓扑信息，比如先选择多个种子，然后优先选择这些种子的邻居。