在线社交网络中的多主题谣言溯源

Tracing to Source of Multi-topic Rumors in Online Social Networks

随着通信技术的快速发展,用户之间的信息可以很快地流通,同时也导致谣言在社交网络中传播,因此亟需对谣言来源进行检测以确保社交网络的公信力。目前关于谣言溯源的研究方向基本注重于单主题谣言传播,然而社交网络中存在大量不同主题的谣言,谣言源头以及谣言主题数量越多,产生的不良影响越大。针对多主题谣言同时存在的情况,信息的传播过程需要被重新定义。因此,该文提出了一种多主题独立级联模型,并在该模型的基础上定义了谣言溯源问题。从已感染的网络子图中,基于影响力最大化的原则找出前k个可疑节点,这组节点被认为是最可能的谣言来源。并证明了该问题是NP难的,以及目标函数是单调且子模的。在此基础上,提出了一种基于影响力最大化的近似比为(1-1/e)的贪婪算法。在大型真实数据集上的实验表明,平均误差距离控制在1跳之内。而且与其他算法相比,该算法具有更高的准确性以及有效性。

With the rapid development of communication technology,information between users can flow quickly,which also leads to the spread of rumors in social networks,so there is an urgent need to detect the source of rumors to ensure the credibility of social networks.At present,the research on rumor traceability basically focuses on the spread of single-topic rumors.However,there are a large number of rumors with different topics in social networks.The more the source of rumors and the number of rumor topics,the greater the adverse effects.In view of the fact that multi-topic rumors exist at the same time,the process of information dissemination needs to be redefined.Therefore,a multi-topic independent cascade model is proposed,and the rumor traceability problem is defined on the basis of this model.From the infected network subgraph,the first k suspicious nodes are identified based on the principle of maximizing influence,and this group of nodes is considered to be the most likely source of rumors.It is proved that the problem is NP-hard and the objective function is monotone and submodular.On this basis,a greedy algorithm based on influence maximization with approximate ratio(1-1/e)is proposed.Experiments on large real data sets show that the average error distance is controlled within 1 hop.And compared with other algorithms,the proposed algorithm has higher accuracy and effectiveness.