Rumor Initiator Detection in Infected Signed Networks
Jiawei Zhang, Charu C. Aggarwal and Philip S. Yu
University of Illinois at Chicago, IBM T. J. Watson Research Center, University of Illinois at Chicago

In many cases, the information spread in an online network may not always be truthful or correct; such information corresponds to rumors. In recent years, signed networks have become increasingly popular because of their ability to represent diverse relationships such as friends, enemies, trust, and distrust. Signed networks are ideal for information flow in a network with varying beliefs (trust or distrust) about facts. In this paper, we will study the problem of influence analysis and diffusion models in signed networks and investigate the problem of rumor initiator detection, given the state of the network at a given moment in time. Conventional information diffusion models for unsigned networks cannot be applied to signed networks directly, and we show that the rumor initiator detection problem is NP-hard. We propose a new information diffusion model, referred to as asyMmetric Flipping Cascade (MFC), to model the propagation of information in signed networks. Based on MFC, a novel framework, Rumor Initiator Detector (RID), is introduced to determine the potential number and the identity of the rumor initiators from the state of the network at a given time. Extensive experiments conducted on real-world signed networks demonstrate that MFC works very well in modeling information diffusion in signed networks and RID can significantly outperform other comparison methods in identifying rumor initiators.