Rumor Spreading Maximization and Source Identification in a Social Network

ABSTRACT

The goal of a rumor source node in a social network is to spread its rumor to as many nodes as possible, while remaining hidden from the network administrator. On the other hand, the network administrator aims to identify the source node based on knowledge of which nodes have accepted the rumor (which are called infected nodes). We model the rumor spreading and source identification problem as a strategic game, where the rumor source and the network administrator are the two players. As the Jordan center estimator is a minimax source estimator that has been shown to be robust in recent works, we assume that the network administrator utilizes a source estimation strategy that probes every node within a given radius of the Jordan center. Given any estimation strategy, we design a best-response infection strategy for the rumor source. Given any infection strategy, we design a best-response estimation strategy for the network administrator. We derive conditions under which the Nash equilibria of the strategic game exist. Simulations in both synthetic and real-world networks demonstrate that our proposed infection strategy infects more nodes while maintaining the same safety margin between the true source node and the Jordan center source estimator.

References

1. B. Viswanath, A. Mislove, M. Cha, and K. P. Gummadi, "On the evolution of user interaction in Facebook," in Proc. 2nd ACM Workshop on Online Social Networks, 2009.
2. M. Cha, H. Haddadi, F. Benevenuto, and K. P. Gummadi, "Measuring user influence in Twitter: the million follower fallacy," in Proc. 4th International AAAI Conference on Weblogs and Social Media, 2010.
3. V. Gundotra. (2012, December) Google+: communities and photos. Google Official Blog.
4. Pew Research Center. (2014, September) How social media is reshaping news. {Online}. Available: http://goo.gl/xeIoXi
5. L. Han, S. Han, Q. Deng, J. Yu, and Y. He, "Source tracing and pursuing of network virus," in Proc. 8th IEEE International Conference on Computer and Information Technology Workshops, 2008.
6. J. Weng, E.-P. Lim, J. Jiang, and Q. He, "Twitterrank: finding topic-sensitive influential twitterers," in Proc. 3rd ACM International Conference on Web Search and Data Mining, 2010.
7. E. Bakshy, J. M. Hofman, W. A. Mason, and D. J. Watts, "Everyone's an influencer: quantifying influence on Twitter," in Proc. 4th ACM International Conference on Web Search and Data Mining, 2011.
8. The Huffington Post. (2013, June) Jackie Chan addresses death hoax, proves he's alive with Facebook post. {Online}. Available: http://goo.gl/dO0ZQ9
9. R. K. Garrett, "Troubling consequences of online political rumoring," Human Communication Research, vol. 37, pp. 255--274, 2011.
10. Daily Mail. (2013, April) 'Syrian hackers' break into Associated Press' Twitter account and 'break news' that explosions at White House have injured Obama - sending DOW Jones plunging 100 points. {Online}. Available: http://goo.gl/NSliQP
11. D. Shah and T. Zaman, "Rumors in a network: Who's the culprit?" IEEE Trans. Inf. Theory, vol. 57, no. 8, pp. 5163--5181, 2011.
12. W. Luo, W. P. Tay, and M. Leng, "Identifying infection sources and regions in large networks," IEEE Trans. Signal Process., vol. 61, no. 11, pp. 2850--2865, 2013.
13. W. Dong, W. Zhang, and C. W. Tan, "Rooting out the rumor culprit from suspects," arXiv:1301.6312, 2013. {Online}. Available: http://arxiv.org/abs/1301.6312
14. K. Zhu and L. Ying, "Information source detection in the SIR model: a sample path based approach," in Information Theory and Applications Workshop, 2013.
15. W. Luo, W. P. Tay, and M. Leng, "How to identify an infection source with limited observations," IEEE J. Sel. Top. Sign. Proces., vol. 8, no. 4, pp. 586--597, 2014.
16. W. Luo, W. P. Tay, and M. Leng, "On the universality of Jordan centers for estimating infection sources in tree networks," arXiv:1411.2370, 2014. {Online}. Available: http://arxiv.org/abs/1411.2370
17. Secret. {Online}. Available: https://www.secret.ly/
18. The Wall Street Journal. (2014, Feburary) Evernote denies 'Secret' acquisition rumor. {Online}. Available: http://goo.gl/6GiuAl
19. G. Fanti, P. Kairouz, S. Oh, and P. Viswanath, "Spy vs. spy: rumor source obfuscation," arXiv:1412.8439, 2014. {Online}. Available: http://arxiv.org/abs/1412.8439
20. S. Wasserman, K. Faust, and D. Iacobucci, Social Network Analysis: Methods and Applications (Structural Analysis in the Social Sciences). Cambridge University Press, 1994.
21. M. J. Osborne and A. Rubinstein, A course in game theory. The MIT Press, 1994.
22. W. Luo, W. P. Tay, and M. Leng, "Rumor spreading and source identification: a hide and seek game," IEEE Trans. Signal Process., 2015, submitted. {Online}. Available: http://arxiv.org/abs/1504.04796
23. D. J. Watts and S. H. Strogatz, "Collective dynamics of 'small-world' networks." Nature, vol. 393, no. 6684, pp. 440--442, 1998.
24. J. McAuley and J. Leskovec, "Learning to discover social circles in ego networks," in NIPS, 2012.