动态社交网络中非完全信息下谣言溯源问题研究

Rumor source identification under incomplete information in dynamic social network

突发事件发生后,在线社交网络往往成为谣言滋生与传播的重灾区.追溯谣言源头,从源头阻断谣言传播是舆情管控的有效手段.但在实际中在线社交网络是动态变化的,并且谣言传播的历史情况信息很难完全获取,通常只能获取当前时刻下谣言的传播情况,因此本文聚焦于研究动态社交网络中非完全信息下谣言溯源问题.本文根据节点的传播级联在最后一层网络上的感染集合与当前时刻下新增被谣言感染节点集合的期望对称差构造目标函数,并证明了目标函数具有#P-hard的性质,且既不是次模函数也不是超模函数.接下来设计了基于可达集合抽样的方法寻找谣言源头节点,并给出了算法框架和计算复杂度分析.最后在三个真实的动态网络数据集上仿真验证了本文所提出谣言溯源方法RSS相比于已有方法的效果更好,并探究了动态社交网络的拓扑结构变化对本文提出的谣言溯源方法准确性的影响.

After emergencies,online social networks often become the hardest hit areas for rumors to breed and spread.Tracing the source of rumors and blocking the spread of rumors from the source is an effective means of public opinion control.However,in practice,online social networks are dynamic,and it is difficult to fully obtain the historical information of rumor propagation.Usually,we can only obtain the rumor propagation at the current moment.Therefore,this paper focuses on the rumor traceability under incomplete information in dynamic social networks.In this paper,the objective function is constructed according to the expected symmetric difference between the infected set on the last layer of the network and the new infected node set at the current time.It is proved that the objective function has the property of#P-hard and is neither a submodular function nor a supermodular function.Next,a method based on reachable set sampling is designed to find the rumor source node,the algorithm framework and computational complexity analysis are given.Finally,the simulation results on three real dynamic network data sets verify that the rumor tracing method RSS proposed in this paper is better than the existing methods,and explore the impact of the topology change of dynamic social networks on the accuracy of the rumor tracing method proposed in this paper.