Please wait a minute...
Frontiers of Computer Science

ISSN 2095-2228

ISSN 2095-2236(Online)

CN 10-1014/TP

邮发代号 80-970

2019 Impact Factor: 1.275

Frontiers of Computer Science  2016, Vol. 10 Issue (3): 518-531   https://doi.org/10.1007/s11704-015-5008-y
  本期目录
Understanding information interactions in diffusion: an evolutionary game-theoretic perspective
Yuan SU(),Xi ZHANG,Lixin LIU,Shouyou SONG,Binxing FANG
Key Laboratory of Trustworthy Distributed Computing and Service, Ministry of Education, School of Computer Science, Beijing University of Posts and Telecommunications, Beijing 100876, China
 全文: PDF(542 KB)  
Abstract

Social networks are fundamental mediums for diffusion of information and contagions appear at some node of the network and get propagated over the edges. Prior researches mainly focus on each contagion spreading independently, regardless of multiple contagions’ interactions as they propagate at the same time. In the real world, simultaneous news and events usually have to compete for user’s attention to get propagated. In some other cases, they can cooperate with each other and achieve more influences.

In this paper, an evolutionary game theoretic framework is proposed to model the interactions among multiple contagions. The basic idea is that different contagions in social networks are similar to the multiple organisms in a population, and the diffusion process is as organisms interact and then evolve from one state to another. This framework statistically learns the payoffs as contagions interacting with each other and builds the payoff matrix. Since learning payoffs for all pairs of contagions IS almost impossible (quadratic in the number of contagions), a contagion clustering method is proposed in order to decrease the number of parameters to fit, which makes our approach efficient and scalable. To verify the proposed framework, we conduct experiments by using real-world information spreading dataset of Digg. Experimental results show that the proposed game theoretic framework helps to comprehend the information diffusion process better and can predict users’ forwarding behaviors with more accuracy than the previous studies. The analyses of evolution dynamics of contagions and evolutionarily stable strategy reveal whether a contagion can be promoted or suppressed by others in the diffusion process.

Key wordssocial networks    information diffusion    game theory    evolutionary game    evolution dynamics
收稿日期: 2015-01-05      出版日期: 2016-05-16
Corresponding Author(s): Yuan SU   
 引用本文:   
. [J]. Frontiers of Computer Science, 2016, 10(3): 518-531.
Yuan SU,Xi ZHANG,Lixin LIU,Shouyou SONG,Binxing FANG. Understanding information interactions in diffusion: an evolutionary game-theoretic perspective. Front. Comput. Sci., 2016, 10(3): 518-531.
 链接本文:  
