有向重叠社区下考虑兴趣度的谣言免疫策略研究

闫 涵，康海燕

(北京信息科技大学 信息管理学院 北京 100192)

0 引言

谣言是未被认定的信息，它干扰用户获取正确信息、影响用户的思维，最终可能会威胁社会稳定，因此研究谣言的抑制方法是很必要的。谣言像流行病毒一样传播广泛，但是不同于流行病毒，对谣言不感兴趣的节点不会传播谣言。实际上在谣言的免疫策略中，谣言终归会被限制在一个兴趣区间内传播，因此广泛实施的免疫策略的实际效率较低。

复杂网络中有3种免疫策略：随机免疫、目标免疫、熟人免疫。基于这3种免疫策略，研究者们通过选择节点的不同方式实现不一样的免疫效果。文献[1]使用改进的边划分理论，提出了可以有效控制谣言传播范围和爆发阈值的免疫策略。文献[2]解决了谣言的抵抗能力存在差异以及用户间不同的亲密度，建立一种新的网络谣言传播动力学模型。文献[3]研究了疫苗免疫和群外个体迁入对传染病传播行为的影响。文献[4]发现传播过程中节点具有不同的活跃度，提出了基于活跃度的网络免疫策略。文献[5]提出一种选择节点自身出度和邻居最大出度(self-degree and neighbor-degree,SDND)谣言免疫策略，在选取免疫节点时综合考虑节点自身出度及其邻居最大出度。文献[6]定义了谣言感染和谣言清除的规则，提出主动免疫和被动免疫两种网络谣言免疫策略。文献[7]基于加权网络提出边权优先的节点熟人免疫策略。

在具有社区结构的社交网络中，文献[8]提出在社区结构中根据节点所属社区的成员身份号来选择目标节点。文献[9]提出了一种称为Comm度量节点的策略。它结合了社区内链接和社区间链接的数量，对社区中与社区之间的节点进行排名。文献[10]提出了community bridge finde搜索桥节点算法，它的基本思想是：在社区结构中，当选择另一个社区中的节点时，将不再链接到先前访问过的站点。Bridge-Hub检测器[11]是CBF策略的另一种变体，它通过探索被访问节点的朋友圈来选择节点进行免疫。随机游走重叠选择策略[12]是从网络的随机节点开始随机游走，访问或提取的社区重叠节点列表被选择为免疫目标，否则继续随机游走。以上研究把社交网络认定为社区结构，但是信息的传播具有方向性，且由于节点对信息的兴趣度不一样，本文提出符合谣言传播环境的具有社区兴趣度的有向重叠社区结构，同时，提出了考虑兴趣度的谣言免疫策略。

1 有向重叠社区下考虑兴趣度的谣言免疫策略

社交网络是一个具有重叠社区结构的复杂网络，其节点具有不同的特征，由此显现出节点异构性。现有的免疫策略多是在同构网络或具有社区结构的复杂网络下，没有考虑真实社交网络的结构，也没有分析节点的特征，因此现有的免疫策略是不完全适合真实社交网络的。

在研究了谣言的传播规律与抑制后，本文提出了有向重叠社区下考虑兴趣度的谣言免疫策略。此谣言免疫策略在每个社区中加入兴趣属性用于确定节点所在的社区；采用富节点与特殊富节点的方式选择目标免疫节点，其他节点以介数中心性确定施行熟人免疫。有向重叠社区下考虑兴趣度的谣言免疫策略的框架如图1所示，框架中主要包括：有向重叠社区的建立；异构节点的分析与选择；免疫策略的设计与实施。有向重叠社区的建立在于将重叠社区结构中节点的连接方式认定为有向连接，且在每个社区中加入社区兴趣度的属性，这样可以在有限范围内确定谣言的传播区域，加快免疫速度；异构节点的分析与选择着重考虑免疫策略中体现节点影响力的指标，其中我们提出富节点和特殊富节点的指标用于在重叠社区结构中确定有影响力的节点；免疫策略的设计与实施是将富节点和特殊富节点在确定范围内进行目标免疫，其他剩余节点则采用熟人免疫，既避免了目标免疫对网络结构的过分依赖，也避免了熟人免疫在全部网络实施免疫策略中效率上的浪费。

