独立级联模型下基于双区分集的观察节点选择方法  

Method for Selecting Observers Based on Doubly Resolving Set in Independent Cascade Model

作　　者：陈张缘 陈崚[1] 刘维[1] 李斌[1] CHEN Zhangyuan;CHEN Ling;LIU Wei;LI Bin(College of Information Engineering,Yangzhou University,Yangzhou,Jiangsu 225000,China)

机构地区：[1]扬州大学信息工程学院,江苏扬州225000

出　　处：《计算机科学》2025年第4期280-290,共11页Computer Science

基　　金：国家自然科学基金(61379066,61702441,61379064,61472344,61402395,61602202);江苏省自然科学基金(BK20140492,BK20160428);江苏省教育厅自然科学基金(12KJB520019,13KJB520026,09KJB20013);江苏省六大人才高峰(2011-DZXX-032)。

摘　　要：随着互联网的发展,谣言信息可以在社交网络上快速传播,找到谣言源头有助于阻止负影响的传播,因此谣言源定位问题有着重要的研究价值。目前,最有效的源定位方法是基于观察节点的方法,但是现有选择观察节点的方法都没有考虑图的顶点分布的均匀性,并且都是预先设置观察节点的数量而没有根据图的拓扑特性来合理确定观察节点的个数。文中从节点预算阈值和节点的覆盖率阈值两个角度研究观察节点的放置策略,考虑了观察节点激活状态以及到源集合的区分距离,并提出了一种新的K-双区分算法。该算法首先根据双区分集概念选择初始观察节点,然后选择其中一个锚点根据提出的覆盖率和预算约束问题贪心地选择观察节点来达到预算和覆盖率阈值。在真实数据集上对所提算法进行了实验,在同一种源定位算法中对比多种选择观察节点的算法。实验结果表明,所提算法的源定位结果精确度和平均距离误差均优于对比算法,在大型数据集中只使用5%~10%的观察节点就可以达到很好的定位效果。With the development of the Internet,rumor information may quickly spread on social networks.Finding the source of rumor can effectively help stop the spread of negative influences,so the source localization problem has great research value.At present,the most effective source localization method is based on observation nodes.But the existing selection of observation nodes has not considered the uniformity of node distribution in the network,and the number of observation nodes is pre-set without reasonably considering the topological characteristics of the graph.This paper studies the strategy of observer nodes placement from two perspectives:node budget threshold and node coverage threshold.Taking into account the activation status of observer nodes and the discriminative distance to the source set,a novel K-differentiation algorithm is proposed,which initially selects the initial observer nodes based on the concept of the doubly-resolving set.Subsequently,an anchor node is chosen to greedily select observer nodes based on a combination of coverage and budget differences to reach the specified thresholds for coverage and budget.The algorithm then addresses two problems related to budget and coverage proposed in this paper when choosing observer nodes for experimentation within the same source localization algorithm.Experiments are conducted in real world social datasets.The proposed algorithm for selecting observer nodes is compared with various alternatives within the same source localization algorithm.The results indicate that the accuracy of source localization and average error distance by our algorithm outperforms other algorithms and achieve excellent results in the large dataset with 5%~10%observer nodes.

关 键 词：观察节点 社交网络 独立级联模型 双区分集 源定位 

分 类 号：TP399[自动化与计算机技术—计算机应用技术]