DynaDiffuse: A Dynamic Diffusion Model for Continuous Time Constrained Influence Maximization

Authors

  • Miao Xie University of Chinese Academy of Sciences
  • Qiusong Yang Institute of Software, Chinese Academy of Sciences
  • Qing Wang Institute of Software, Chinese Academy of Sciences
  • Gao Cong Nanyang Technological University
  • Gerard Melo Tsinghua University/Microsoft Research Asia

DOI:

https://doi.org/10.1609/aaai.v29i1.9203

Keywords:

Social Network, Influence Maximization, Influence Diffusion, Dynamic Networks, Stochastic Model Checking, Greedy Algorithm

Abstract

Studying the spread of phenomena in social networks is critical but still not fully solved. Existing influence maximization models assume a static network, disregarding its evolution over time. We introduce the continuous time constrained influence maximization problem for dynamic diffusion networks, based on a novel diffusion model called DynaDiffuse. Although the problem is NP-hard, the influence spread functions are monotonic and submodular, enabling fast approximations on top of an innovative stochastic model checking approach. Experiments on real social network data show that our model finds higher quality solutions and our algorithm outperforms state-of-art alternatives.

Downloads

Published

2015-02-09

How to Cite

Xie, M., Yang, Q., Wang, Q., Cong, G., & Melo, G. (2015). DynaDiffuse: A Dynamic Diffusion Model for Continuous Time Constrained Influence Maximization. Proceedings of the AAAI Conference on Artificial Intelligence, 29(1). https://doi.org/10.1609/aaai.v29i1.9203