2 有向重叠社区的建立

复杂网络是指一种呈现高度复杂性的网络，面对现实的社交网络， Barabsi和Albert提出了BA无标度模型，此无标度模型中单一社区模型无法体现社交用户节点的复杂特性，因此在重叠社区模型下研究具有异构性的节点，可以体现社交网络下谣言的传播特点。

定义1(复杂网络)G=(V,E)，V表示网络中节点的集合，E表示网络中入边的集合。

定义2社区是指网络中的节点内聚子图，子图内部的节点间存在较多的连接，不同子图的节点间连接相对稀少。

定义3有向性指结构图中存在一个节点指向另一节点的方向。节点1指向节点2代表节点1关注节点2。

定义4重叠社区是网络中节点的集合，节点同时隶属于多个不同的社区，社区内部节点间的联系较为紧密，而属于不同社区的节点之间的联系较为稀疏，此类社区称为重叠社区。

定义5有向重叠社区是网络中节点与节点连接方向的集合，社区内节点同时隶属于多个不同的社区，节点之间是有向连接。如图2所示，节点1属于社区1、2，节点4属于社区2、3，节点6属于社区1、3，且图中每个节点具有连接方向，社区1～3被称为有向重叠社区。

定义6社区兴趣度是确定谣言传播范围的指标，在谣言出现后，假设谣言初次出现的社区为满兴趣度，其余社区关于此谣言有着不同的兴趣度。

如图3所示，节点1～5，7，9属于兴趣区间1，其他节点属于兴趣区间2，当节点4开始大面积传播谣言时，对此谣言感兴趣的兴趣区间1中的社区才有可能继续传播谣言，因此首先对兴趣区间1的社区进行免疫才能提高效率，如不考虑社区兴趣度采用其他方式大面积免疫，将会降低免疫效率。

3 异构节点的分析与选择

在社交网络中，谣言传播需要考虑节点的影响力，来表示其他用户对谣言产生的阅读和转发行为。在同一社区环境下，免疫策略的节点选择需要考虑节点的异构性。衡量节点异构性的标准有很多，比如度数、核数、介数以及特征向量中心性等。由于本文设定谣言的传播网络为有向重叠社区，所以各项指标定义有所不同，本文选择了节点介数与富节点。

定义8(介数中心性) 本文量化了一个节点作为其他节点之间最短路径上桥梁的能力，刻画出了社会网络中一个用户对于其他用户之间交流的影响力，是一种非常重要的度量指标。对节点介数进行归一化，Bi的介数中心性CB(vi)表示为CB(vi)=(2Bi)/((N-1)(N-2))。

定义9(富节点与特殊富节点) 在有向重叠社区结构中，富节点为网络中少量入度值极高的节点或节点有富节点进入的边。

图4 社交网络有向拓扑图Figure 4 Directed social network topology

寻找入度值极高的节点作为富节点，以及拥有富节点指向的节点作为特殊富节点。社交网络中的富节点表现为用户的粉丝数很高，但存在入度值远远低于富节点但有富节点指向的情况，这代表此节点可能为权威性节点，一旦被传染，那么谣言的传播效率将大大提升。社交网络有向拓扑图如图4所示。

图4中，节点1～3的入度值极高，被认为是富节点；节点4入度值为2，但是其存在节点1与节点2的进入边，因此认为节点4为特殊富节点。按照此拓扑图选择节点进行免疫时，应选择节点1～4。在社区Cn中，当节点vi的入度值ik>K时，节点vi属于富节点，节点vi中存在的出度节点也为富节点。富节点与特殊富节点的选择算法如算法1所示。

算法1 富节点与特殊富节点。

输入： 复杂网络G(V,E)，社区集合ComList。

输出： 富节点集合RichList。

1) RichList(V,E) ← 0∥创建一个空集合RichList(V,E)

2) for each k in ComList do ∥获得某个社区的节点

3) Sort ComList by ComList[k].getE

