计算机科学 ›› 2022, Vol. 49 ›› Issue (2): 204-215.doi: 10.11896/jsjkx.201100190
邵玉, 陈崚, 刘维
SHAO Yu, CHEN Ling, LIU Wei
摘要： 如今,网络谣言、传染病、计算机病毒等负面影响力的传播,给社会稳定、人类健康和信息安全造成了巨大的隐患,识别它们的传播源,对于控制负面影响力造成的危害有着重要的意义。目前大多数方法都只致力于单个传播源的定位问题,而在实际网络中,负影响力往往来自多个传播源,而且需要进行传播过程的模拟;此外,由于忽略了顶点之间拓扑限制的差异,导致定位传播源的准确率不高而且需要大量的计算时间。针对这些问题,提出了一种基于极大似然的方法,利用少量观测点提供的信息来有效定位多个传播源。首先,提出了传播图的概念以及产生传播图的方法,根据节点的入度和边的权重将其划分成若干层级,并去除传播概率较小的边,形成包含观测节点的传播图;然后,利用似然法计算传播图中的每一层顶点的激活概率,选取相对于观测点的似然最大的k个顶点构成源节点集合;最后,对所提方法进行了模拟实验,实验结果表明,该方法能够准确识别网络中的多个传播源,源定位结果的精确度高于其他类似算法;同时,也通过实验验证了观测点的选择和网络结构在不同程度上会影响传播源的定位结果。
中图分类号:
| [1]YANG F,YANG S,PENG Y,et al.Locating the propagation source in complex networks with a direction-induced search based Gaussian estimator[J].Knowledge-Based Systems,2020,195:105674. [2]WANG H J,ZHANG F F,SUN K J.An algorithm for locating propagation source in complex networks[J].Physics Letters A,2021,393:127184. [3]PALUCH R,LU X,SUCHECKI K,et al.Fast and accurate detection of spread source in large complex networks[J].Scientific Reports,2018,8(1):2508. [4]PINTO P C,THIRAN P,VETTERLI M.Locating the source of diffusion in large-scale networks[J].Phys. Rev. Lett.,2012,109(6):68702. [5]ZANG W,ZHANG P,ZHOU C,et al.Discovering Multiple Diffusion Source Nodes in Social Networks[J].Procedia Computerscience,2014,29:443-452. [6]HU Z,SHEN Z,CAO S,et al.Locating multiple diffusionsources in time varying networks from sparse observations[J].Scientific Reports,2018,8(1):2685. [7]JIANG J,WEN S,YU S,et al.Rumor Source Identification in Social Networks with Time-Varying Topology[J].IEEE Tran-sactions on Dependable and Secure Computing,2018,15(1):166-179. [8]HUANG Q,ZHAO C,ZHANG X,et al.Locating the source of spreading in temporal networks[J].Physica A:Statistical Mechanics and its Applications,2017,468:434-444. [9]DONG M,ZHENG B,HUNG N Q V,et al.Multiple rumor source detection with graphconvolutional networks[C]//Proceedings of the 28th ACM International Conference on Information and Knowledge Management.2019:569-578. [10]WANG H.An universal algorithm for source location in complex networks[J].Physica A:Statistical Mechanics and its Applications,2019,514:620-630. [11]YANG X,ZHU Z,YU H,et al.A Naming Game-Based Method for the Location of Information Source in Social Networks[J].Complexity,2020,2020:1-8. [12]ZANG W,ZHANG P,ZHOU C,et al.Locating multiple sources in social networks under the SIR model:A divide-and-conquer approach[J].Journal of Computational Science,2015,10:278-287. [13]DING Y,CUI X,WANG H,et al.PRIA:a Multi-source Recognition Method Based on Partial Observation in SIR Model[J].Mobile Networks and Applications,2020,25(1):271-280. [14]ZHANG Z,YUE K,SUN Z,et al.Locating Sources in OnlineSocial Networks via Random Walk[C]//2017 IEEE Internatio-nal Congress on Big Data (Big Data Congress).IEEE,2017:337-343. [15]LI X,LIU Y,ZHAO C,et al.Locating Multiple Sources of Contagion in Complex Networks under the SIR Model[J].Applied Sciences,2019,9(20):4472. [16]LI X,WANG X,ZHAO C,et al.Optimal Identification of Multiple Diffusion Sources in Complex Networks with Partial Observations[C]//The International Conference on Natural Computation,Fuzzy Systems and Knowledge Discovery.2019:214-223. [17]ALI S S,ANWAR T,RIZVI S A M.A Revisit to the Infection Source Identification Problem under Classical Graph Centrality Measures[J].Online Social Networks and Media,2020,17(1):100061. [18]SHAH D,ZAMAN T.Rumors in a Network:Who's the Culprit?[J].IEEE Transactions on Information Theory,2011,57(8):5163-5181. [19]SEJEONG K,MEEYOUNG C,KYOMIN J.Rumor Detectionover Varying Time Windows[J].PloS one,2017,12(1):e0168344. [20]FANG M,SHI P,SHANG W,et al.Locating the Source ofAsynchronous Diffusion Process in Online Social Networks[J].IEEE Access,2018,6:17699-17710. [21]LI X,WANG X,ZHAO C,et al.Locating the Epidemic Source in Complex Networks with Sparse Observers[J].Applied Sciences,2019,9(18):3644. [22]LI X,WANG X,ZHAO C,et al.Locating the Source of Diffusion in Complex Networks via Gaussian-Based Localization and Deduction[J].Applied Sciences,2019,9(18):3758. [23]LEE C,SUNG C,MA H,et al.IDR:Positive Influence Maximization and Negative Influence Minimization Under Competitive Linear Threshold Model[C]//2019 20th IEEE International Conference on Mobile Data Management (MDM).IEEE,2019:501-506. [24]LI Y,FAN J,WANG Y,et al.Influence Maximization on Social Graphs:A Survey[J].IEEE Transactions on Knowledge and Data Engineering,2018,30(10):1852-1872. [25]TANG Y,SHI Y,XIAO X.Influence Maximization in Near-Li-near Time:A Martingale Approach[C]//Proceedings of the 2015 ACM SIGMOD Internatio-nal Conference on Management of Data.2015:1539-1554. [26]ZHOU J,FAN J,WANG J,et al.Cost-Efficient Influence Maximization in Online Social Networks[C]//2017 Fifth Internatio- nal Conference on Advanced Cloud and Big Data (CBD).IEEE,2017:232-237. [27]WANG F,SHE J,OHYAMA Y,et al.Maximizing positive influence in competitive social networks:A trust-based solution[J].Information Sciences,2021,546:559-572. [28]LI L,LIU Y,ZHOU Q,et al.Targeted influence maximizationunder a multifactor-based information propagation model[J].Information Sciences,2020,519:124-140. [29]TRIVEDI N,SINGH A.Efficient Influence Maximization in Social-Networks Under Independent Cascade Model[J].Procedia Computer Science,2020,173:315-324. [30]LV J,YANG B,YANG Z,et al.A community-based algorithm for influence blocking maximization in social networks[J].Cluster Computing,2019,22(3):5587-5602. [31]DING J,SUN W,WU J,et al.Influence maximization based on the realistic independent cascade model[J].Knowledge-Based System,2020,191:105265. [32]FU L,SHEN Z,WANG W X,et al.Multi-source localization on complex networks with limited observers[J].EPL (Europhysics Letters),2016,113(1):18006. [33]WOO J,CHOI J.Estimating the Information Source under Deca-ying Diffusion Rates[J].Electronics,2019,8(12):1384. [34]KONG F,LI Q Z,LI S.Survey on Online Influence Maximization[J].Computer Science,2020,47(5):7-13. [35]MA Y Y,HAN H,QU Q Q.Importance Evaluation Algorithm Based on Node Intimate Degree[J].Computer Science,2021,48(5):140-146. [36]DEVARAPALLI R K,BISWAS A.Rumor Detection and Tra-cing its Source to Prevent Cyber-Crimes on Social Media[C]//Intelligent Data Analytics for Terror Threat Prediction:Architectures,Methodologies,Techniques and Applications.2021:1-30. [37]LI W M,LI Z,LUVEMBE A M,et al.Influence maximization algorithm based on Gaussian propagation model[J].Information Sciences,2021,568:386-402. |
| [1] | 杨卓璇, 马源培, 严冠. 基于耦合强度的多项式时间社团探测算法 Polynomial Time Community Detection Algorithm Based on Coupling Strength 计算机科学, 2020, 47(6A): 102-107. https://doi.org/10.11896/JsJkx.190900170 |
| [2] | 孔芳, 李奇之, 李帅. 在线影响力最大化研究综述 Survey on Online Influence Maximization 计算机科学, 2020, 47(5): 7-13. https://doi.org/10.11896/jsjkx.200200071 |
| [3] | 富坤, 仇倩, 赵晓梦, 高金辉. 基于节点演化分阶段优化的事件检测方法 Event Detection Method Based on Node Evolution Staged Optimization 计算机科学, 2020, 47(5): 96-102. https://doi.org/10.11896/jsjkx.190400072 |
| [4] | 李豪,崔新凯,高向川. 大规模MIMO室外无线光通信系统中基于分段高斯近似的最大似然盲检测算法 Maximum Likelihood Blind Detection Algorithm Based on Piecewise Gaussian Approximation for Massive MIMO Outdoor Wireless Optical Communication Systems 计算机科学, 2020, 47(3): 255-260. https://doi.org/10.11896/jsjkx.190200310 |
| [5] | 韩忠明, 郑晨烨, 段大高, 董健. 基于多信息融合表示学习的关联用户挖掘算法 Associated Users Mining Algorithm Based on Multi-information Fusion Representation Learning 计算机科学, 2019, 46(4): 77-82. https://doi.org/10.11896/j.issn.1002-137X.2019.04.012 |
| [6] | 徐方, 邓敏, 熊曾刚, 叶从欢, 徐宁. 移动社会网络中基于多维上下文匹配的数据转发算法 Data Forwarding Algorithm Based on Multidimensional Context Matching in Mobile Social Networks 计算机科学, 2019, 46(2): 81-87. https://doi.org/10.11896/j.issn.1002-137X.2019.02.013 |
| [7] | 金婷, 谭文安, 孙勇, 赵尧. 模糊多目标进化的社会团队形成方法 Social Team Formation Method Based on Fuzzy Multi-objective Evolution 计算机科学, 2019, 46(2): 315-320. https://doi.org/10.11896/j.issn.1002-137X.2019.02.048 |
| [8] | 胡庆成, 张勇, 邢春晓. 基于有重叠社区划分的社会网络影响最大化方法研究 K-clique Heuristic Algorithm for Influence Maximization in Social Network 计算机科学, 2018, 45(6): 32-35. https://doi.org/10.11896/j.issn.1002-137X.2018.06.005 |
| [9] | 张昱, 高克宁, 于戈. 一种融合节点属性信息的社会网络链接预测方法 Method of Link Prediction in Social Networks Using Node Attribute Information 计算机科学, 2018, 45(6): 41-45. https://doi.org/10.11896/j.issn.1002-137X.2018.06.007 |
| [10] | 张林姿, 贾传亮. 基于拓扑路径的网络演化传播机制研究 Study of Propagation Mechanism in Networks Based on Topological Path 计算机科学, 2018, 45(11A): 308-314. |
| [11] | 珠杰,洪军建. 基于SDAs的人物关系抽取方法研究 Research on Method of Personal Relation Extraction under SDAs 计算机科学, 2017, 44(Z6): 141-145. https://doi.org/10.11896/j.issn.1002-137X.2017.6A.033 |
| [12] | 刘林峰,严禹道,吴国新. 一种基于节点移动倾向检测的社会网络机会转发机制 Opportunistic Forwarding Mechanism Based on Node Movement Tendencies Detecting 计算机科学, 2017, 44(7): 74-78. https://doi.org/10.11896/j.issn.1002-137X.2017.07.013 |
| [13] | 王珍,韩忠明,李晋. 大规模数据下的社交网络结构洞节点发现算法研究 Research on Social Network Structural Holes Discovery Algorithm under Large-scale Data 计算机科学, 2017, 44(4): 188-192. https://doi.org/10.11896/j.issn.1002-137X.2017.04.041 |
| [14] | 张晓琳,张臣,张文超,张换香,于芳名. D-VSSP:分布式社会网络隐私保护算法 D-VSSP:Distributed Social Network Privacy Preserving Algorithm 计算机科学, 2017, 44(2): 93-97. https://doi.org/10.11896/j.issn.1002-137X.2017.02.012 |
| [15] | 吕文渊,周丽华,廖仁建. 一种面向主题耦合的影响力最大化算法 Coupled Topic-oriented Influence Maximization Algorithm 计算机科学, 2017, 44(12): 28-32. https://doi.org/10.11896/j.issn.1002-137X.2017.12.005 |
|
||
首页