CIC模型下基于社区检测的谣言抑制最大化方法.pdf

CNATURSCIENCEMar.,20232023年3月JOURNAIVERSITYVol.59,No.2第59 卷第2 期南京大学学报（自然科学DOI:10.13232/ki.jnju.2023.02.011CIC模型下基于社区检测的谣言抑制最大化方法刘维维*，杜宁宁，陈峻，洪青青（扬州大学信息工程学院，扬州，2 2 512 7）摘要：随着电子设备的日益普及和信息扩散的便利性，在线社交网络为各种负面信息的传播提供了高效的媒介.谣言是社交媒体上负面信息的突出形式之一，会引发社会动荡，造成经济损失，因此，快速有效地抑制谣言传播成为当前社交网络研究领域中的一个热点.提出一种有效的谣言抑制传播方法，从网络中选取多个正种子节点来传播真相，抑制谣言的传播.首先采用竞争性独立级联（ConpetitiveIndependentCascade，CIC）模型来同时传播谣言和真相；其次，提出一种基于标签传播的社区检测算法对社交网络进行分解，并为各个社区分配正种子节点预算；最后，创新地提出节点强度来衡量网络中节点的重要性，并利用节点强度在各个社区中选取抑制谣言传播的初始正种子集.实验证明，该方法能达到与贪算法相匹配的抑制效果，且运行时间比贪婪算法快三个数量级。关键词：在线社交网络，社区结构，谣言抑制，竞争性独立级联模型中图分类号：TP393文献标志码：ARumor blocking maximization method based oncommunity detection under the CIC modelLiu Wei,Du Ningning,Chen Ling,Hong Qingqing(College of Information Engineering,Yangzhou University,Yangzhou,225127,China)Abstract:With the increasing popularity of electronic devices and the convenience of information diffusion,online socialnetworks provide an efficient medium for the propagation of various negative information.Rumors are one of the prominentforms of negative information on social media,which trigger social unrest and cause economic losses.Therefore,how toquickly and effectively block the spread of rumors has become a hot spot in current social network research field.In this paper,we present an effective method for blocking rumor propagation,which selects multiple positive seed nodes from the networkto spread the truth to block rumor propagation.Firstly,we adopt a Competitive Independent Cascade(CIC)model topropagate rumors and truth simultaneously.Secondly,we propose a community detection method based on label propagationto decompose social networks and allocated positive seed node budgets to each community.Finally,we propose a novel nodestrength to measure the importance of nodes in the network and use it to select the initial positive seed set which blocks thespread of rumors in each community.Experimental results show that the proposed method achieves the same blocking effectas the Greedy algorithm,while the running time is three orders of magnitude faster than the Greedy algorithm.Key words:online social networks,community structure,rumor blocking maximization,Competitive Independent Cascademodel基金项目：国家自然科学基金（6 197 12 33，6 17 0 2 411），江苏省自然科学基金（BK20170513）收稿日期：2 0 2 2-11-14*通讯联系人，E-mail:283刘第2 期维等：CIC模型下基于社区检测的谣言抑制最大化方法大数据时代，人与人之间的信息交流愈加频繁，Twitter,Meta，Yo u T u b e 都是深受人们喜欢的在线社交网络（Online Social Networks,OSNs)平台，如2 0 2 2 年1月统计，Meta拥有数十亿的注册账户，月活跃用户超过2 8.9亿.通过这些平台，供应商和卖家可以选取一些“具有影响力”的用户（种子节点)来宣传产品、观点及思想 1 使尽可能多的用户购买该商品，基于此，影响力最大化(Influence Maximization,IM)应运而生 2-5,并得到了广泛的关注.IM的目标是在网络中寻找一部分关键的种子节点集合，通过传播模型使扩散的影响力最大化，但在没有严格审查时，产生和分享大量信息会使信息内容的真实性不断削弱，导致谣言在网络中肆意传播，造成一系列不利影响.例如，2 0 2 2 年4月国外上映了一部名为“WatchtheWater的电影，声称COVID-19是“蛇毒”的合成版本，饮用水和COVID-19疫苗会导致“邪恶势力”的传播.虽然纯属杜撰，但该视频发布后一周内就在托管平台Rumble上获得近30 0 万次的观看和转发，谣言四起.由此可见，及时发现并抑制OSNs中的谣言传播已迫在眉睫 6 本文研究谣言抑制最大化（RumorBlockingMaximization,RBM)7,是IM的对偶问题,旨在选择一些种子节点来最大程度地阻止谣言的传播对RBM的研究已有不少工作(8-10 1.Newmanetal81证明，以大约10%的偏离度降序移除节点可以免疫谣言对其他节点的影响.Wangetal通过发现和阻断一组未受感染的关键用户来最大程度地减少被感染用户的规模.另一方面,Kimuraet al101建议阻断重要的链接，而不是阻断节点.上述工作极大地推进了抑制谣言传播的研究，但仍存在挑战，具体地：（1)采用阻断节点的方式抑制谣言，没有考虑真实社交网络中的用户体验，而且在一定程度上会对网络结构造成破坏；（2）由于OSNs是无标度网络，即使采用阻断链接的方式来抑制谣言，用户仍然可以传播来自其他链接的谣言，因此阻断链接不是最佳选择；（3)谣言传播是多个谣言源通过合作方式来传播谣言的过程，因此，辟谣也应该通过合作的方式来传播真相，抑制谣言.此外，OSNs还具有社区结构的特征 11.社区结构的一个重要特性是社区内的节点间联系密集，而与其他社区节点之间的联系稀疏，且消息在社区内传播比社区外传播要快得多.因此，合理利用网络中的社区结构，可以有效地提高谣言的抑制效果：本研究采用竞争策略，通过传播真相来抑制谣言的传播.首先，将OSNs划分成互不重叠的社区，在各个社区内实现谣言抑制最大化与已有的阻断策略相比,该方法既阻断了谣言的进一步传播，又在OSNs中扩散了真实消息，因而提升了人们识别谣言的能力传统的独立级联（Inde-pendentCascade,IC)模型只适用于一种信息的传播，而本文提出的方法是基于竞争性独立级联(Conpetitive Independent Cascade,CIC)模型的,目标是最大程度保护节点免受谣言的影响。本文的主要贡献：(1)基于OSNs中的CIC模型,提出三阶段策略来解决谣言抑制最大化问题.第一阶段，社区划分；第二阶段，进行传播真相的正种子预算分配；第三阶段，进行传播真相的正种子选择。(2)提出基于标签传播的社区检测算法来识别网络的社区结构，能有效地克服传统标签传播中容易出现的不易收敛的缺陷。（3)提出节点强度来量化真实传播过程中节点的重要性，能够在社区中选取性质良好的正种子节点来传播真相。（4)在四个真实数据集上进行的大量实验表明，本文提出的方法具有良好的可扩展性，在大规模数据集上，对谣言也有很好的抑制效果，1相关工作IM问题由Domingos and Richardson12提出，Kempe etal13提出一种贪婪爬山算法来解决IM问题,并证明该问题是NP-hard问题,在此基础上提出了独立级联（IC)和线性阈值（LinearThre-shold,LT)模型.由此，人们开始从理论和时间两个方面对IM问题进行广泛的研究，各种传播模型和算法相继被提出：RBM(Rumor Blocking Maximization)是 IM问题的扩展，最先由Budaketal14提出.IM问题通常考虑诸如积极信息和创新等理想事物的传284第59 卷南京大学学报（自然科学）播，而RBM旨在限制谣言的传播.目前，解决该问题的方法主要有三类：(1)阻断有影响力的用户 15-18 .在信息传播过程中，确定OSNs中最有影响力的传播者是一个重要的问题，该类方法通过识别并阻断一组关键节点来最大程度减少网络中谣言的扩散.Yanetal15选择阻断节点集来最小化谣言源节点的激活概率之和，提出一种两阶段方法来生成候选集并选择要阻断的节点集.Juetal16研究如何最大程度阻断来自不确定来源的负面影响，并提出一种基于实时边子图中的传播树来计算正种子阻断增量的算法.Hosni and Lil17考虑OSNs中个体和社会的行为，提出一个多谣言传播模型,还提出一种动态阻断周期的方法来最小化谣言的影响，Zhu et al18研究了一个新的问题一一错误信息影响的活动最小化，将一个节点集从网络中阻断，从而使节点之间的错误信息交互的总数最小化.但随意阻断节点，不仅会影响网络用户的体验，还有可能会破坏网络结构，(2)删除用户之间的链接，通过识别一组关键链接并将其删除来减少OSNs中谣言的传播(19-2 1.Scaman etal19将谣言的动态控制定义为动态资源分配问题，提出一种新颖的感染边缘最大减少控制策略，具有高效和易于实现的优点。Yan etal201提出一个启发式算法来不断迭代删除一条可以最小化谣言传播值的边，从而抑制谣言的传播与传统的谣言抑制问题不同,Guo et al21研究如何保护目标用户不受谣言的影响，称为目标保护最大化问题，目标是阻断最小的边缘，使受谣言影响的目标节点的预期比例低于一定的值。但通过阻断链接的方式来抑制谣言会破坏网络结构，同时，谣言仍可以通过其他链接进一步传播，抑制作用不明显(3)传播正面信息来抑制谣言，即使用一组传递积极消息的节点对抗来自谣言源的扩散2-2 7 Heetal22研究了竞争线性值模型下社交网络中竞争影响力的传播，给出了一个有效的算法来找到种子节点，尽可能地阻止其竞争实体的影响传播.曹玖新等 2 3 研究竞争环境中利已信息的影响力最大化问题，考虑节点间交互内容的主题偏好特点，提出两种利已信息的影响力最大化算法.Tripathi and Rao25提出一种用于OSNs中信息扩散的点对点线性值模型，并提出PWD(Proximity-Weight-Degree)算法选取正种子节点来抑制谣言.考虑谣言抑制的成本,Yao etal26用可信度作为成本来衡量一个人对他人的影响，提出一种最长有效跳的算法来抑制谣言.Sriniva-san and Dhinesh27提出一种防御性的谣言控制方法，利用群居昆虫的免疫策略来传播反谣言.但上述算法在运行效率方面存在不足，或是仅促使某一种竞争实体的影响力最大化，忽略对另一种竞争实体的抑制.针对以上问题，本文提出的算法可以实现在抑制谣言传播的同时，使真相的扩散范围最广，2传播模型和问题定义本节介绍使用的传播模型，并给出问题形式化的定义.2.1竞争性独立级联模型(CIC)在线社交网络通常被建模成一个无向图G=(V,E),其中每个节点 EV代表网络中的一个用户，每条边(u,)EE表示用户u和之间的关系，E中的每一条边被分配一个概率Pu，表示u对的影响.假设有两个级联同时在网络中存在：R（谣言）和T(真相）,则每个节点具有三种不同的状态之一：（a）R-a c t i v e;（b）T-a c t i v e;（c）In a c t i v e.谣言和真相同时在网络中传播，每个节点最初都是不活动的，一旦节点被激活，就不会改变其状态，因此，先到达的级联将率先激活节点.在每一个时间步，如果一个节点被属于不同级联的两个或多个邻居成功激活，它将选择具有最高优先级的那一个，假设谣言（R)具有更高的优先级，这种非对称性反映了社会心理学研究中经常提到的负面认知偏差.给定N)表示节点的邻居节点集，ST和SR分别表示传播真相的正种子集和传播谣言的负种子集，传播过程如下：(1)初始时刻,所有节点都处于非活动状态。（2)当t=O时，ST和SR中的节点分别被谣言和真相激活.(3)当t0时，在t一1时被激活的每个节点u尝试以Pu的概率激活每个不活动的邻居u.如第2 期285刘维等：CIC模型下基于社区检测的谣言抑制最大化方法果有多个节点同时到达节点，则它们激活 节点是相互独立的，且最多只有一个节点可以成功激活.节点u在t时刻只有一次机会去尝试激活其不活动的邻居。（4)在t十1之后，u无法激活其任何邻居，该扩散过程持续到没有新的节点被激活为止。图1展示了一个简单的扩散过程。Rumor-activatednodeInactivatednodeTruth-activatednodeV2V2V2V3V3V3V4V4V4VVV1V5V5V5Time=0Time=1Time=2Rumor-activepath-InactivepathTruth-activepath图1一个简单的扩散过程示例Fig.1Anillustrativeexample2.2问题定义给定一个社交网络G(V,E),ST和SR分别为传播真相和传播谣言的种子集.对于R，初始种子集SR已知，ST和SR在网络中传播真相和谣言.定义谣言抑制最大化问题如下：设(V,S)为在扩散过程结束后处于R状态的节点，(VSR,ST)为种子集ST和SR联合效应下的处于R状态的节点，则传播真相的正种子集ST的谣言抑制作用可表示为：RBR(ST,SR)=(V,SR)-(VISR,ST)(1)其期望值为：0r(ST)=E(IRBR(ST,SR)I)(2)定义1谣言抑制最大化问题给定图G=(V,E),谣言抑制最大化的目标旨在找到一个大小为K的传播真相的正种子集合S二V，使得r(S)最大：S*=argmaxi(ST)(3)STEVISRST1;12.SSUUj;13.else14./*节点,划分至对应标签值最大的社区C,*/15.C,C,U(u,);16.C+CUCi;17.end for18.for,ES do19./*计算0，在各个社区C,的连接度*/287第2 期刘维等：CIC模型下基于社区检测的谣言抑制最大化方法20.Calculate,sconniz;21.achieve max(conniz);22./*将0 并入连接度最大的社区C,*/23.C,C,U(u.);24.C+CUC;25.end for26.End3.1.3合并链接密切的社区定义5社区稠密度使用节点的聚类程度来描述社区的密度,则社区C,的稠密度,定义为：2|E.(7)I N I(I N.I 1)其中，E，表示社区C,中节点之间的边的数量，IN|是社区C,中节点的数量.社区越稠密，节点间的联系越密集，则节点间交换信息的频率越高，这样就可以利用更快更精准地传播真相来抑制谣言的扩散。划分初始社区后会得到节点数较少的小社区，为了进一步提高传播正种子节点的谣言抑制效果，需要合并这些小社区.具体步骤如下：(1)计算所有社区中心之间的距离，合并中心距离最小的两个社区，(2)设置稠密度阈值n，当社区C,的稠密度大于值时合并结束.与Lietal28相似，本文的社区稠密度阈值设置为0.5.社区检测过程如图3所示，3.2分配社区正种子节点预算第二阶段需要为每个社区分配传播真相的正种子节点预算.设社交网络被划分为h个社区C=Ci,C2，,C h)，L(1,2)L(1,3).L(1,15)L(1,16)1passL(8,2)L(8,3)L(8,15)L(8,16)L(11,2)L(11,3)L(11,15)L(11,16)生成标签传播矩阵L(13,2)L(13,3)L(13,15)L(13,16)2dpass划分初始社区3npass合井社区图3社区检测的过程Fig.3Theprocess of community detection将h个社区的正种子节点的分配向量定义为k二(k1,kn),其中,-,k;=K,K表示图G中正种子节点的总预算，即如果将k分配给社区Ci,意味着最多可以从社区C,选取ki个正种子.在社区Ci中，谣言种子的负面影响程度越大，分配的正种子节点预算就应该越多.SR表示社区C,中传播谣言的负种子集合，S?表示社区C,中负种子数量，IFR，表示S?的影响范围，应根据社区中谣言的负面影响范围和社区规模来进行正种子分配，即=N,/N,其中,N.代表社区C,中节点的数量,N代表整个网络图中节点的数量.则k，可计算如下：IFR;k;XXK(8)IFR;C.EC从式（8)可以看出,IFR,对k,的影响较大，通常可以通过蒙特卡洛模拟的方法得到IFR，的估计值，但是该方法计算量大，效率低。考虑到信息在传播过程中存在衰减，三跳之内的节点间属于强连接关系 2 9,且大部分影响在一个小社区内流动,因此,对于SR中的每个节点,其影响范围Fiu可以通过计算社区C,中节点三跳内路径的激活概率之和来得到，则式（8)可改写为：Fiuk;一XXK(9)Fiu图4展示了F%的计算过程.CB0.20.30.20.40.1ED1C0.10.150.30.40MG图4F,的计算过程Fig.4Thecalculationof F,在社区C,中，A和B表示已经被谣言感染的种子结点，边上的数字代表该边的传播概率.以谣言源2-hop范围计算为例，可以得到：F1A=0.4+0.4X0.1+0.4X0.3+0.2+0.2X0.1+0.2X0.1515.End14.end forR13.IFR,XXK;IFR12.forC,inCdo1l.end for10.IFR+=IFR,;9./*IFR：各个社区谣言负影响力值之和*/8.IFRlist=IFRlistadd(IFR,);7./*IFRlist：存放各个社区的负影响力值*/6.endfor5.IFR,4./*计算各个社区C，的负影响力*/foruEsRdo2.for C,in C do1.Begin288第59 卷南京大学学报（自然科学）F1B=0.3+0.3X0.1+0.3X0.15+0.2+0.2X0.4基于上述过程，给出分配社区种子节点预算（A C B-NB）的伪代码，如下所示Algorithm 3ACB-NB(Allocating CommunityBlockingNodeBudget)Input：在线社交网络G(V,E);最终社区划分C;各个社区中谣言源集合SR；正种子节点的总预算K；Output：社区C传播真相种子节点预算k;3.3选择正种子集在得到社区传播正种子预算分配向量k=（k i，k h)后，为每个社区选择正种子，且正种子的预算满足K=,k.设传播真相的正种子集为ST=ST,ST，,ST),其中,ST是社区C,中的正种子集，STki.传统ECC(Edge Clustering Coefficient）描述了两个连接节点和边缘周围其他节点之间的“紧密性”，但仅仅利用拓扑结构来衡量谣言传播过程中边的重要性是不全面的，因为谣言扩散过程中每条边通过的信息量是不同的，通过的信息量越多，其传播能力就越强.定义6 谣言吞吐量用于衡量每条边上通过的谣言信息量，表示如下：RT_uu=p,ep(Ilerp(e)X p(u,)(10)其中，p表示谣言源SR到节点u或的路径.PI表示这些路径的集合，可表示为：PI=(p(u,w.),p(u,w,)/w,Esr)其中,p(u,w)是从u到w,的独立路径.通过融合网络拓扑性质和谣言吞吐量计算边凝聚度，可以更全面地衡量谣言传播过程中边的重要程度.定义7边凝聚度ECD(u,)=Z(11)RT,+(1-)-1,d,一1其中,Zu是在边缘上构建的三角形数，（u,)EE，d和d分别表示网络中节点u和的度，是影响因子.由于节点的重要性可以通过相邻边的重要程度来量化，因此，在边凝聚度的基础上，定义节点强度来衡量节点的重要性定义8节点强度NS(u)=Zven.ECD(u,)(12)EN其中，N是包含u的所有邻居的集合.基于以上阐述，本文提出的算法不断选取各个社区中节点强度最大的k个节点作为社区的正种子节点，直到预算K=0时停止.针对第三阶段传播真相正种子节点选择问题，提出的SSN算法的框架如下所示。Algorithm4SSN(Selecting Seed Nodes)Input：第i个社区C,=（V,E）;C,中的谣言源集合SR边凝聚度ECD;C,中的正种子节点的个数k;影响因子；Output:C,中传播真相种子节点集ST1.Begin2.Stemp=;3.foruin C,do4.Computing the ECD value of the node u;5.NS(u)-ZveN.ECD(u,);6.NS.list.add(NS(u);7.end for8./*降序排列NS_list*/9.Sort(NS_list)10.foruinNS_listdo11.ST=STUv;12.if len(sT)=ki13.break14.end for15.End4.2为对比算法评估CD-RBM算法的表289第2 期刘维等：CIC模型下基于社区检测的谣言抑制最大化方法基于上述三个阶段，最终可以得到传播真相的正种子集合ST=U=,ST.4实验设计4.1数据集及实验环境使用四个真实世界的数据集来验证CD-RBM算法，如表1所示.表1实验中使用的数据集Table1IDatasets used in experiments数据集节点（个）边（条）Email-Eu-Core100525571Ego-Facebook403988234Gnutella630120777Wiki-Vote7115103689Email-Eu-Core30：是来自欧洲大型研究机构的电子邮件数据集，每个边uu表示用户u向用户U发送了至少一封电子邮件.Ego-Facebook31:是一个来自Facebook应用程序的小社交图谱.Gnutella32：是一个大规模的点对点网络，每个节点代表一台主机，边表示主机之间的连接.Wiki-Votel16：包含Wikipedia的投票数据，其中的节点代表Wikipedia用户，从u到的边表示对u投票.在一台Intel(R）C o r e(T M)i 5处理器（4核)16GB内存的联想PC机上进行实验，操作系统为Windows10专业版（6 4位），编程语言为Python现，采用六种基准算法进行对比：Greedy33:采用蒙特卡洛模拟，每次选取谣言抑制效果最好的正种子节点.MaxDegree(MD)34:是一种启发式方法,从网络中选择前K个度最高节点作为正种子集.Random22：随机选择K个种子节点作为最佳的正种子集.Proximity22：是一种启发式方法，选择谣言源的直接邻居作为正种子集来阻止谣言的负面影响.Proximity-weight-degree(PWD)25 选择具有更多非活跃外邻居和更接近谣言源的正种子节点.Unblocking35是没有正种子传播真相时的基准算法.对于这些比较算法和CD-RBM,随机设置均匀分布在(0,0.4 的任意边（u,)EE的激活概率为p(u,),因为激活概率过高会导致不同算法的性能相似.随机选取每个数据集的1%作为源节点来传播谣言，所用算法都选择了不同大小（0 100)的种子集ST.将上述算法在CIC模型上进行测试，由于该模型是概率模型，使用10 0 0 次蒙特卡洛模拟来估计预期受影响节点的数量和算法的运行时间（单位：s).4.3实验结果及分析斤将CD-RBM和六种对比算法分别在从小到大的四个真实网络数据集上进行实验，从谣言抑制效果、真相扩散范围、影响因子、感染率变化和运行时间来评估CD-RBM算法和对比算法的性能。4.3.1谣言抑制效果的对比通过谣言扩散值来比较CD-RBM和其他算法的谣言抑制效果，如图5所示，横坐标表示正种子节点预算，纵坐标表示网络中的谣言扩散值.由图可见，随着正种子节点预算的增加，各算法的谣言扩散值逐渐降低，CD-RBM在四个真实世界数据集上的抑制效果都是最好的,Random的效果最差.在Email-Eu-Core数据集上（图5a），正种子节点预算小于7 0 时，CD-RBM的谣言抑制效果远高于Greedy和其他算法，即使正种子节点预算高于7 0,CD-RBM的抑制效果也与Greedy相同.在Ego-Facebook数据集上（图5b），正种子节点预算为10,50,7 0 时，PWD的效果陡然下降，在Gnutella数据集上（图5c）也发生了类似的现象.而CD-RBM在四个数据集上对谣言的抑制效果都随着正种子预算的增加而稳步增强，证明其具有良好的鲁棒性.在Wiki-Vote数据集上（图5d）,CD-R BM 的谣言抑制效果也是最好的，说明其具有良好的扩展性，即使在大数据集上，对谣言的抑制效果依然很好。此外，当正种子节点预算小于50 时，在Email-Eu-Core数据集上（图5a）,M D 抑制谣言传播的效果略优于PWD，在Wiki-Vote数据集上（图5d），PWD抑制谣言的效果明显差于MD,产生这一现290第59 卷南京大学学报（自然科学）90040008003500700300060025001500200040015003001000-200100500+01020304050607080901000102030405060708090100Thebudget of positiveseed nodesThebudget of positivebseed nodes(a)Email-Eu-Core(b)Ego-Facebook500030004500250040003500川2000300015002500200010001500500100001020304050607080901000102030405060708090100Thebudget of positiveseed nodesThe budget of positive seed nodes(c)Gnutella(d)Wiki-VoteCD-RBMGreedyMDPWDProximityRandomUnblocking图5各算法在四个数据集上的谣言抑制效果对比Fig.5Rumor blocking effects of different algorithms on four datasets象的原因是不同数据集的网络结构和直径不同.4.3.2真相扩散范围对比比为了评估CD-RBM中正种子节点传播真相的能力，图6 展示了改变正种子节点预算时真相扩散范围的变化.在Email-Eu-Core(图6 a)和Ego-Facebook(图6 b)数据集上，可见随着正种子节点预算的不断增加，Greedy优于PWD,Proximity和Random，但略低于CD-RBM.在Ego-Facebook(图6 b)数据集上，CD-RBM的真相扩散范围领先Greedy的幅度高于Email-Eu-Core（图6 a）,这是由于在Email-Eu-Core数据集中，节点的稠密度高达50%，Greedy更易于迭代性质良好的正节点，在Gnutella（图6c)和Wiki-Vote(图6 d)数据集上，可以发现随着数据集的不断变大，CD-RBM的真相扩散的范围不断变大，期望保护的节点也越多.而Proximity和Random在四个数据集上表现的性能都较差.4.3.3影响因子对比图7 展示了在不同数据集上算法中参数的变化对谣言抑制效果的影响.由图可见，=0.4时在小数据集Email-Eu-Core上,CD-RBM对谣言抑制的效果最好.对于大数据集，当0.55 0.6 5时，算法对谣言的抑制效果最好，说明在随机选取谣言源时，的选取无论在大数据集还是小数据集上都对谣言抑制发挥着非常重要的作用.4.3.4感染率对比定义9感染率描述节点被谣言的感染程度，计算如下：Number of rumor affected nodesinfectionrate=(13)Number of totalnodes图8 展示了在四个不同的真实世界数据集上，六种算法随着正种子节点预算的增加，社交网络中节点感染率的变化情况：由图可见，随着传播真相的正种子节点预算的不断增加，大多数算法的谣言感染率都在下降，但Random是不同的，在Email-Eu-Core(图8 a)和Ego-Facebook(图8 b)数据集上，Random的谣言感染率分别从8 4%和92%下降到41%和56%，而在Gnutella（图8 c）和Wiki-Vote（图8 d）数据集上，Random的谣言感染291第2 期维等：CIC模型下基于社区检测的谣言抑制最大化方法刘35007003000sapou600-2500500-20004001500300-200-1000100500-0001020304050607080901000102030405060708090100The budget of positive seed nodesThe budget of positive seed nodes(a)Email-Eu-Core(b)Ego-Facebook300035003000-2500250020002000150015001000二：10005005000001020304050607080901000102030405060708090100Thebudget of positiveseed nodesThebudget of positive seed nodes(c)Gnutella(d)Wiki-VoteCD-RBMGreedyMDPWDProximityRandom图6各算法在四个数据集上的真相扩散范围的对比Fig.6The truth spreading range of different algorithms on four datasets3500-Email-Eu-Core3000Ego-Facebook-Gnutella2500-+-Wiki-Vote20001500100050000.00.20.40.60.81.0图7影响因子对各算法的谣言抑制效果的影响Fig.7The effect of rumor blocking effects of differentalgorithms with different impact factor 率分别从47%和6 5%下降到34%和54%，说明Random的抑制谣言的效果是不稳定的,不能随着正种子预算的不断增加而稳步提升谣言抑制效果.而在四个真实数据集上，CD-RBM感染率下降的幅度都是最高的，感染率最低可达15%，即CD-RBM可以很好地抑制谣言的传播.此外，在Ego-Facebook数据集上（图8 b）CD-R BM 明显优于其他算法，与Greedy相比，下降的感染率最大为8%,与MD,PWD,Proximity,Random相比,下降的感染率分别为16%，30%，48%，53%.产生这种现象的原因是数据集Ego-Facebook的平均度为2 1.8 4,最大度为10 2 4，因此正种子节点在该网络中可以更加快速地传播真相，从而更好地抑制谣言的扩散.4.3.5运行时间对比比图9展示了六种算法在数据集Email-Eu-Core和Ego-Facebook上的运行时间.由图可见，CD-RBM的运行时间比Greedy短很多.在Ego-Facebook上,Greedy的运行时间长达7 8.3h，而CD-RBM只需5min，比贪心算法还要快三个数量级，此外，Proximity和Random的运行时间也很短，因为它们在选取正种子节点时不需要太多的计算成本，但由图5和图6 可知，这些算法对谣言的抑制效果远不如CD-RBM.PWD和MD的运行时间虽然也较短，但它们在不同数据集上的谣言抑制效果不如CD-RBM稳定292第59 卷南京大学学报（自然科学）infectionrateinfectionrate-0.90.9RandomRandomProximity-0.6Proximity-0.7PWDPWD0.40.4MDMDGreedy0.2Greedy0.2CD-RBM-CD-RBM-TTT10203040 506070 80 9010010203040 506070 80 90100The budget ofpositive seed nodesThe budget of positive seed nodes(a)Email-Eu-Core(b)Ego-Facebookinfectionrateinfectionrate0.50.7RandomRandom0.4-0.5ProximityProximityPWD-0.3PWD0.4MDMD-0.10.2CD-RBM-CD-RBM-1020304050 6070809010010203040506070 80 90100The budget of positive seed nodesThe budget of positive seed nodes(c)Gnutella(d)Wiki-Vote图8 在四个数据集上不同算法的社交网络感染率的对比Fig.8The infection rate of social networks of different algorithms on four datasets100000078.3hEmail-Eu-Core10000Ego-Facebook3.2h100001000100-100MDPWDRandomProximityCD-RBMGreedy图9各算法在Email-Eu-Core和Ego-Facebook数据集上的运行时间对比Fig.9The running time of different algorithms onEmail-Eu-Core andEgo-Facebookdatasets5结论本文主要研究了CIC模型下基于社区检测的谣言抑制最大化问题，提出了有效的算法CD-RBM.该算法首先考虑节点之间相互影响的概率，通过最大独立路径来计算节点接收的标签值，并在此基础上进行了社区划分；然后，利