南京大学学报(自然科学版) ›› 2023, Vol. 59 ›› Issue (2): 282–294.doi: 10.13232/j.cnki.jnju.2023.02.011

• • 上一篇    下一篇

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

刘维(), 杜宁宁, 陈崚, 洪青青   

  1. 扬州大学信息工程学院，扬州，225127
  • 收稿日期:2022-11-14 出版日期:2023-03-31 发布日期:2023-04-07
  • 通讯作者: 刘维 E-mail:yzliuwei@126.com
  • 基金资助:
    国家自然科学基金(61971233);江苏省自然科学基金(BK20170513)

Rumor blocking maximization method based on community detection under the CIC model

Wei Liu(), Ningning Du, Ling Chen, Qingqing Hong   

  1. College of Information Engineering，Yangzhou University，Yangzhou，225127，China
  • Received:2022-11-14 Online:2023-03-31 Published:2023-04-07
  • Contact: Wei Liu E-mail:yzliuwei@126.com

RichHTML

13

PDF (PC)

468

摘要：

随着电子设备的日益普及和信息扩散的便利性，在线社交网络为各种负面信息的传播提供了高效的媒介.谣言是社交媒体上负面信息的突出形式之一，会引发社会动荡，造成经济损失，因此，快速有效地抑制谣言传播成为当前社交网络研究领域中的一个热点.提出一种有效的谣言抑制传播方法，从网络中选取多个正种子节点来传播真相，抑制谣言的传播.首先采用竞争性独立级联（Conpetitive Independent Cascade，CIC）模型来同时传播谣言和真相；其次，提出一种基于标签传播的社区检测算法对社交网络进行分解，并为各个社区分配正种子节点预算；最后，创新地提出节点强度来衡量网络中节点的重要性，并利用节点强度在各个社区中选取抑制谣言传播的初始正种子集.实验证明，该方法能达到与贪婪算法相匹配的抑制效果，且运行时间比贪婪算法快三个数量级.

关键词: 在线社交网络, 社区结构, 谣言抑制, 竞争性独立级联模型

Abstract:

With the increasing popularity of electronic devices and the convenience of information diffusion，online social networks provide an efficient medium for the propagation of various negative information. Rumors are one of the prominent forms of negative information on social media，which trigger social unrest and cause economic losses. Therefore，how to quickly 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 network to spread the truth to block rumor propagation. Firstly，we adopt a Competitive Independent Cascade (CIC) model to propagate rumors and truth simultaneously. Secondly，we propose a community detection method based on label propagation to decompose social networks and allocated positive seed node budgets to each community. Finally，we propose a novel node strength to measure the importance of nodes in the network and use it to select the initial positive seed set which blocks the spread of rumors in each community. Experimental results show that the proposed method achieves the same blocking effect as 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 Cascade model

中图分类号: 

  • TP393

图1

一个简单的扩散过程示例"

图2

节点间标签值的计算"

图3

社区检测的过程"

图4

Fiv 的计算过程"

表1

实验中使用的数据集"

数据集节点（个）边（条）
Email⁃Eu⁃Core100525571
Ego⁃Facebook403988234
Gnutella630120777
Wiki⁃Vote7115103689

图5

各算法在四个数据集上的谣言抑制效果对比"

图6

各算法在四个数据集上的真相扩散范围的对比"

图7

影响因子γ对各算法的谣言抑制效果的影响"

图8

在四个数据集上不同算法的社交网络感染率的对比"

图9

各算法在Email?Eu?Core和Ego?Facebook数据集上的运行时间对比"

