Rumor Source Detection in Networks Based on the SEIR Model

Abstract

Online social networks have become extremely important in daily life and can be used to influence lives in dramatic ways. Two issues are the veracity and provenance of posted information, including rumors. There is a need for methods for tracing rumors (or any piece of information) to their most likely source in such networks. We consider the detection problem of single rumor source based on observed snapshots based on the susceptible-exposed-infected-recovered (SEIR) model. According to the SEIR model, all nodes in the network are formulated into four possible states: susceptible (S), exposed (E), infected (I), and recovered (R). Given an observed snapshot in the network, from which we can know the relevant graph topology and all infected nodes, but where nodes in susceptible, exposed, or recovered status cannot be distinguished, the purpose of our research is to identify the rumor source based on the observed snapshot and graph topology. We propose the concept of the optimal infection process and derive an estimator for the rumor source based on this optimal infection process. Subsequently, we prove that this estimator matches the rumor source with a high probability. The effectiveness of the proposed scheme is validated using experiments based on regular tree networks with different degrees. We further evaluate the performance of our scheme on two well-known synthetic complex networks and four real-world networks; the results suggest that our proposed scheme outperforms the traditional rumor centrality heuristics. The performance analysis on computational complexity demonstrates that our scheme has advantages in efficiency compared with other rumor centrality heuristics used in rumor detection methods.

Keywords

• Rumor source detection
• optimal infection process
• susceptible-exposed-infected-recovered (SEIR) model
• information security