计算机科学 ›› 2022, Vol. 49 ›› Issue (11): 316-325.doi: 10.11896/jsjkx.211000043
宋新月, 帅天平, 陈彬
SONG Xin-yue, SHUAI Tian-ping, CHEN Bin
摘要: 在线社交网络如微信等的普及,使人们更加关注信息传播的问题。虚假信息在社交网络中进行传播可能会造成很严重的后果,比如经济损失或者公众恐慌等。因此,需要采取相关的措施来控制虚假信息的传播。传统的虚假信息控制方法主要通过向网络中的部分节点传播真实信息,让真实信息和虚假信息进行竞争来减小虚假信息的影响。文中将传播真实信息和加边的方式相结合,提出了一个虚假信息修正最大化问题。该问题是NP-难的,其目标函数值的计算是#P-难的。由于目标函数既不是次模的也不是超模的,因此采用三明治近似策略来求解该问题。为此,构造目标函数的次模的上界和下界函数,利用反向影响采样技术在基数约束下求解上界和下界函数,最终得到原问题的一个数据相关的近似解。通过在3个真实网络的数据集上进行仿真实验,验证了所提算法的有效性。
中图分类号:
[1]KEMPE D,KLEINBERG J,TARDOS É.Maximizing the spread of infıuence through a social network[C]//Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM,2003:137-146. [2]CHEN W,WANG C,WANG Y J.Scalable influence maximization for prevalent viral marketing in large-scale social networks[C]//Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM,2010:1029-1038. [3]BROGS C,BRAUTBAR M,CHAYES J,et al.Maximizing social infıuence in nearly optimal time [C]//Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms.SIAM,2014:946-957. [4]TANG Y Z,XIAO X K,SHI Y C.Influence maximization:near-optimal time complexity meets practical efficiency[C]//Procee-dings of the 2014 ACM SIGMOD International Conference on Management of Data.ACM,2014:75-86. [5]TANG Y Z,SHI Y C,XIAO X K.Influence Maximization in Near-Linear Time:A Martingale Approach[C]//Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data.ACM,2015:1539-1554. [6]HU Q C,ZHANG Y,XING C X.K-clique Heuristic Algorithm for Influence Maximization in Social Network[J].Computer Science,2018,45(6):32-35. [7]KONG F,LI Q Z,LI S.Survey on Online Influence Maximization [J].Computer Science,2020,47(5):7-13. [8]TAN Q,ZHANG F L,ZHANG Z Y,et al.Modeling Methods of Social Network User Influence [J].Computer Science,2021,48(2):76-86. [9]TAN Q,ZHANG F L,WANG T,et al.Social Network User Influence Evaluation Algorithm Integrating Structure Centrality [J].Computer Science,2021,48(7):124-129. [10]DOERR B,FOUZ M,FRIEDRICH T.Why rumors spread so quickly in social networks [J].Communications of the ACM,2012,55(6):70-75. [11]BUDAK C,AGRAWAL D,ABBADI E A.Limiting the spread of misinformation in social networks[C]//Proceedings of the 20th International Conference on World Wide Web.ACM,2011:665-674. [12]HE X R,SONG G J,CHEN W,et al.Influence blocking maximization in social networks under the competitive linear thre-shold model[C]//Proceedings of the 2012 SIAM International Conference on Data Mining.SIAM,2012:463-474. [13]TONG G M,WU W L,GUO L,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. [14]WANG S Z,ZHAO X J,CHEN Y,et al.Negative influence mi-nimizing by blocking nodes in social networks [C]//Proceedings of the 17th AAAI Conference on Late-Breaking Developments in the Field of Artificial Intelligence.ACM,2013:134-136. [15]YAN R D,LI D Y,WU W L,et al.Negative influence minimizing by blocking nodes in social networks [J].IEEE Transactions on Network Science and Engineering,2020,7(3):1067-1078. [16]KIMURA M,SAITO K,MOTODA H.Minimizing the spread of contamination by blocking links in a network[C]//Proceedings of the 23rd National Conference on Artificial Intelligence-Vo-lume 2.ACM,2008:1175-1180. [17]KUHLMAN C J,TULI G,SWARUP S,et al.Blocking simple and complex contagion by edge removal [C]//IEEE 13th International Conference on Data Mining.IEEE,2013:399-408. [18]CHEN J Y,ZHANG D J,LIN X,et al.False Message Propagation Suppression Based on Influence Maximization [J].Compu-ter Science,2020,47(S1):17-23. [19]VOSOUGHI S,ROY D,ARAL S.The spread of true and false news online [J].Science,2018,359(6380):1146-1151. [20]CHAOJI V,RANU S,RASTOGI R,et al.Recommendations to boost content spread in social networks[C]//Proceedings of the 21st International Conference on World Wide Web.ACM,2012:529-538. [21]D’ANGELO G,SEVERINI L,VELAJ Y.Recommending links through influence maximization[J].Theoretical Computer Science,2019,764:30-41. [22]YU L,LI G H,YUAN L.Maximizing Boosted Influence Spread with Edge Addition in Online Social Networks[J].ACM/IMS Transactions on Data Science,2020,1(2):1-21. [23]KARP R M.Reducibility among combinatorial problems[C]//Complexity of Computer Computations.Springer,1972:85-103. [24]VALIANT L G.The complexity of enumeration and reliability problems [J].SIAM Journal on Computing,1979,8(3):410-421. [25]LU W,CHEN W,LAKSHMANAN L V S.From competition to complementarity:Comparative influence diffusion and maximization [J].Proceedings of the VLDB Endowment,2015,9(2):60-71. [26]ROSSI R A,AHMED N K.The network data repository with interactive graph analytics and visualization[EB/OL].http://networkrepositoy.com. [27]GAO C,LIU J,ZHONG N.Network immunization and virus propagation in email networks experimental evaluation and ana-lysis[J].Knowledge and Information Systems,2011,27(2):60-71. [28]KHALIL E,DIKINA B,SONG L.Scalable diffusion-aware optimization of network topology [C]//Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Disco-very and Data Mining.ACM,2014:1226-1235. |
[1] | 孔世明, 冯永, 张嘉云. 融合知识图谱的多层次传承影响力计算与泛化研究 Multi-level Inheritance Influence Calculation and Generalization Based on Knowledge Graph 计算机科学, 2022, 49(9): 221-227. https://doi.org/10.11896/jsjkx.210700144 |
[2] | 王剑, 彭雨琦, 赵宇斐, 杨健. 基于深度学习的社交网络舆情信息抽取方法综述 Survey of Social Network Public Opinion Information Extraction Based on Deep Learning 计算机科学, 2022, 49(8): 279-293. https://doi.org/10.11896/jsjkx.220300099 |
[3] | 魏鹏, 马玉亮, 袁野, 吴安彪. 用户行为驱动的时序影响力最大化问题研究 Study on Temporal Influence Maximization Driven by User Behavior 计算机科学, 2022, 49(6): 119-126. https://doi.org/10.11896/jsjkx.210700145 |
[4] | 余皑欣, 冯秀芳, 孙静宇. 结合物品相似性的社交信任推荐算法 Social Trust Recommendation Algorithm Combining Item Similarity 计算机科学, 2022, 49(5): 144-151. https://doi.org/10.11896/jsjkx.210300217 |
[5] | 畅雅雯, 杨波, 高玥琳, 黄靖云. 基于SEIR的微信公众号信息传播建模与分析 Modeling and Analysis of WeChat Official Account Information Dissemination Based on SEIR 计算机科学, 2022, 49(4): 56-66. https://doi.org/10.11896/jsjkx.210900169 |
[6] | 左园林, 龚月姣, 陈伟能. 成本受限条件下的社交网络影响最大化方法 Budget-aware Influence Maximization in Social Networks 计算机科学, 2022, 49(4): 100-109. https://doi.org/10.11896/jsjkx.210300228 |
[7] | 郭磊, 马廷淮. 基于好友亲密度的用户匹配 Friend Closeness Based User Matching 计算机科学, 2022, 49(3): 113-120. https://doi.org/10.11896/jsjkx.210200137 |
[8] | 李家文, 郭炳晖, 杨小博, 郑志明. 基于信息传播的致病基因识别研究 Disease Genes Recognition Based on Information Propagation 计算机科学, 2022, 49(1): 264-270. https://doi.org/10.11896/jsjkx.201100129 |
[9] | 王剑, 王玉翠, 黄梦杰. 社交网络中的虚假信息:定义、检测及控制 False Information in Social Networks:Definition,Detection and Control 计算机科学, 2021, 48(8): 263-277. https://doi.org/10.11896/jsjkx.210300053 |
[10] | 桑春艳, 胥文, 贾朝龙, 文俊浩. 社交网络中基于注意力机制的网络舆情事件演化趋势预测 Prediction of Evolution Trend of Online Public Opinion Events Based on Attention Mechanism in Social Networks 计算机科学, 2021, 48(7): 118-123. https://doi.org/10.11896/jsjkx.200600155 |
[11] | 谭琪, 张凤荔, 王婷, 王瑞锦, 周世杰. 融入结构度中心性的社交网络用户影响力评估算法 Social Network User Influence Evaluation Algorithm Integrating Structure Centrality 计算机科学, 2021, 48(7): 124-129. https://doi.org/10.11896/jsjkx.200600096 |
[12] | 张人之, 朱焱. 基于主动学习的社交网络恶意用户检测方法 Malicious User Detection Method for Social Network Based on Active Learning 计算机科学, 2021, 48(6): 332-337. https://doi.org/10.11896/jsjkx.200700151 |
[13] | 鲍志强, 陈卫东. 基于最大后验估计的谣言源定位器 Rumor Source Detection in Social Networks via Maximum-a-Posteriori Estimation 计算机科学, 2021, 48(4): 243-248. https://doi.org/10.11896/jsjkx.200400053 |
[14] | 张少杰, 鹿旭东, 郭伟, 王世鹏, 何伟. 供需匹配中的非诚信行为预防 Prevention of Dishonest Behavior in Supply-Demand Matching 计算机科学, 2021, 48(4): 303-308. https://doi.org/10.11896/jsjkx.200900090 |
[15] | 袁得嵛, 陈世聪, 高见, 王小娟. 基于斯塔克尔伯格博弈的在线社交网络扭曲信息干预算法 Intervention Algorithm for Distorted Information in Online Social Networks Based on Stackelberg Game 计算机科学, 2021, 48(3): 313-319. https://doi.org/10.11896/jsjkx.200400079 |
|