4) choose 5% nodes add RichList ∥利用入度选择富节点

5) for each i in ComList[k] do

6) if i has RichList nodes degress then

7) i add RichList ∥选择特殊富节点

8) end if

9) end for

10)end for

11)return RichList(V,E)

在社交网络中，节点的入度随时间变化，但富节点是在一定范围内拥有极高入度量，且特殊富节点也具有特殊性，因此时间不影响对富节点与特殊富节点的判断。

4 谣言免疫策略的设计与实施

免疫策略旨在免疫一些关键节点，以减少或阻止谣言传播的目标。现有的研究中，谣言的免疫策略主要有3种免疫方式：随机免疫、熟人免疫、目标免疫。随机免疫与目标免疫在无标度网络下都需要选择大量节点进行免疫，效果较低。熟人免疫策略主要是从网络中随机选择一定比例的节点，对每个被选节点的一个邻居节点进行免疫。在无标度网络下，它无须考虑复杂的结构，比目标免疫效果要好。而如今谣言的传播平台倾向于社交网络，单纯的使用熟人免疫是无法适应的。

在设计确定性策略中，对于网络的每个节点，使用全局信息计算影响度，然后根据它们的影响值对节点进行排序和免疫。使一个节点成为染病节点的原因有多种，但最主要的原因是节点与染病节点处于同一社区，在一个社区内进行大范围传播谣言；在谣言向外扩散时，作为重叠社区中染病节点会向多社区扩散谣言，但只有与谣言社区兴趣度高的社区才会出现大概率染病节点。

4.1 社区兴趣度

社区兴趣度是为了确定谣言可能进行大范围传染的社区，要有效率地抑制谣言的传播，其核心思想是当n个社区已经开始传播谣言时，根据这n个社区与其他社区的连接密度、重叠节点，确定此谣言的兴趣度。

4.2 改进传染病模型

我们用传染病模型来验证文中兴趣度的重叠社区模型以及谣言免疫策略。传染病模型中，SIR(susceptible-infected-recovered)传染病模型是最为基础的模型。在该模型中，节点有3种状态：易感者(susceptible)，染病者(infected)和恢复者(recovered)。 SIR模型的感染机制如图5(a)所示。基于此感染机制，在重叠社区结构中利用常微分方程建立SIR模型的平均场方程：

式中：k表示一个度为k的节点组；Sk(t)+Ik(t)+Rk(t)=1;θ(t)=k′P(k′)I′k(t)/(〈k〉);λ代表了易感者(S)被感染成为染病者(I)时的转换概率。

通过研究SIR模型的感染机制，我们得知易感者会以一定概率成为染病者，而且易感者只有这一条转换路线。在谣言的传播过程中，易感者并不只是转换为染病者。在一段时间后，易感者也会以一定概率转换为恢复者，因此我们需要改进SIR传染病模型来更符合谣言在真实世界的传播规律。

图5 传染病模型传播机制Figure 5 Transmission mechanism of infectious disease model

我们根据社区兴趣度与富节点集合定义免疫概率为δk，且

4.3 谣言免疫策略

通过对网络与节点的分析，我们在有向重叠社区结构下，社区具有兴趣属性，以节点介数中间性和富节点作为指标来设计谣言免疫策略。由于需要了解节点的异构性，因此我们认为此谣言免疫策略为局域免疫策略。建立此谣言免疫策略的核心重点为：1) 对社区网络进行了重叠社区划分，计算此谣言的兴趣区间，寻找在同一兴趣区间但并未感染谣言的社区；2) 计算健康节点(未感染)的入度值，选择前n项入度值高的节点(富节点)；3) 选择富节点的出度节点作为特殊富节点；4) 将网络中余下的节点进行熟人免疫，其中采用介数中心性选取邻居节点。通过对谣言免疫策略的设计，提出了考虑社区兴趣的谣言免疫策略算法如算法2所示。

算法2 考虑社区兴趣度的谣言免疫策略。

输入： 复杂网络G(V,E),重叠社区列表 loon,谣言已传播列表 lorc。

