Finding Rumor Source in large Social Network

We address the problem of estimating the source of a rumor in large-scale social networks.Previous works studying this problem have mainly focused on graph models with deterministic and homogenous internode relationship strengths.However, internode relationship strengths in real social networks are random.We model this uncertainty by using random, non-homogenous edge weights on the underlying social network graph.We propose a novel two-stage algorithm that uses the modularity of the social network to locate the source of the rumor with fewer sensor nodes than other existing algorithms.Real-world time series data are used to model the uncertainty in social relationship strengths.Simulations show that the proposed algorithm can determine the actual source within two hops, 69%-80% of the time, when the diameter of the networks varies between 7 and 13.Our numerical results also show that it is easier to estimate the source of a rumor when the source has higher betweenness centrality.Finally, we demonstrate that our twostage algorithm outperforms the alternative algorithm in terms of the accuracy of localizing the source.