SIR-Hawkes: Linking Epidemic Models and Hawkes Processes to Model Diffusions in Finite Populations

ABSTRACT

Among the statistical tools for online information diffusion modeling, both epidemic models and Hawkes point processes are popular choices. The former originate from epidemiology, and consider information as a viral contagion which spreads into a population of online users. The latter have roots in geophysics and finance, view individual actions as discrete events in continuous time, and modulate the rate of events according to the self-exciting nature of event sequences. Here, we establish a novel connection between these two frameworks. Namely, the rate of events in an extended Hawkes model is identical to the rate of new infections in the Susceptible-Infected-Recovered (SIR) model after marginalizing out recovery events -- which are unobserved in a Hawkes process. This result paves the way to apply tools developed for SIR to Hawkes, and vice versa. It also leads to HawkesN, a generalization of the Hawkes model which accounts for a finite population size. Finally, we derive the distribution of cascade sizes for HawkesN, inspired by methods in stochastic SIR. Such distributions provide nuanced explanations to the general unpredictability of popularity: the distribution for diffusion cascade sizes tends to have two modes, one corresponding to large cascade sizes and another one around zero.

References

1. Linda J. S. Allen. 2008. An Introduction to Stochastic Epidemic Models. In Mathematical Epidemiology. Springer, Berlin, Heidelberg, Chapter 3, 81--130.
2. Peng Bao, Hua-Wei Shen, Xiaolong Jin, and Xue-Qi Cheng. 2015. Modeling and Predicting Popularity Dynamics of Microblogs using Self-Excited Hawkes Processes. In Proceedings of the 24th International Conference on World Wide Web - WWW '15 Companion. ACM Press, New York, New York, USA, 9--10.
3. Christian Bauckhage, Fabian Hadiji, and Kristian Kersting. 2015. How Viral Are Viral Videos?. In ICWSM. 22-30.
4. Georgiy V. Bobashev, D. Michael Goedecke, Feng Yu, and Joshua M. Epstein. 2007. A hybrid epidemic model: Combining the advantages of agent-based and equation-based approaches. In Proceedings - Winter Simulation Conference. IEEE, 1532-1537.
5. Biao Chang, Hengshu Zhu, Yong Ge, Enhong Chen, Hui Xiong, and Chang Tan. 2014. Predicting the Popularity of Online Serials with Autoregressive Models. In Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management - CIKM '14. ACM Press, New York, New York, USA, 1339--1348.
6. Riley Crane and Didier Sornette. 2008. Robust dynamic classes revealed by measuring the response function of a social system. Proceedings of the National Academy of Sciences 105, 41 (oct 2008), 15649--15653.
7. D J Daley and D Vere-Jones. 2008. An introduction to the theory of point processes. {V}ol. {I}. Vol. I. xviii+573 pages.
8. Wanying Ding, Yue Shang, Lifan Guo, Xiaohua Hu, Rui Yan, and Tingting He. 2015. Video Popularity Prediction by Sentiment Propagation via Implicit Network. In Proceedings of the 24th ACM International on Conference on Information and Knowledge Management. ACM, 1621--1630.
9. Ling Feng, Yanqing Hu, Baowen Li, H Eugene Stanley, Shlomo Havlin, and Lidia A Braunstein. 2015. Competing for attention in social media under information overload conditions. PloS one 10, 7 (2015), e0126090.
10. Robert Fourer, David M Gay, and Brian W Kernighan. 1987. AMPL: A mathematical programming language. AT&T Bell Laboratories Murray Hill, NJ 07974.
11. Shuai Gao, Jun Ma, and Zhumin Chen. 2015. Modeling and Predicting Retweeting Dynamics on Microblogging Platforms. In Proceedings of the Eighth ACM International Conference on Web Search and Data Mining - WSDM '15. ACM Press, New York, New York, USA, 107--116.
12. Sharad Goel, Ashton Anderson, Jake Hofman, and Duncan J Watts. 2015. The structural virality of online diffusion. Management Science 62, 1 (2015), 180--196.
13. William Goffman. 1971. A Mathematical Method for Analyzing the Growth of a Scientific Discipline. Journal of the ACM (JACM) 18, 2 (apr 1971), 173--185.
14. Manuel Gomez-Rodriguez, Le Song, Nan Du, Hongyuan Zha, and Bernhard Schölkopf. 2016. Influence Estimation and Maximization in Continuous-Time Diffusion Networks. ACM Transactions on Information Systems 34, 2 (feb 2016), 1--33.
15. Daniel Gruhl, R. Guha, David Liben-Nowell, and Andrew Tomkins. 2004. Information Diffusion Through Blogspace. In Proceedings of the 13th International Conference on World Wide Web (WWW '04). ACM, New York, NY, USA, 491--501.
16. Alan G. Hawkes. 1971. Spectra of some self-exciting and mutually exciting point processes. Biometrika 58, 1 (apr 1971), 83--90.
17. Agnès Helmstetter and Didier Sornette. 2002. Subcritical and supercritical regimes in epidemic models of earthquake aftershocks. Journal of Geophysical Research: Solid Earth 107, B10 (2002), ESE 10--1Ð-ESE 10--21. arXiv:cond-mat/0109318
18. W. O. Kermack and A. G. McKendrick. 1927. A Contribution to the Mathematical Theory of Epidemics. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 115, 772 (aug 1927), 700--721.
19. Ryota Kobayashi and Renaud Lambiotte. 2016. TiDeH: Time-Dependent Hawkes Process for Predicting Retweet Dynamics. In ICWSM 2016. arXiv:1603.09449
20. Patrick J. Laub, Thomas Taimre, and Philip K. Pollett. 2015. Hawkes Processes. (jul 2015). arXiv:1507.02822 http://arxiv.org/abs/1507.02822
21. Travis Martin, Jake M. Hofman, Amit Sharma, Ashton Anderson, and Duncan J. Watts. 2016. Exploring Limits to Prediction in Complex Social Systems. In Proceedings of the 25th International Conference on World Wide Web. 683--694. arXiv:1602.01013
22. Hongyuan Mei and Jason Eisner. 2017. The Neural Hawkes Process: A Neurally Self-Modulating Multivariate Point Process. In Advances in Neural Information Processing Systems 30. 6757--6767. arXiv:1612.09328 https://arxiv.org/abs/1612. 09328
23. Swapnil Mishra, Marian-Andrei Rizoiu, and Lexing Xie. 2016. Feature Driven and Point Process Approaches for Popularity Prediction. In Proceedings of the 25th ACM International on Conference on Information and Knowledge Management - CIKM '16. ACM Press, Indianapolis, IN, USA, 1069--1078.
24. Yamir Moreno, Maziar Nekovee, and Amalio F. Pacheco. 2004. Dynamics of rumor spreading in complex networks. Physical Review E - Statistical, Nonlinear, and Soft Matter Physics 69, 6 2 (jun 2004), 066130. arXiv:cond-mat/0312131
25. online supplement. 2017. Appendix: SIR Hawkes: Linking Epidemic Models and Hawkes Point Processes for Online Information Diffusion. (2017). https: //arxiv.org/pdf/1711.01679.pdf#page=11.
26. Romualdo Pastor-Satorras and Alessandro Vespignani. 2001. Epidemic spreading in scale-free networks. Physical Review Letters 86, 14 (apr 2001), 3200--1203. arXiv:cond-mat/0010317
27. Henrique Pinto, Jussara M. Almeida, and Marcos A. Gonçalves. 2013. Using early view patterns to predict the popularity of youtube videos. In Proceedings of the sixth ACM international conference on Web search and data mining - WSDM '13. ACM Press, New York, New York, USA, 365.
28. Marian-Andrei Rizoiu, Lexing Xie, Scott Sanner, Manuel Cebrian, Honglin Yu, and Pascal Van Hentenryck. 2017. Expecting to be HIP: Hawkes Intensity Processes for Social Media Popularity. In 26th International Conference on World Wide Web - WWW '17. ACM Press, Perth, Australia., 735--744. arXiv:1602.06033
29. Hw Shen, Dashun Wang, Chaoming Song, and Al Barabási. 2014. Modeling and Predicting Popularity Dynamics via Reinforced Poisson Processes. In Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence. AAAI Press, Québec City, Québec, Canada., 291--297. arXiv:arXiv:1401.0778v1
30. Ernest S. Shtatland and Timur Shtatland. 2008. Another Look at Low-Order Autoregressive Models in Early Detection of Epidemic Outbreaks and Explosive Behaviors in Economic and Financial Time Series. In SGF Proceedings.
31. Gabor Szabo and Bernardo a. Huberman. 2010. Predicting the popularity of online content. Commun. ACM 53, 8 (aug 2010), 80. arXiv:0811.0405
32. Daniel Trpevski, Wallace K. S. Tang, and Ljupco Kocarev. 2010. Model for rumor spreading over networks. Physical Review E - Statistical, Nonlinear, and Soft Matter Physics 81, 5 (may 2010), 056102.
33. A Wächter and L T Biegler. 2006. On the Implementation of a Primal-Dual Interior Point Filter Line Search Algorithm for Large-Scale Nonlinear Programming. Mathematical Programming 106, 1 (2006), 25--57.
34. Jacco Wallinga and Peter Teunis. 2004. Different epidemic curves for severe acute respiratory syndrome reveal similar impacts of control measures. American journal of epidemiology 160, 6 (sep 2004), 509--16.
35. Yichen Wang, Evangelos Theodorou, Apurv Verma, and Le Song. 2016. A Stochastic Differential Equation Framework for Guiding Online User Activities in Closed Loop. (mar 2016). arXiv:1603.09021 http://arxiv.org/abs/1603.09021
36. Yichen Wang, Xiaojing Ye, Haomin Zhou, Hongyuan Zha, and Le Song. 2017. Linking Micro Event History to Macro Prediction in Point Process Models. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, Vol. 54. 1375--1384. http://proceedings.mlr.press/v54/wang17f.html
37. Duncan J. Watts. 2011. Everything is obvious: once you know the answer. Crown Business. 335 pages.
38. Jiyoung Woo and Hsinchun Chen. 2016. Epidemic model for information diffusion in web forums: experiments in marketing exchange and political dialog. SpringerPlus 5, 1 (dec 2016), 66.
39. Ping Yan. 2008. Distribution Theory, Stochastic Processes and Infectious Disease Modelling. In Mathematical Epidemiology, Wu J. Brauer F., van den Driessche P. (Ed.). Springer, Berlin, Heidelberg, Chapter 10, 229--293.
40. Linyun Yu, Peng Cui, Fei Wang, Chaoming Song, and Shiqiang Yang. 2017. Uncovering and predicting the dynamic process of information cascades with survival model. Knowledge and Information Systems 50, 2 (feb 2017), 633--659. arXiv:1505.07193
41. Damián H. Zanette. 2002. Dynamics of rumor propagation on small-world networks. Physical Review E - Statistical, Nonlinear, and Soft Matter Physics 65, 4 (mar 2002), 041908. arXiv:0110324
42. Ali Zarezade, Abir De, Hamid Rabiee, and Manuel Gomez Rodriguez. 2017. Cheshire: An Online Algorithm for Activity Maximization in Social Networks. (mar 2017). arXiv:1703.02059 http://arxiv.org/abs/1703.02059
43. Ali Zarezade, Utkarsh Upadhyay, Hamid Rabiee, and Manuel Gomez Rodriguez. 2017. RedQueen: An Online Algorithm for Smart Broadcasting in Social Networks. In 10th ACM International Conference on Web Search and Data Mining. arXiv:1610.05773 http://arxiv.org/abs/1610.05773
44. Qingyuan Zhao, Murat A Erdogdu, Hera Y He, Anand Rajaraman, and Jure Leskovec. 2015. SEISMIC: A Self-Exciting Point Process Model for Predicting Tweet Popularity. In ACM SIGKDD Conference on Knowledge Discovery and Data Mining

Index Terms

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

      • Graph algorithms