Demarcating Endogenous and Exogenous Opinion Diffusion Process on Social Networks

ABSTRACT

The networked opinion diffusion in online social networks (OSN) is governed by the two genres of opinions-endogenous opinions that are driven by the influence of social contacts between users, and exogenous opinions which are formed by external effects like news, feeds etc. Such duplex opinion dynamics is led by users belonging to two categories- organic users who generally post endogenous opinions and extrinsic users who are susceptible to externalities, and mostly post the exogenous messages. Precise demarcation of endogenous and exogenous messages offers an important cue to opinion modeling, thereby enhancing its predictive performance. On the other hand, accurate user selection aids to detect extrinsic users, which in turn helps in opinion shaping. In this paper, we design CherryPick, a novel learning machinery that classifies the opinions and users by solving a joint inference task in message and user set, from a temporal stream of sentiment messages. Furthermore, we validate the efficacy of our proposal from both modeling and shaping perspectives. Moreover, for the latter, we formulate the opinion shaping problem in a novel framework of stochastic optimal control, in which the selected extrinsic users optimally post exogenous messages so as to guide the opinions of others in a desired way. On five datasets crawled from Twitter, CherryPick offers a significant accuracy boost in terms of opinion forecasting, against several competitors. Furthermore, it can precisely determine the quality of a set of control users, which together with the proposed online shaping strategy, consistently steers the opinion dynamics more effectively than several state-of-the-art baselines.

References