1 Nguyen H， Zheng R. On budgeted influence maximization in social networks. IEEE Journal on Selected Areas in Communications，2013，31(6)：1084-1094.
2 Cheng J J， Yang K， Yang Z Y，et al. Influence maximization based on community structure and second?hop neighborhoods. Applied Intelligence，2022，52(10)：10829-10844.
3 Wang Y， Zheng Y N， Shi X L，et al. An effective heuristic clustering algorithm for mining multiple critical nodes in complex networks. Physica A：Statistical Mechanics and its Applications，2022(588)：126535.
4 Li W M， Li Z， Luvembe A M，et al. Influence maximization algorithm based on Gaussian propagation model. Information Sciences，2021(568)：386-402.
5 Chen J， Liu J C. Research on a novel influence maximization algorithm based on community structure. Journal of Physics：Conference Series，2020，1631(1)：012064.
6 Doerr B， Fouz M， Friedrich T. Why rumors spread so quickly in social networks. Communications of the ACM，2012，55(6)：70-75.
7 Chen B L， Jiang W X， Chen Y X，et al. Influence blocking maximization on networks：Models，methods and applications. Physics Reports，2022(976)：1-54.
8 Newman M E J， Forrest S， Balthrop J. Email networks and the spread of computer viruses. Physical Review E，2002，66(3)：035101.
9 Wang S Z， Zhao X J， Chen Y，et al. Negative influence minimizing by blocking nodes in social networks∥Proceedings of the 17th AAAI Conference on Late?Breaking Developments in the Field of Artificial Intelligence. Bellevue，WA，USA：AAAI Press，2013：134-136.
10 Kimura M， Saito K， Motoda H. Blocking links to minimize contamination spread in a social network. ACM Transactions on Knowledge Discovery from Data，2009，3(2)：9.
11 Ma T H， Liu Q， Cao J，et al. LGIEM：Global and local node influence based community detection. Future Generation Computer Systems，2020(105)：533-546.
12 Domingos P， Richardson M. Mining the network value of customers∥Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. San Francisco，CA，USA：ACM，2001：57-66.
13 Kempe D， Kleinberg J， Tardos é. Maximizing the spread of influence through a social network∥Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Washington DC，WA，USA：ACM，2003：137-146.
14 Budak C， Agrawal D， El Abbadi A. Limiting the spread of misinformation in social networks∥Proceedings of the 20th International Conference on World Wide Web. Hyderabad，India：ACM，2011：665-674.
15 Yan R D， Li D Y， Wu W L，et al. Minimizing influence of rumors by blockers on social networks∥Proceedings of the 7th International Conference on Computational Social Networks. Springer Berlin Heidelberg，2018：1-12.
16 Ju W J， Chen L， Li B，et al. Node deletion?based algorithm for blocking maximizing on negative influence from uncertain sources. Knowledge?Based Systems，2021(231)：107451.
17 Hosni A I E， Li K. Minimizing the influence of rumors during breaking news events in online social networks. Knowledge?Based Systems，2020(193)：105452.
18 Zhu J M， Ni P K， Wang G Q. Activity minimization of misinformation influence in online social networks. IEEE Transactions on Computational Social Systems，2020，7(4)：897-906.
19 Scaman K， Kalogeratos A， Vayatis N. A greedy approach for dynamic control of diffusion processes in networks∥2015 IEEE 27th International Conference on Tools with Artificial Intelligence. Vietri Sul Mare，Italy：IEEE，2015：652-659.
20 Yan R D， Li Y， Wu W L，et al. Rumor blocking through online link deletion on social networks. ACM Transactions on Knowledge Discovery from Data，2019，13(2)：16.
21 Guo J X， Li Y， Wu W L. Targeted protection maximization in social networks. IEEE Transactions on Network Science and Engineering，2020，7(3)：1645-1655.
22 He X R， Song G J， Chen W，et al. Influence blocking maximization in social networks under the competitive linear threshold model∥Proceedings of the 12th SIAM International Conference on Data Mining. Anaheim，CA，USA：Society for Industrial and Applied Mathematics，2012：463-474.
23 曹玖新，闵绘宇，王浩然,等. 竞争环境中基于主题偏好的利己信息影响力最大化算法. 计算机学报，2019，42(7)：1495-1510.
Cao J X， Min H Y， Wang H R，et al. Self?interest influence maximization algorithm based on subject preference in competitive environment. Chinese Journal of Computers，2019，42(7)：1495-1510.
24 Chen L， Zhang Y L， Chen Y X，et al. Negative influence blocking maximization with uncertain sources under the independent cascade model. Information Sciences，2021(564)：343-367.
25 Tripathi R， Rao S. Rumor containment in peer?to?peer message sharing online social networks. International Journal of Data Science and Analytics，2022，13(3)：185-198.
26 Yao X P， Liang G X， Gu C L，et al. Rumors clarification with minimum credibility in social networks. Computer Networks，2021(193)：108123.
27 Srinivasan S， Dhinesh B L D. A bio?inspired defensive rumor confinement strategy in online social networks. Journal of Organizational and End User Computing，2021，33(1)：47-70.
28 Li X L， Foo C S， Ng S K. Discovering protein complexes in dense reliable neighborhoods of protein interaction networks∥Markstein P，Xu Y. Computa?tional Systems Bioinformatics. San Diego，CA，USA：University of California,2007：157-168.
29 Christakis N A， Fowler J H. Social contagion theory：Examining dynamic social networks and human behavior. Statistics in medicine，2013，32(4)：556-577.
30 Pham C V， Pham D V， Bui B Q，et al. Minimum budget for misinformation detection in online social networks with provable guarantees. Optimization Letters，2022，16(2)：515-544.
31 Zhu W L， Yang W， Xuan S C，et al. Location?based seeds selection for influence blocking maximization in social networks. IEEE Access，2019(7)：27272-27287.
32 Pham C V， Phu Q V， Hoang H X，et al. Minimum budget for misinformation blocking in online social networks. Journal of Combinatorial Optimization，2019，38(4)：1101-1127.
33 Pham C V， Dinh H M， Nguyen H D，et al. Limiting the spread of epidemics within time constraint on online social networks∥Proceedings of the 8th International Symposium on Information and Communication Technology. Nha Trang City，Viet Nam：ACM，2017：262-269.
34 Manouchehri M A， Helfroush M S， Danyali H. A theoretically guaranteed approach to efficiently block the influence of misinformation in social networks. IEEE Transactions on Computational Social Systems，2021，8(3)：716-727.
35 Tong G M， Wu W L， Guo L，et al. An efficient randomized algorithm for rumor blocking in online social networks. IEEE Transactions on Network cience and Engineering，2020，7(2)：845-854.
[1] 郑文萍, 刘美麟, 穆俊芳, 杨贵. 一种基于节点稳定性的社区发现算法[J]. 南京大学学报(自然科学版), 2021, 57(1): 101-109.
[2] 赵卫绩1，2，张凤斌1*，刘井莲2. 一种基于加权共同邻居相似度的局部社区发现算法[J]. 南京大学学报(自然科学版), 2018, 54(4): 751-.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!

版权所有 © 2021 《南京大学学报(自然科学)》

地址：江苏省南京市鼓楼区汉口路22号，南京大学学报编辑部，210093

电话：025-83592704 , 传真：025-83592704        技术支持：北京玛格泰克科技发展有限公司