计算机科学 ›› 2025, Vol. 52 ›› Issue (4): 280-290.doi: 10.11896/jsjkx.240300127
陈张缘, 陈崚, 刘维, 李斌
CHEN Zhangyuan, CHEN Ling, LIU Wei, LI Bin
摘要： 随着互联网的发展,谣言信息可以在社交网络上快速传播,找到谣言源头有助于阻止负影响的传播,因此谣言源定位问题有着重要的研究价值。目前,最有效的源定位方法是基于观察节点的方法,但是现有选择观察节点的方法都没有考虑图的顶点分布的均匀性,并且都是预先设置观察节点的数量而没有根据图的拓扑特性来合理确定观察节点的个数。文中从节点预算阈值和节点的覆盖率阈值两个角度研究观察节点的放置策略,考虑了观察节点激活状态以及到源集合的区分距离,并提出了一种新的K-双区分算法。该算法首先根据双区分集概念选择初始观察节点,然后选择其中一个锚点根据提出的覆盖率和预算约束问题贪心地选择观察节点来达到预算和覆盖率阈值。在真实数据集上对所提算法进行了实验,在同一种源定位算法中对比多种选择观察节点的算法。实验结果表明,所提算法的源定位结果精确度和平均距离误差均优于对比算法,在大型数据集中只使用5%~10%的观察节点就可以达到很好的定位效果。
中图分类号:
| [1]KHULLER S,RAGHAVACHARI B,ROSFIELD A.Land-marks in grapghs[J].Discrete Applied Mathematics,1996,70(3):217-229. [2]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. [3]REN J,LIU M,LIU Y,et al.Optimal resource allocation with spatiotemporal transmission discovery for effective disease control[J].Infectious diseases of poverty,2022,11(1):34. [4]LIU P,LI L,FANG S,et al.Identifying influential nodes in social networks:A voting approach[J].Chaos,Solitons & Fractals,2021,152:111309. [5]SHAH D,ZAMAN T.Rumors in a Network:Who’s the Culprit?[J].IEEE Transactions on Information Theory,2011,57(8):5163-5181. [6]PINTO P C,THIRAN P,VETTERLI M.Locating the source of diffusion in large scale networks[J].Physical Review Letters,2012,109(6):68702. [7]LI X,WANG X,HAO C,et a1.Locating the Epidemic Source in complex Networks with sparse Observers [J].Applied Sciences,2019,9(18):3644. [8]SPINELLI B,CELIS L E,THIRAN P.A General Frameworkfor Sensor Placement in Source Localization[J].IEEE Transactions on Network Science and Engineering,2019,6(2):86-102. [9]CELIS L E,PAVETIC' F,SPINELLI B,et al.Budgeted sensor placement for source localization on trees[J].Electronic Notes in Discrete Mathematics,2015,50:65-70. [10]LOKHOV A,MÉZARD M,OHTA H,et al.Inferring the origin of an epidemic with a dynamic message-passing algorithm[J].Physical Review E,2014,90(1):012801. [11]WANG Z X,SUN C,RUI X,et al.Localization of multiple diffusion sources based on overlapping community detection[J].Knowledge-Based Systems,2021,226:106613. [12]LIU Y,LI W,YANG C,et al.Multi-source detection based on neighborhood entropy in social networks[J].Scientific Reports,2022,12(1):1-12. [13]ZHANG Z,YUE K,SUN Z,et al.Locating Sources in Onlinesocial Networks via Random walk[C]//2017 IEEE Interna-tional Congress on Big Data(Big Data Congress).IEEE,2017:337-343. [14]BAO Z Q,CHEN W D.Rumor Source Detection in Social Networks via Maximum-a-Posteriori Estimation[J].Computer Science,2021,48(4):243-248. [15]YUAN D Y,GAO J,YE M X,et al.Malicious InformationSource Locating Algorithm Based on Topological Extension in Online Social NEtwork[J].Computer Science,2019,46(5):129-134. [16]LI W,GUO C,LIU Y,et al.Rumor source localization in social networks based on infection potential energy[J].Information Science,2023,634,172-188. [17]ZHANG X Z,ZHANG Y B,LV T Y,et al.Identification of efficient observers for locating spreading source in complex networks[J].Physic A,2015,442:100-109. [18]PALUCH R,LU X,SUCHECKI K,et a1.Fast andaccurate detection of spread source in large complex networks[J].Scientific Reports,2018,8(1):2508. [19]PALUCH R,GAJEWSKI L,HOLYST G,et al.Optimizing sensors placement in complex networks for localization of hidden signal source:A review[J].Future Generation Compute Systems,2020,112:1070-1092. [20]SPINELLI B,CELIS L E,THIRAN P.Observer placement for source localization:The effect of budgets and transmission variance[C]//54th Annual Allerton Conference on Communication,Control,and Computing,Allerton 2016.IEEE,2016:743-751. [21]ZEJNILOVIC S,GOMES J,SINOPOLI B.Sequential observer selection for source localization[C]//2015 IEEE Global Confe-rence on Signal and Information Processing(GlobalSIP).IEEE,2015:1220-1224. [22]ZEJNILOVIC S,XAVIER J,GOMES J,et al.Selecting observers for source localization via error exponents[C]//2015 IEEE International Symposium on Information Theory(ISIT),IEEE,2015:2914-2918. [23]ZEJNILOVIC,GOMES J,SINOPOLI B.Network observability and localization of the source of diffusion based on a subset of nodes[C]//51st Annual Allerton Conference on Communication,Control,and Computing(Allerton).IEEE,2013:847-852. [24]GAJEWSKI L,PALUCH R,SUCHECKI K,et al.Comparison of observer based methods for source localization in complex networks[J].Scientific Reports,2022,12:5079-5079. [25]CHEN X,HU X,WAN C.Approximation for the minimum cost doubly resolving set problem[J].Theoretical Computer Science,2016,609:526-543. [26]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. [27]ZHAO J,HAO K,CHEONG H.Early identification of diffusion source in complex networks with evidence theory[J].Information Science,2023,642:119061. [28]BERRY J,HART,W,PHILLIPS C,et al.Sensor placement in municipal water networks with temporal integer programming models[J].Journal of Water Resources Planning and Manage- ment,2006,132(4):218. |
|
||
首页