CIC模型下基于社区检测的谣言抑制最大化方法.pdf
《CIC模型下基于社区检测的谣言抑制最大化方法.pdf》由会员分享,可在线阅读,更多相关《CIC模型下基于社区检测的谣言抑制最大化方法.pdf(13页珍藏版)》请在咨信网上搜索。
1、CNATURSCIENCEMar.,20232023年3月JOURNAIVERSITYVol.59,No.2第59 卷第2 期南京大学学报(自然科学DOI:10.13232/ki.jnju.2023.02.011CIC模型下基于社区检测的谣言抑制最大化方法刘维维*,杜宁宁,陈峻,洪青青(扬州大学信息工程学院,扬州,2 2 512 7)摘要:随着电子设备的日益普及和信息扩散的便利性,在线社交网络为各种负面信息的传播提供了高效的媒介.谣言是社交媒体上负面信息的突出形式之一,会引发社会动荡,造成经济损失,因此,快速有效地抑制谣言传播成为当前社交网络研究领域中的一个热点.提出一种有效的谣言抑制传播方法
2、,从网络中选取多个正种子节点来传播真相,抑制谣言的传播.首先采用竞争性独立级联(ConpetitiveIndependentCascade,CIC)模型来同时传播谣言和真相;其次,提出一种基于标签传播的社区检测算法对社交网络进行分解,并为各个社区分配正种子节点预算;最后,创新地提出节点强度来衡量网络中节点的重要性,并利用节点强度在各个社区中选取抑制谣言传播的初始正种子集.实验证明,该方法能达到与贪算法相匹配的抑制效果,且运行时间比贪婪算法快三个数量级。关键词:在线社交网络,社区结构,谣言抑制,竞争性独立级联模型中图分类号:TP393文献标志码:ARumor blocking maximizat
3、ion 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 socialn
4、etworks 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 h
5、ot 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 topropag
6、ate 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
7、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
8、 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 Soc
9、ial Networks,OSNs)平台,如2 0 2 2 年1月统计,Meta拥有数十亿的注册账户,月活跃用户超过2 8.9亿.通过这些平台,供应商和卖家可以选取一些“具有影响力”的用户(种子节点)来宣传产品、观点及思想 1 使尽可能多的用户购买该商品,基于此,影响力最大化(Influence Maximization,IM)应运而生 2-5,并得到了广泛的关注.IM的目标是在网络中寻找一部分关键的种子节点集合,通过传播模型使扩散的影响力最大化,但在没有严格审查时,产生和分享大量信息会使信息内容的真实性不断削弱,导致谣言在网络中肆意传播,造成一系列不利影响.例如,2 0 2 2 年4月国外上
10、映了一部名为“WatchtheWater的电影,声称COVID-19是“蛇毒”的合成版本,饮用水和COVID-19疫苗会导致“邪恶势力”的传播.虽然纯属杜撰,但该视频发布后一周内就在托管平台Rumble上获得近30 0 万次的观看和转发,谣言四起.由此可见,及时发现并抑制OSNs中的谣言传播已迫在眉睫 6 本文研究谣言抑制最大化(RumorBlockingMaximization,RBM)7,是IM的对偶问题,旨在选择一些种子节点来最大程度地阻止谣言的传播对RBM的研究已有不少工作(8-10 1.Newmanetal81证明,以大约10%的偏离度降序移除节点可以免疫谣言对其他节点的影响.Wan
11、getal通过发现和阻断一组未受感染的关键用户来最大程度地减少被感染用户的规模.另一方面,Kimuraet al101建议阻断重要的链接,而不是阻断节点.上述工作极大地推进了抑制谣言传播的研究,但仍存在挑战,具体地:(1)采用阻断节点的方式抑制谣言,没有考虑真实社交网络中的用户体验,而且在一定程度上会对网络结构造成破坏;(2)由于OSNs是无标度网络,即使采用阻断链接的方式来抑制谣言,用户仍然可以传播来自其他链接的谣言,因此阻断链接不是最佳选择;(3)谣言传播是多个谣言源通过合作方式来传播谣言的过程,因此,辟谣也应该通过合作的方式来传播真相,抑制谣言.此外,OSNs还具有社区结构的特征 11.
12、社区结构的一个重要特性是社区内的节点间联系密集,而与其他社区节点之间的联系稀疏,且消息在社区内传播比社区外传播要快得多.因此,合理利用网络中的社区结构,可以有效地提高谣言的抑制效果:本研究采用竞争策略,通过传播真相来抑制谣言的传播.首先,将OSNs划分成互不重叠的社区,在各个社区内实现谣言抑制最大化与已有的阻断策略相比,该方法既阻断了谣言的进一步传播,又在OSNs中扩散了真实消息,因而提升了人们识别谣言的能力传统的独立级联(Inde-pendentCascade,IC)模型只适用于一种信息的传播,而本文提出的方法是基于竞争性独立级联(Conpetitive Independent Cascad
13、e,CIC)模型的,目标是最大程度保护节点免受谣言的影响。本文的主要贡献:(1)基于OSNs中的CIC模型,提出三阶段策略来解决谣言抑制最大化问题.第一阶段,社区划分;第二阶段,进行传播真相的正种子预算分配;第三阶段,进行传播真相的正种子选择。(2)提出基于标签传播的社区检测算法来识别网络的社区结构,能有效地克服传统标签传播中容易出现的不易收敛的缺陷。(3)提出节点强度来量化真实传播过程中节点的重要性,能够在社区中选取性质良好的正种子节点来传播真相。(4)在四个真实数据集上进行的大量实验表明,本文提出的方法具有良好的可扩展性,在大规模数据集上,对谣言也有很好的抑制效果,1相关工作IM问题由Do
14、mingos and Richardson12提出,Kempe etal13提出一种贪婪爬山算法来解决IM问题,并证明该问题是NP-hard问题,在此基础上提出了独立级联(IC)和线性阈值(LinearThre-shold,LT)模型.由此,人们开始从理论和时间两个方面对IM问题进行广泛的研究,各种传播模型和算法相继被提出:RBM(Rumor Blocking Maximization)是 IM问题的扩展,最先由Budaketal14提出.IM问题通常考虑诸如积极信息和创新等理想事物的传284第59 卷南京大学学报(自然科学)播,而RBM旨在限制谣言的传播.目前,解决该问题的方法主要有三类:(
15、1)阻断有影响力的用户 15-18 .在信息传播过程中,确定OSNs中最有影响力的传播者是一个重要的问题,该类方法通过识别并阻断一组关键节点来最大程度减少网络中谣言的扩散.Yanetal15选择阻断节点集来最小化谣言源节点的激活概率之和,提出一种两阶段方法来生成候选集并选择要阻断的节点集.Juetal16研究如何最大程度阻断来自不确定来源的负面影响,并提出一种基于实时边子图中的传播树来计算正种子阻断增量的算法.Hosni and Lil17考虑OSNs中个体和社会的行为,提出一个多谣言传播模型,还提出一种动态阻断周期的方法来最小化谣言的影响,Zhu et al18研究了一个新的问题一一错误信息
16、影响的活动最小化,将一个节点集从网络中阻断,从而使节点之间的错误信息交互的总数最小化.但随意阻断节点,不仅会影响网络用户的体验,还有可能会破坏网络结构,(2)删除用户之间的链接,通过识别一组关键链接并将其删除来减少OSNs中谣言的传播(19-2 1.Scaman etal19将谣言的动态控制定义为动态资源分配问题,提出一种新颖的感染边缘最大减少控制策略,具有高效和易于实现的优点。Yan etal201提出一个启发式算法来不断迭代删除一条可以最小化谣言传播值的边,从而抑制谣言的传播与传统的谣言抑制问题不同,Guo et al21研究如何保护目标用户不受谣言的影响,称为目标保护最大化问题,目标是阻
17、断最小的边缘,使受谣言影响的目标节点的预期比例低于一定的值。但通过阻断链接的方式来抑制谣言会破坏网络结构,同时,谣言仍可以通过其他链接进一步传播,抑制作用不明显(3)传播正面信息来抑制谣言,即使用一组传递积极消息的节点对抗来自谣言源的扩散2-2 7 Heetal22研究了竞争线性值模型下社交网络中竞争影响力的传播,给出了一个有效的算法来找到种子节点,尽可能地阻止其竞争实体的影响传播.曹玖新等 2 3 研究竞争环境中利已信息的影响力最大化问题,考虑节点间交互内容的主题偏好特点,提出两种利已信息的影响力最大化算法.Tripathi and Rao25提出一种用于OSNs中信息扩散的点对点线性值模型
18、,并提出PWD(Proximity-Weight-Degree)算法选取正种子节点来抑制谣言.考虑谣言抑制的成本,Yao etal26用可信度作为成本来衡量一个人对他人的影响,提出一种最长有效跳的算法来抑制谣言.Sriniva-san and Dhinesh27提出一种防御性的谣言控制方法,利用群居昆虫的免疫策略来传播反谣言.但上述算法在运行效率方面存在不足,或是仅促使某一种竞争实体的影响力最大化,忽略对另一种竞争实体的抑制.针对以上问题,本文提出的算法可以实现在抑制谣言传播的同时,使真相的扩散范围最广,2传播模型和问题定义本节介绍使用的传播模型,并给出问题形式化的定义.2.1竞争性独立级联模
19、型(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.谣言和真相同时在网络中传播,每个节点最初都是不活动的,一旦节点被激活,就不会改变其状态,因此,先到达的级联将率先激活节点.在每一个时间步,如果一个节点被属于不同级联的两个或多个邻居成功激活,它将选择具有最高优先级
20、的那一个,假设谣言(R)具有更高的优先级,这种非对称性反映了社会心理学研究中经常提到的负面认知偏差.给定N)表示节点的邻居节点集,ST和SR分别表示传播真相的正种子集和传播谣言的负种子集,传播过程如下:(1)初始时刻,所有节点都处于非活动状态。(2)当t=O时,ST和SR中的节点分别被谣言和真相激活.(3)当t0时,在t一1时被激活的每个节点u尝试以Pu的概率激活每个不活动的邻居u.如第2 期285刘维等:CIC模型下基于社区检测的谣言抑制最大化方法果有多个节点同时到达节点,则它们激活 节点是相互独立的,且最多只有一个节点可以成功激活.节点u在t时刻只有一次机会去尝试激活其不活动的邻居。(4)
21、在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在
22、网络中传播真相和谣言.定义谣言抑制最大化问题如下:设(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,
23、*/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,中节点之间的边的
24、数量,IN|是社区C,中节点的数量.社区越稠密,节点间的联系越密集,则节点间交换信息的频率越高,这样就可以利用更快更精准地传播真相来抑制谣言的扩散。划分初始社区后会得到节点数较少的小社区,为了进一步提高传播正种子节点的谣言抑制效果,需要合并这些小社区.具体步骤如下:(1)计算所有社区中心之间的距离,合并中心距离最小的两个社区,(2)设置稠密度阈值n,当社区C,的稠密度大于值时合并结束.与Lietal28相似,本文的社区稠密度阈值设置为0.5.社区检测过程如图3所示,3.2分配社区正种子节点预算第二阶段需要为每个社区分配传播真相的正种子节点预算.设社交网络被划分为h个社区C=Ci,C2,,C h
25、),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中,谣言种子的负面
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- CIC 模型 基于 社区 检测 谣言 抑制 最大化 方法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。