Rumor Source Identification in Social Networks with Time-Varying Topology

© 2004-2012 IEEE. Identifying rumor sources in social networks plays a critical role in limiting the damage caused by them through the timely quarantine of the sources. However, the temporal variation in the topology of social networks and the ongoing dynamic processes challenge our traditional source identification techniques that are considered in static networks. In this paper, we borrow an idea from criminology and propose a novel method to overcome the challenges. First, we reduce the time-varying networks to a series of static networks by introducing a time-integrating window. Second, instead of inspecting every individual in traditional techniques, we adopt a reverse dissemination strategy to specify a set of suspects of the real rumor source. This process addresses the scalability issue of source identification problems, and therefore dramatically promotes the efficiency of rumor source identification. Third, to determine the real source from the suspects, we employ a novel microscopic rumor spreading model to calculate the maximum likelihood (ML) for each suspect. The one who can provide the largest ML estimate is considered as the real source. The evaluations are carried out on real social networks with time-varying topology. The experiment results show that our method can reduce 60 - 90 percent of the source seeking area in various time-varying social networks. The results further indicate that our method can accurately identify the real source, or an individual who is very close to the real source. To the best of our knowledge, the proposed method is the first that can be used to identify rumor sources in time-varying social networks