基于有责量和免责量的谣言溯源算法

Identifying Rumor Source Based on Exoneration and Prominence

复杂网络中的谣言溯源问题一直是学者们的研究重点,随着互联网技术和社交网络的发展,如何快速准确地确定网络中的谣言源以削减其不良影响显得尤为重要。考虑到谣言源是网络中最早感染的节点,即拥有最大的节点年龄,通过对节点的未受感染邻居所表现出的免责量进行研究,综合免责量与节点年龄之间的关系,提出基于有责量和免责量的谣言溯源算法,同时为了减少计算成本,选取高介数中心性节点作为可疑集。结合现实网络中谣言发展的真实情形,将算法推广至网络中双源情况,基于优化的谱分析方法将感染网络划分为两个社区,将复杂双源问题转化为单源问题。在几个合成与真实网络中进行的仿真实验结果表明,在单源和双源的情况下,提出的溯源算法能够快速有效地识别到谣言源,在多个网络中溯源结果的平均误差距离小于1跳,相较于其他启发式算法具有一定的优越性,同时,在高度稀疏性的网络中,性能表现良好。

The problem of identifying the source of rumors in complex networks has always been the research focus of scholars.At the same time,with the development of Internet technology and social networks,how to quickly and accurately identify the source of rumors in the network to reduce its adverse effects is particularly important.Considering that the source of the rumors is the earliest infected node in the network,that is,it has the oldest age.By studying the exoneration shown by the uninfected neighbors of the node,comprehensively the relationship between the exoneration and the age of the node,we propose a source traceability algorithm based on exoneration and prominence.At the same time,in order to reduce the computational cost,high betweenness centrality nodes are selected as suspicious sets.Combined with the real situation of the development of rumors in the real network,the algorithm is extended to the dual-source situation in the network.On the basis of community division,the infection map is divided into two communities based on the optimized spectrum analysis method,and the complex dual source problem is transformed into a single source problem.Simulation and comparison experiments in several synthetic networks and real networks show that the proposed algorithm can quickly and effectively identify the source of rumors in the case of single source and dual source,and the average error distance of the traceability results in multiple network topologies is less than 1 hop,which has certain advantages compared with other heuristic algorithms.Meanwhile,in highly sparse network,the performance is good.