1. P. Clifford and A. Sudbury. A model for spatial conflict. Biometrika, 60(3):581--588, 1973.
2. M. H. DeGroot. Reaching a consensus. Journal of the American Statistical Association, 69(345):118--121, 1974.
3. M. E. Yildiz, R. Pagliari, A. Ozdaglar, and A. Scaglione. Voting models in random networks. In Information Theory and Applications Workshop, pages 1--7, 2010.
4. A. Das, S. Gollapudi, and K. Munagala. Modeling opinion dynamics in social networks. In WSDM, 2014.
5. A. De, S. Bhattacharya, P. Bhattacharya, N. Ganguly, and S. Chakrabarti. Learning a linear influence model from transient opinion dynamics. In CIKM, 2014.
6. Abir De, Isabel Valera, Niloy Ganguly, Sourangshu Bhattacharya, and Manuel Gomez Rodriguez. Learning and forecasting opinion dynamics in social networks. In NIPS. 2016.
7. Jan Christian Dittmer. Consensus formation under bounded confidence. Nonlinear Analysis: Theory, Methods & Applications, 47(7):4615--4621, 2001.
8. Igor Douven and Alexander Riegler. Extending the hegselmann--krause model i. Logic Journal of IGPL, 18(2):323--335, 2009.
9. Claudio Altafini and Gabriele Lini. Predictable dynamics of opinion forming for networks with antagonistic interactions. IEEE Transactions on Automatic Control, 60(2):342--357, 2015.
10. Irinel-Constantin Mor, Antoine Girard, et al. Opinion dynamics with decaying confidence: Application to community detection in graphs. IEEE Transactions on Automatic Control, 56(8):1862--1873, 2011.
11. Seyed Rasoul Etesami and Tamer Bacsar. Game-theoretic analysis of the hegselmann-krause model for opinion dynamics in finite dimensions. IEEE Transactions on Automatic Control, 60(7):1886--1897, 2015.
12. Vincent D Blondel, Julien M Hendrickx, and John N Tsitsiklis. On krause's multi-agent consensus model with state-dependent connectivity. IEEE transactions on Automatic Control, 54(11):2586--2597, 2009.
13. Noah E Friedkin. The problem of social control and coordination of complex systems in sociology: A look at the community cleavage problem. IEEE Control Systems, 35(3):40--51, 2015.
14. Irinel-Constantin Moruarescu, Samuel Martin, Antoine Girard, and Aurélie Muller-Gueudin. Coordination in networks of linear impulsive agents. IEEE Transactions on Automatic Control, 61(9):2402--2415, 2016.
15. P. Holme and M. E. Newman. Nonequilibrium phase transition in the coevolution of networks and opinions. Physical Review E, 74(5):056108, 2006.
16. Przemyslaw A Grabowicz, Niloy Ganguly, and Krishna P Gummadi. Distinguishing between topical and non-topical information diffusion mechanisms in social media. In ICWSM, pages 151--160, 2016.
17. Seth A Myers, Chenguang Zhu, and Jure Leskovec. Information diffusion and external influence in networks. In KDD, 2012.
18. Aris Anagnostopoulos, Ravi Kumar, and Mohammad Mahdian. Influence and correlation in social networks. In KDD, 2008.
19. Trisha Greenhalgh, Glenn Robert, Fraser Macfarlane, Paul Bate, and Olivia Kyriakidou. Diffusion of innovations in service organizations: systematic review and recommendations. The Milbank Quarterly, 82(4):581--629, 2004.
20. Thomas W Valente. Social network thresholds in the diffusion of innovations. Social networks, 18(1):69--89, 1996.
21. Yichen Wang, Grady Williams, Evangelos Theodorou, and Le Song. Variational policy for guiding point processes. arXiv preprint arXiv:1701.08585, 2017.
22. A. Zarezade, U. Upadhyay, H. Rabiee, and M. Gomez-Rodriguez. Redqueen: An online algorithm for smart broadcasting in social networks. In WSDM '17, 2017.
23. Ali Zarezade, Abir De, Hamid Rabiee, and Manuel Gomez-Rodriguez. Cheshire: An online algorithm for activity maximization in social networks. In arXiv preprint arXiv:1703.02059, 2017.
24. E. Yildiz, A. Ozdaglar, D. Acemoglu, A. Saberi, and A. Scaglione. Binary opinion dynamics with stubborn agents. ACM Transactions on Economics and Computation, 1(4):19, 2013.
25. Frank Schweitzer and Laxmidhar Behera. Nonlinear voter models: the transition from invasion to coexistence. The European Physical Journal B-Condensed Matter and Complex Systems, 67(3):301--318, 2009.
26. Federico Vazquez, Paul L Krapivsky, and Sidney Redner. Constrained opinion dynamics: Freezing and slow evolution. Journal of Physics A: Mathematical and General, 36(3):L61, 2003.
27. Xavier Castelló, V'ıctor M Egu'ıluz, and Maxi San Miguel. Ordering dynamics with two non-excluding options: bilingualism in language competition. New Journal of Physics, 8(12):308, 2006.
28. Nazareno GF Medeiros, Ana TC Silva, and FG Brady Moreira. Domain motion in the voter model with noise. Physical Review E, 73(4):046120, 2006.
29. Rick Durrett and Simon Levin. Spatial models for species-area curves. Journal of Theoretical Biology, 179(2):119--127, 1996.
30. R. Hegselmann and U. Krause. Opinion dynamics & bounded confidence models, analysis, & simulation. Journal of Artificial Societies & Social Simulation, '02, 5(3).
31. Ulrich Krause. A discrete nonlinear and non-autonomous model of consensus formation. Communications in difference equations, pages 227--236, 2000.
32. Bing Liu. Sentiment analysis and opinion mining. Synthesis lectures on human language technologies, 5(1):1--167, 2012.
33. B. Pang and L. Lee. Opinion mining and sentiment analysis. Foundations and trends in information retrieval, 2(1--2):1--135, 2008.
34. James W Pennebaker, Martha E Francis, and Roger J Booth. Linguistic inquiry and word count: Liwc 2001. Mahway: Lawrence Erlbaum Associates, 71(2001):2001, 2001.
35. Aniko Hannak, Eric Anderson, Lisa Feldman Barrett, Sune Lehmann, Alan Mislove, and Mirek Riedewald. Tweetin'in the rain: Exploring societal-scale effects of weather on mood. In ICWSM, 2012.
36. Huayi Li, Zhiyuan Chen, Arjun Mukherjee, Bing Liu, and Jidong Shao. Analyzing and detecting opinion spam on a large-scale dataset via temporal and spatial patterns. In ICWSM, pages 634--637, 2015.
37. Santosh KC and Arjun Mukherjee. On the temporal dynamics of opinion spamming: Case studies on yelp. In WWW, pages 369--379, 2016.
38. Huayi Li, Geli Fei, Shuai Wang, Bing Liu, Weixiang Shao, Arjun Mukherjee, and Jidong Shao. Bimodal distribution and co-bursting in review spam detection. In WWW, 2017.
39. Bidisha Samanta, Abir De, Abhijnan Chakraborty, and Niloy Ganguly. Lmpp: a large margin point process combining reinforcement and competition for modeling hashtag popularity. In IJCAI, pages 2679--2685, 2017.
40. Bhushan Kulkarni, Sumit Agarwal, Abir De, Sourangshu Bhattacharya, and Niloy Ganguly. SLANT+: A nonlinear model for opinion dynamics in social networks. In ICDM, 2017.
41. Bidisha Samanta, Abir De, and Niloy Ganguly. Strm: A sister tweet reinforcement process for modeling hashtag popularity. In INFOCOM 2017, pages 1--9. IEEE, 2017.
42. Krunal Parmar, Samuel Bushi, Sourangshu Bhattacharya, and Surender Kumar. Forecasting ad-impressions on online retail websites using non-homogeneous hawkes processes. In CIKM, 2017.
43. Abir De, Sourangshu Bhattacharya, Sourav Sarkar, Niloy Ganguly, and Soumen Chakrabarti. Discriminative link prediction using local, community, and global signals. IEEE Transactions on Knowledge and Data Engineering, 28(8):2057--2070, 2016.
44. Abir De, Niloy Ganguly, and Soumen Chakrabarti. Discriminative link prediction using local links, node features and community structure. In ICDM, 2013.
45. Abir De, Maunendra Sankar Desarkar, Niloy Ganguly, and Pabitra Mitra. Local learning of item dissimilarity using content and link structure. In ACM RecSys, 2012.
46. Supplementary material. hrefhttp://www.cnergres.iitkgp.ac.in/supp.pdfhttp://www.cnergres.iitkgp.ac.in/supp.pdf.
47. Jerome Friedman, Trevor Hastie, and Robert Tibshirani. Sparse inverse covariance estimation with the graphical lasso. Biostatistics, 9(3):432--441, 2008.
48. Ajit Singh, Andrew Guillory, and Jeff Bilmes. On bisubmodular maximization. In AISTATS, 2012.
49. Anna Huber and Vladimir Kolmogorov. Towards minimizing k-submodular functions. ISCO, 7422:451--462, 2012.
50. Kazutoshi Ando, Satoru Fujishige, and Takeshi Naitoh. A characterization of bisubmodular functions. Discrete Mathematics, 148(1--3):299--303, 1996.
51. Anna Huber, Andrei Krokhin, and Robert Powell. Skew bisubmodularity and valued csps. SIAM Journal on Computing, 43(3):1064--1084, 2014.
52. Satoru Fujishige, Shin-ichi Tanigawa, and Yuichi Yoshida. Generalized skew bisubmodularity: A characterization and a min--max theorem. Discrete Optimization, 12:1--9, 2014.
53. Justin Ward and Stanislav Zivnỳ. Maximizing k-submodular functions and beyond. ACM Transactions on Algorithms, 12(4):47, 2016.
54. Tyler H Summers, Fabrizio L Cortesi, and John Lygeros. On submodularity and controllability in complex dynamical networks. IEEE Transactions on Control of Network Systems, 3(1):91--101, 2016.
55. George L Nemhauser, Laurence A Wolsey, and Marshall L Fisher. An analysis of approximations for maximizing submodular set functions--i. Mathematical Programming, 14(1):265--294, 1978.
56. Andreas Krause and Daniel Golovin. Submodular function maximization., 2014.
57. D. P. Bertsekas. Dynamic programming and optimal control, volume 1. Athena Scientific Belmont, MA, 1995.
58. F. B. Hanson. Applied stochastic processes and control for Jump-diffusions: modeling, analysis, and computation, volume 13. Siam, 2007.
59. C. K. Garrett. Numerical integration of matrix Riccati differential equations with solution singularities. PhD thesis, The University of Texas at Arlington, May 2013.
60. M. Farajtabar, Y. Wang, M. Gomez-Rodriguez, S. Li, H. Zha, and L. Song. Coevolve: A joint point process model for information diffusion and network co-evolution. In NIPS, 2015.