COEVOLVE: A Joint Point Process Model for Information Diffusion and Network Co-evolution

ABSTRACT

Information diffusion in online social networks is affected by the underlying network topology, but it also has the power to change it. Online users are constantly creating new links when they are exposed to new information sources, and in turn these links are alternating the way information spreads. However, these two highly intertwined stochastic processes---information diffusion and network evolution---have been typically studied separately, ignoring their co-evolutionary dynamics. In this work, we propose a temporal point process model, COEVOLVE, for such joint dynamics, allowing the intensity of one process to be modulated by that of the other. The model allows us to efficiently simulate interleaved diffusion and network events, and generate traces obeying common diffusion and network patterns observed in real-world networks. Moreover, we develop a convex optimization framework to learn the parameters of the model from historical diffusion and network evolution traces. Experiments in both synthetic data and real data gathered from Twitter show that our model provides a good fit to the data as well as more accurate predictions than alternatives.

References

1. D. Antoniades and C. Dovrolis. Co-evolutionary dynamics in social networks: A case study of twitter. arXiv preprint arXiv:1309.6001, 2013.
2. L. Backstrom, P. Boldi, M. Rosa, J. Ugander, and S. Vigna. Four degrees of separation. In Proceedings of the 4th Annual ACM Web Science Conference, pages 33--42, 2012.
3. D. Chakrabarti, Y. Zhan, and C. Faloutsos. R-mat: A recursive model for graph mining. Computer Science Department, page 541, 2004.
4. J. Cheng, L. Adamic, P. A. Dow, J. M. Kleinberg, and J. Leskovec. Can cascades be predicted In Proceedings of the 23rd international conference on World wide web, pages 925--936, 2014.
5. N. Du, L. Song, M. Gomez-Rodriguez, and H. Zha. Scalable influence estimation in continuous-time diffusion networks. In Advances in Neural Information Processing Systems 26, 2013.
6. P. Erdos and A. Rényi. On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci, 5:17--61, 1960.
7. M. Farajtabar, N. Du, M. Gomez-Rodriguez, I. Valera, H. Zha, and L. Song. Shaping social activity by incentivizing users. In Advances in Neural Information Processing Systems (NIPS), 2014.
8. M. Farajtabar, Y. Wang, M. Gomez-Rodriguez, S. Li, and H. Zha. Coevolve: A joint point process model for information diffusion and network evolution. Journal of Machine Learning Research, 18:1--49, 2017.
9. M. Farajtabar, J. Yang, X. Ye, H. Xu, R. Trivedi, E. Khalil, S. Li, L. Song, and H. Zha. Fake news mitigation via point process based intervention. arXiv preprint arXiv:1703.07823, 2017.
10. M. Farajtabar, X. Ye, S. Harati, L. Song, and H. Zha. Multistage campaigning in social networks. In Advances in Neural Information Processing Systems, pages 4718--4726, 2016.
11. S. Goel, D. J. Watts, and D. G. Goldstein. The structure of online diffusion networks. In Proceedings of the 13th ACM conference on electronic commerce, pages 623--638, 2012.
12. M. Gomez-Rodriguez, D. Balduzzi, and B. Schölkopf. Uncovering the temporal dynamics of diffusion networks. In Proceedings of the International Conference on Machine Learning, 2011.
13. M. Gomez-Rodriguez, J. Leskovec, and A. Krause. Inferring networks of diffusion and influence. In Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 1019--1028. ACM, 2010.
14. M. Granovetter. The strength of weak ties. American journal of sociology, pages 1360--1380, 1973.
15. S. A. Hosseini, K. Alizadeh, A. Khodadadi, A. Arabzadeh, M. Farajtabar, H. Zha, and H. R. Rabiee. Recurrent poisson factorization for temporal recommendation. arXiv preprint arXiv:1703.01442, 2017.
16. D. Hunter, P. Smyth, D. Q. Vu, and A. U. Asuncion. Dynamic egocentric models for citation networks. In Proceedings of the 28th International Conference on Machine Learning, pages 857--864, 2011.
17. T. Iwata, A. Shah, and Z. Ghahramani. Discovering latent influence in online social activities via shared cascade poisson processes. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 266--274. ACM, 2013.
18. M. R. Karimi, E. Tavakoli, M. Farajtabar, L. Song, and M. Gomez-Rodriguez. Smart broadcasting: Do you want to be seen arXiv preprint arXiv:1605.06855, 2016.
19. H. Kwak, C. Lee, H. Park, and S. Moon. What is Twitter, a social network or a news media In Proceedings of the 19th International Conference on World Wide Web, pages 591--600, New York, NY, USA, 2010. ACM.
20. J. Leskovec, L. Backstrom, R. Kumar, and A. Tomkins. Microscopic evolution of social networks. In Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 462--470. ACM, 2008.
21. J. Leskovec, D. Chakrabarti, J. Kleinberg, C. Faloutsos, and Z. Ghahramani. Kronecker graphs: An approach to modeling networks. Journal of Machine Learning Research, 11(Feb):985--1042, 2010.
22. J. Leskovec, J. Kleinberg, and C. Faloutsos. Graphs over time: densification laws, shrinking diameters and possible explanations. In Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, pages 177--187. ACM, 2005.
23. S. W. Linderman and R. P. Adams. Discovering latent network structure in point process data. In International Conference on Machine Learning (ICML), 2014.
24. T. J. Liniger. Multivariate Hawkes Processes. PhD thesis, Swiss Federal Institute of Technology Zurich, 2009.
25. S. A. Myers and J. Leskovec. The bursty dynamics of the twitter information network. In 23rd International Conference on the World Wide Web, pages 913--924, 2014.
26. D. M. Romero and J. Kleinberg. The directed closure process in hybrid social-information networks, with an analysis of link formation on twitter. In ICWSM, 2010.
27. B. Tabibian, I. Valera, M. Farajtabar, L. Song, B. Schölkopf, and M. Gomez-Rodriguez. Distilling information reliability and source trustworthiness from digital traces. arXiv preprint arXiv:1610.07472, 2016.
28. L. Tran, M. Farajtabar, L. Song, and H. Zha. Netcodec: Community detection from individual activities. In SDM, 2015.
29. J. Ugander, L. Backstrom, and J. Kleinberg. Subgraph frequencies: Mapping the empirical and extremal geography of large graph collections. In Proceedings of the 22nd international conference on World Wide Web, pages 1307--1318. International World Wide Web Conferences Steering Committee, 2013.
30. D. Q. Vu, D. Hunter, P. Smyth, and A. U. Asuncion. Continuous-time regression models for longitudinal networks. In Advances in Neural Information Processing Systems, pages 2492--2500, 2011.
31. D. J. Watts and S. H. Strogatz. Collective dynamics of small-world networks. Nature, 393(6684):440--442, June 1998.
32. L. Weng, J. Ratkiewicz, N. Perra, B. Gonccalves, C. Castillo, F. Bonchi, R. Schifanella, F. Menczer, and A. Flammini. The role of information diffusion in the evolution of social networks. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 356--364. ACM, 2013.
33. A. Zarezade, A. Khodadadi, M. Farajtabar, H. R. Rabiee, and H. Zha. Correlated cascades: Compete or cooperate. arXiv preprint arXiv:1510.00936, 2015.
34. K. Zhou, H. Zha, and L. Song. Learning triggering kernels for multi-dimensional hawkes processes. In International Conference on Machine Learning (ICML), 2013.

Index Terms

• Information systems

  • World Wide Web

    • Web applications

      • Social networks

• Networks

  • Network properties

    • Network dynamics

    • Network structure

      • Topology analysis and generation

  • Network types

    • Overlay and other logical network structures

      • Online social networks