https://academic.hep.com.cn/fcs/CN/10.1007/s11704-015-5008-y
https://academic.hep.com.cn/fcs/CN/Y2016/V10/I3/518
1 Pastor-Satorras R, Vespignani A. Epidemic spreading in scale-free networks. Physical Review Letters, 2001, 86(14): 3200–3203
2 Galuba W, Aberer K, Chakraborty D, Despotovic Z, Kellerer W. Outtweeting the twitterers-predicting information cascades in microblogs. In: Proceedings of the 3rd Conference on Online Social Networks. 2010, 3–11
3 Leskovec J, McGlohon M, Faloutsos C, Glance N, Hurst M. Patterns cascading behavior in large blog graphs. In: Proceedings of the 7th SIAM International Conference on Data Mining. 2007, 551–556
4 Yang J, Leskovec J. Modeling information diffusion in implicit networks. In: Proceedings of the 10th International Conference on Data Mining. 2010, 599–608
5 Centola D, Macy M. Complex contagions and the weakness of long ties. American Journal of Sociology, 2007, 113(3): 702–734
6 Cosley D, Huttenlocher D, Kleinberg J M, Lan X, Suri S. Sequential influence models in social networks. In: Proceedings of the 4th International AAAI Conference onWeblogs and SocialMedia. 2010, 26–33
7 Wu S, Hofman J M, Mason W A, Watts D J. Who says what to whom on twitter. In: Proceedings of the 20th International Conference on World Wide Web. 2011, 705–714
8 Kempe D, Kleinberg J, Tardos É. Maximizing the spread of influence through a social network. In: Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2003, 137–146
9 Kempe D, Kleinberg J, Tardos É. Influential nodes in a diffusion model for social networks. Automata, Languages and Programming, 2005, 1127–1138
10 Weng L, Flammini A, Vespignani A, Menczer F. Competition among memes in a world with limited attention. Scientific Reports, 2012, 2
11 Myers S A, Leskovec J. Clash of the contagions: cooperation and competition in information diffusion. In: Proceedings of the 12th International Conference on Data Mining. 2012, 539–548
12 Smith J M, Price G R. The logic of animal conflict. Nature, 1973, 246: 15–18
13 McNamara J M, Gasson C E, Houston A I. Incorporating rules for responding into evolutionary games. Nature, 1999, 401(6751): 368–371
14 May R M, Leonard W J. Nonlinear aspects of competition between three species. SIAM Journal on Applied Mathematics, 1975, 29(2):243–253
15 Doebeli M, Knowlton N. The evolution of interspecific mutualisms. In: Proceedings of the National Academy of Sciences, 1998, 95(15): 8676–8680
16 Axelrod R, Hamilton W D. The evolution of cooperation. Science, 1981, 211(4489): 1390–1396
17 Nowak M A, Sigmund K. Evolution of indirect reciprocity. Nature, 2005, 437(7063): 1291–1298
18 Nowak M A, Komarova N L, Niyogi P. Computational and evolutionary aspects of language. Nature, 2002, 417(6889): 611–617
19 Easley D, Kleinberg J. Networks, crowds, and markets: reasoning about a highly connected world. Cambridge University Press, 2010
20 Weibull J W. Evolutionary game theory. MIT Press, 1997
21 Gomez-Rodriguez M, Leskovec J, Krause A. Inferring networks of diffusion and influence. ACM Transactions on Knowledge Discovery from Data, 2012, 5(4): 21
22 Sadikov E, Medina M, Leskovec J, Garcia-Molina H. Correcting for missing data in information cascades. In: Proceedings of the 4th ACM International Conference on Web Search and Data Mining. 2011, 55–64
23 Zheng X, Zhong Y, Zeng D, Wang F Y. Social influence and spread dynamics in social networks. Frontiers of Computer Science, 2012, 6(5): 611–620
24 Bakshy E, Hofman J M, Mason W A, Watts D J. Everyone’s an influencer: quantifying influence on twitter. In: Proceedings of the 4th ACMInternational Conference onWeb Search and DataMining. 2011, 65–74
25 Sneppen K, Trusina A, Jensen M H, Bornholdt S. A minimal model for multiple epidemics and immunity spreading. PloS One, 2010, 5(10): e13326
26 Kuhlman C J, Kumar V S A, Marathe M V, Swarup S, Tuli G, Ravi S S, Rosenkrantz D J. Inhibiting the diffusion of contagions in bi-threshold systems: analytical and experimental results. AAAI Fall Symposium: Complex Adaptive Systems, 2011
27 Wang F, Wang H Y, Xu K. Diffusive logistic model towards predicting information diffusion in online social networks. In: Proceedings of the 32nd International Conference on Distributed Computing Systems Workshops. 2012, 133–139
28 Granovetter M. Threshold models of collective behavior. American Journal of Sociology, 1978: 1420–1443
29 Schelling T. Micromotives and macromotives. Norton, 1978
30 Goldenberg J, Libai B, Muller E. Talk of the network: a complex systems look at the underlying process of word-of-mouth. Marketing Letters, 2001, 12(3): 211–223
31 Hethcote H W. The mathematics of infectious diseases. SIAM Review, 2000, 42(4): 599–653
32 Newman M E. The structure and function of complex networks. SIAM Review, 2003, 45(2): 167–256
33 Pathak N, Banerjee A, Srivastava J. A generalized linear threshold model for multiple cascades. In: Proceedings of the 10th International Conference on Data Mining. 2010, 965–970
34 Prakash B, Beutel A, Rosenfeld R, Faloutsos C. Winner takes all: competing viruses or ideas on fair-play networks. In: Proceedings of the 21st International Conference on World Wide Web. 2012, 1037–1046
35 Karrer B, NewmanME J. Competing epidemics on complex networks. Physical Review E, 2011, 84(3): 036106
36 Bharathi S, Kempe D, Salek M. Competitive influence maximization in social networks. Internet and Network Economics, 2007: 306–311
37 Budak C, Agrawal D, EL Abbadi A. Limiting the spread of misinformation in social networks. In: Proceedings of the 20th International Conference on World Wide Web. 2011, 665–674
38 Narayanam R, Narahari Y. A shapley value-based approach to discover influential nodes in social networks. IEEE Transactions on Automation Science and Engineering, 2010, 99: 1–18
39 Chen W, Liu Z M, Sun X R, Wang Y J. A game-theoretic framework to identify overlapping communities in social networks. Data Mining and Knowledge Discovery, 2010, 21(2): 224–240
40 Jiang C X, Chen Y, Liu K J R. Evolutionary information diffusion over social networks. 2013, arXiv preprint arXiv:1309.2920
41 Ferrara E, JafariAsbagh M, Varol O, Qazvinian V, Menczer F, Flammini A. Clustering memes in social media. In: Proceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. 2013, 548–555
42 Hogg T, Lerman K. Social dynamics of digg. EPJ Data Science, 2012, 1(1): 1–26
43 Lerman K, Ghosh R. Information contagion: an empirical study of the spread of news on digg and twitter social networks. ICWSM, 2010, 10: 90–97
44 Davis J, Goadrich M. The relationship between precision-recall and roc curves. In: Proceedings of the 23rd International Conference on Machine Learning. 2006, 233–240
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed