[1]陈伯伦,朱国畅,纪敏,等.代价约束下基于随机游走的负影响力传播抑制方法[J].智能系统学报,2022,17(2):266-275.[doi:10.11992/tis.202101037]
CHEN Bolun,ZHU Guochang,JI Min,et al.Negative influence propagation suppression method based on a random walk under cost constraint[J].CAAI Transactions on Intelligent Systems,2022,17(2):266-275.[doi:10.11992/tis.202101037]
点击复制
CHEN Bolun,ZHU Guochang,JI Min,et al.Negative influence propagation suppression method based on a random walk under cost constraint[J].CAAI Transactions on Intelligent Systems,2022,17(2):266-275.[doi:10.11992/tis.202101037]
代价约束下基于随机游走的负影响力传播抑制方法
《智能系统学报》[ISSN 1673-4785/CN 23-1538/TP] 卷:
17
期数:
2022年第2期
页码:
266-275
栏目:
学术论文—机器学习
出版日期:
2022-03-05
- Title:
- Negative influence propagation suppression method based on a random walk under cost constraint
- Keywords:
- social network; cost constraint; information diffusion; superposed random walk; negative influence; propagation inhibition; percolation; sub-graph
- 分类号:
- TP301.6
- 摘要:
- 在社交网络的信息传播机制中，不同用户之间信息扩散往往会受到用户之间影响力的影响，因此开展复杂网络分析研究显得格外必要。首先研究在代价约束下，社交网络的影响力传播模型，在未知网络传播原理的情况下，研究如何利用叠加的随机游走策略对网络的影响力传播进行度量，将影响力传播的范围控制在某一子图中，设计出抑制负影响力传播的有效方法。在此基础上，通过渗流来对抑制节点的范围进行控制。实验证明，本文的算法不仅可以有效地限制负影响力的传播，而且在代价约束下能够取得较好的性能。本文不仅对分析、理解和预测网络的拓扑结构、功能和动力学行为具有十分重要的理论意义，而且在舆情管控、虚假信息抑制等领域中也发挥着重要的作用。
- Abstract:
- The information diffusion mechanism of social networking among different users is often affected by the influence among users, so it is particularly necessary to carry out a complex network analysis. In this paper, we first study the influence propagation model of complex networks with cost constraints. In the case of the unknown network propagation principle, we use a superposed random walk strategy to measure the influence propagation of networks, control the scope of influence propagation in a certain sub-graph, and design an effective method to suppress negative influence propagation. On this basis, the idea of percolation is introduced to determine the set size of restraining nodes. Experimental results show that this algorithm can effectively limit the propagation of negative influence and achieve better performance under cost constraints. This paper is of great theoretical significance to analyzing, understanding, and predicting social network’s topological structure, function, and dynamic behavior. It plays an important role in public opinion control and false information suppression.
- 参考文献/References:
-
[1] HUANG Keke, WANG Sibo, BEVILACQUA G, et al. Revisiting the stop-and-stare algorithms for influence maximization[J]. Proceedings of the VLDB endowment, 2017, 10(9): 913–924.
[2] 吴信东, 李毅, 李磊. 在线社交网络影响力分析[J]. 计算机学报, 2014, 37(4): 735–752
WU Xindong, LI Yi, LI Lei. Influence analysis of online social networks[J]. Chinese journal of computers, 2014, 37(4): 735–752
[3] MORONE F, MAKSE H A. Influence maximization in complex networks through optimal percolation[J]. Nature, 2015, 524(7563): 65–68.
[4] LYU Linyuan, CHEN Duanbing, REN Xiaolong, et al. Vital nodes identification in complex networks[J]. Physics reports, 2016, 650: 1–63.
[5] TIAN Huaiyu, LIU Yonghonh, LI Yidan, et al. An investigation of transmission control measures during the first 50 days of the COVID-19 epidemic in China[J]. Science, 2020, 368(6491): 638–642.
[6] CALIò A, INTERDONATO R, PULICE C, et al. Topology-driven diversity for targeted influence maximization with application to user engagement in social networks[J]. IEEE transactions on knowledge and data engineering, 2018, 30(12): 2421–2434.
[7] CHAKRABORTY S, STEIN S, BREDE M, et al. Competitive influence maximisation using voting dynamics[C]//Proceedings of 2019 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. Vancouver, Canada, 2019: 978-985.
[8] 刘雅辉, 靳小龙, 沈华伟, 等. 社交媒体中的谣言识别研究综述[J]. 计算机学报, 2018, 41(7): 1536–1558
LIU Yahui, JIN Xiaolong, SHEN Huawei, et al. A survey on rumor identification over social media[J]. Chinese journal of computers, 2018, 41(7): 1536–1558
[9] HE Xinran, SONG Guojie, CHEN Wei, et al. Influence blocking maximization in social networks under the competitive linear threshold model[C]//Proceedings of the 12th SIAM International Conference on Data Mining. Anaheim, USA, 2012: 463-474.
[10] ARAZKHANI N, MEYBODI M R, REZVANIAN A. Influence blocking maximization in social network using centrality measures[C]//Proceedings of the 5th Conference on Knowledge Based Engineering and Innovation. Tehran, Iran, 2019: 492-497.
[11] 谭振华, 时迎成, 石楠翔, 等. 基于引力学的在线社交网络空间谣言传播分析模型[J]. 计算机研究与发展, 2017, 54(11): 2586–2599
TAN Zhenhua, SHI Yingcheng, SHI Nanxiang, et al. Rumor propagation analysis model inspired by gravity theory for online social networks[J]. Journal of computer research and development, 2017, 54(11): 2586–2599
[12] TONG Guangmo, WU Weili, GUO Ling, et al. An efficient randomized algorithm for rumor blocking in online social networks[J]. IEEE transactions on network science and engineering, 2020, 7(2): 845–854.
[13] 刘亚州, 王静, 潘晓中, 等. 节点影响力下无标度网络谣言传播研究[J]. 小型微型计算机系统, 2018, 39(11): 2375–2379
LIU Yazhou, WANG Jing, PAN Xiaozhong, et al. Research on scale-free network rumor spreading under node influence[J]. Journal of Chinese computer systems, 2018, 39(11): 2375–2379
[14] LEE C L, SUNG C E, MA Haoshang, et al. IDR: positive influence maximization and negative influence minimization under competitive linear threshold model[C]//Proceedings of the 20th IEEE International Conference on Mobile Data Management (MDM). Hong Kong, China, 2019: 501-506.
[15] 曹玖新, 董丹, 徐顺, 等. 一种基于k-核的社会网络影响最大化算法[J]. 计算机学报, 2015, 38(2): 238–248
CAO Jiuxin, DONG Dan, XU Shun, et al. A k-core based algorithm for influence maximization in social networks[J]. Chinese journal of computers, 2015, 38(2): 238–248
[16] PENG Sancheng, WU Min, WANG Guojun, et al. Containing smartphone worm propagation with an influence maximization algorithm[J]. Computer networks, 2014, 74: 103–113.
[17] 陈晋音, 张敦杰, 林翔, 等. 基于影响力最大化策略的抑制虚假消息传播的方法[J]. 计算机科学, 2020, 47(S1): 17–23, 33
CHEN Jinyin, ZHANG Dunjie, LIN Xiang, et al. False message propagation suppression based on influence maximization[J]. Computer science, 2020, 47(S1): 17–23, 33
[18] 江成, 刘室辰. 谣言网络多级传播路径下关键引爆点识别模型和算法研究[J]. 情报杂志, 2020, 39(6): 152–158
JIANG Cheng, LIU Shichen. Research on models and algorithms for identifying trigger points of rumor network under multi-level propagation paths[J]. Journal of intelligence, 2020, 39(6): 152–158
[19] ARAZKHANI N, MEYBODI M R, REZVANIAN A. An efficient algorithm for influence blocking maximization based on community detection[C]//Proceedings of the 5th International Conference on Web Research. Tehran, Iran, 2019: 258-263.
[20] LV Jiaguo, YANG Bin, YANG Zhen, et al. A community-based algorithm for influence blocking maximization in social networks[J]. Cluster computing, 2019, 22(3): 5587–5602.
[21] WANG Biao, CHEN Ge, FU Luoyi, et al. DRIMUX: dynamic rumor influence minimization with user experience in social networks[J]. IEEE transactions on knowledge and data engineering, 2017, 29(10): 2168–2181.
[22] ZHU Wenlong, YANG Wu, XUAN Shichang, et al. Location-aware influence blocking maximization in social networks[J]. IEEE access, 2018, 6: 61462–61477.
[23] YIN Hao, BENSON A R, LESKOVEC J, et al. Local higher-order graph clustering[C]//Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Halifax, Canada, 2017: 555-564.
[24] TRAUD A L, MUCHA P J, PORTER M A. Social structure of Facebook networks[J]. Physica A: statistical mechanics and its applications, 2012, 391(16): 4165–4180.
[25] DüNKER D, KUNEGIS J. Social networking by proxy: analysis of Dogster, Catster and Hamsterster[C]//Proceedings of the 24th International Conference on World Wide Web. Florence, Italy, 2015: 361-362.
[26] TRAUD A L, KELSIC E D, MUCHA P J, et al. Comparing community Structure to characteristics in online collegiate social networks[J]. SIAM review, 2011, 53(3): 526–543.
[27] WANG Huijuan, HERNANDEZ J M, VAN MIEGHEM P. Betweenness centrality in a weighted network[J]. Physical review E, 2008, 77(4): 046105.
[28] BOLDI P, SANTINI M, VIGNA S. PageRank: functional dependencies[J]. ACM transactions on information systems, 2009, 27(4): 19.
[29] MITZENMACHER M, UPFAL E. Probability and computing: Randomized algorithms and probabilistic analysis[J]. The bulletin of symbolic logic, 2006, 12(2): 304–307.
- 相似文献/References:
-
[1]孔庆超,毛文吉,张育浩.社交网站中用户评论行为预测[J].智能系统学报,2015,10(3):349.[doi:10.3969/j.issn.1673-4785.201403019]
KONG Qingchao,MAO Wenji,ZHANG Yuhao.User comment behavior prediction in social networking sites[J].CAAI Transactions on Intelligent Systems,2015,10():349.[doi:10.3969/j.issn.1673-4785.201403019]
[2]王景丽,许立波,庞超逸.复杂网络中的在线社交网络演化模型[J].智能系统学报,2015,10(6):949.[doi:10.11992/tis.201507042]
WANG Jingli,XU Libo,PANG Chaoyi.Evolution model of online social networks based on complex networks[J].CAAI Transactions on Intelligent Systems,2015,10():949.[doi:10.11992/tis.201507042]
[3]石磊,杜军平,周亦鹏,等.在线社交网络挖掘与搜索技术研究[J].智能系统学报,2016,11(6):777.[doi:10.11992/tis.201612007]
SHI Lei,DU Junping,ZHOU Yipeng,et al.A survey on online social network mining and search[J].CAAI Transactions on Intelligent Systems,2016,11():777.[doi:10.11992/tis.201612007]
[4]花勇,陈伯伦,朱国畅,等.基于渗流模型的影响力最大化算法[J].智能系统学报,2019,14(6):1262.[doi:10.11992/tis.201906039]
HUA Yong,CHEN Bolun,ZHU Guochang,et al.An influence maximization algorithm based on percolation model[J].CAAI Transactions on Intelligent Systems,2019,14():1262.[doi:10.11992/tis.201906039]
[5]熊尧,李弼程,王子玥.基于两级传播理论的舆论超网络传播分析[J].智能系统学报,2020,15(5):870.[doi:10.11992/tis.201903011]
XIONG Yao,LI Bicheng,WANG Ziyue.Analysis of public opinions in network communication based on the two-level communication theory[J].CAAI Transactions on Intelligent Systems,2020,15():870.[doi:10.11992/tis.201903011]
[6]常新功,王金珏.基于图卷积集成的网络表示学习[J].智能系统学报,2022,17(3):547.[doi:10.11992/tis.202107048]
CHANG Xingong,WANG Jinjue.Network representation learning using graph convolution ensemble[J].CAAI Transactions on Intelligent Systems,2022,17():547.[doi:10.11992/tis.202107048]
[7]孟祥福,赖贞祥,崔江燕.集合空间关键字内聚组查询方法[J].智能系统学报,2024,19(3):707.[doi:10.11992/tis.202211013]
MENG Xiangfu,LAI Zhenxiang,CUI Jiangyan.Cohesive group query approach for collective spatial keywords[J].CAAI Transactions on Intelligent Systems,2024,19():707.[doi:10.11992/tis.202211013]
备注/Memo
收稿日期:2021-01-29。
基金项目:国家自然科学基金项目(61602202)；江苏省自然科学基金项目(BK20160428)；江苏省高等学校自然科学研究项目(20KJA520008)
作者简介:陈伯伦，副教授，主要研究方向为复杂网络分析和算法优化。主持国家自然科学基金项目、江苏省自然科学基金项目以及企业横向课题多项，曾获江苏省计算机学会科技进步三等奖。发表学术论文50余篇;朱国畅，硕士研究生，主要研究方向为复杂网络分析、深度学习;纪敏，副教授，主要研究方向为复杂网络分析、链接预测、推荐系统
通讯作者:陈伯伦.E-mail:chenbolun@hyit.edu.cn
更新日期/Last Update:
1900-01-01