输出： 免疫节点列表immunity。

1) frc←第一次出现谣言的社区

2) H←计算兴趣区间(frc,lorc,looc)

3) loon.remove(lorc)∥此时loon中没有传播谣言的社区

4) for each k in loon do

5) if k的兴趣度

6) lorc.add(k) ∥寻找在兴趣区间的未感染社区

7) loon.remove(k)

8) end if

9) end for

10) immunity choose富节点与特殊富节点 in lorc ∥寻找在兴趣区间内社区的富节点

11) 开始实施目标免疫

12) immunity choose熟人免疫节点 in loon

13) 开始实施熟人免疫

5 实验

为了评估本文所提出的谣言免疫策略，我们将此免疫策略进行仿真实验，并将其与现有的免疫策略进行对比。实验中网络总节点数N=103，平均节点度k=10。

实验一传播模型的改进对比。

在4.2节中我们将SIR模型进行了改进，考虑了在免疫策略出现后SIR模型下3种状态转换中的概率。实验对SIR模型与改进的SIR模型进行仿真分析，通过实验结果进行比对，发现改进模型的优势。SIR模型中设定参数λ=1，仿真结果如图6(a)所示。染病者的人群密度在时间为8小时达到高峰。由于当网络上开始传播谣言时，相关辟谣信息才能随之推出，相对的免疫策略必然是在此谣言具有一定传播效应后才能开始运行，也就是实施免疫策略具有一段的延迟时间。根据SIR模型的仿真结果，我们假定在时间为5小时开始实施免疫策略，此时改进的SIR模型的相关参数为λ=1，δk=0.4，仿真结果如图6(b)所示。

图6 传染病模型节点密度变化图Figure 6 Density change of nodes in infectious disease model

根据图6的仿真结果对比发现：1) 在时间为5小时加入免疫策略后，染病者的人群密度虽然继续走高，但是其峰值低于SIR模型，且提前1个时间到达峰值；2) 易感者在5小时后人群密度极度减少，相对恢复者的人群密度增多，但染病者人群密度的增长速度减缓，这代表了开始实施免疫策略后，全局节点可以获得正确信息，减少了未知此事的易感者感染谣言的概率。

图7 不同免疫策略染病节点密度变化图Figure 7 Density changes of infected nodes under different immunization strategies

以上仿真结果表示，当任意免疫策略进入时，可以减缓染病者的增长速率，使其快速到达拐点，并且对易感者可以起到预防作用，因此免疫策略对谣言的抑制有着很大的作用。

实验二免疫策略对比。

我们将对目标免疫、熟人免疫和考虑社区兴趣度的免疫策略进行实验对比，主要对比这3种免疫策略中传染病发展的过程。仿真过程利用改进的SIR模型进行实验，实验结果如图7所示。

假定在时间为5小时开始实行免疫策略，经过对比发现，本文提出的免疫策略由于在免疫时需要选择特殊节点，因此比目标免疫的效果弱一些，但是随着时间的推移，本文提出的免疫策略逐渐接近目标免疫的效果。由于本文提出的免疫策略不需要一直依靠节点的入度选择免疫节点，相比与目标免疫，我们认为本文提出的免疫策略更加优秀。

6 总结

随着用户越来越依赖社交媒体来传播信息，信息的传播也随着原来的人传人转移到一人传多人。本文提出的谣言免疫策略考虑了社交网络结构以及节点特征，更加适用于社交网络。此免疫策略不再使用一个策略对网络中所有节点进行抑制，而是优先对某一部分容易被感染的社区进行免疫。此免疫策略通过计算节点值的情况，不仅考虑了少数粉丝数极高的富节点，还考虑了影响力不足但数量很多的普通用户。

本文还提出社区存在对谣言的兴趣度，利用社区兴趣度，可以判断谣言下一步的传播方向和传播社区。在每个社区中寻找影响力高的富节点，利用富节点影响普通节点的谣言传播。此方法减少了大范围搜索节点或大范围节点免疫的时间，提高了谣言的免疫效率。通过实验分析，在社交网络中，此免疫策略更加有效。