Proceedings

Parameter Learning for Latent Network Diffusion

Download BibTeX Cite

Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 2923-2929.

© 2013 International Joint Conferences on Artificial Intelligence

Abstract

Diffusion processes in networks are increasingly used to model dynamic phenomena such as the spread of information, wildlife, or social influence. Our work addresses the problem of learning the underlying parameters that govern such a diffusion process by observing the time at which nodes become active. A key advantage of our approach is that, unlike previous work, it can tolerate missing observations for some nodes in the diffusion process. Having incomplete observations is characteristic of offline networks used to model the spread of wildlife. We develop an EM algorithm to address parameter learning in such settings. Since both the E and M steps are computationally challenging, we employ a number of optimization methods such as nonlinear and difference-of-convex programming to address these challenges. Evaluation of the approach on the Red-cockaded Woodpecker conservation problem shows that it is highly robust and accurately learns parameters in various settings, even with more than 80% missing data.

  1. [Ahmadizadeh et al., 2010] Kiyan Ahmadizadeh, Bistra Dilkina, Carla P. Gomes, and Ashish Sabharwal. An empirical study of optimization for maximizing diffusion in networks. In Proceedings of the 16th International Conference on Principles and Practice of Constraint Programming, pages 514-521, 2010.
  2. [Anderson and May, 2002] Roy M. Anderson and Robert M. May, editors. Infectious Diseases of Humans: Dynamics and Control. Oxford University Press, 2002.
  3. [Byrd et al., 2006] Richard H. Byrd, Jorge Nocedal, and Richard A. Waltz. KNITRO: An integrated package for nonlinear optimization. In Large Scale Nonlinear Opti- mization, pages 35-59, 2006.
  4. [Dempster et al., 1977] Arthur P. Dempster, Nan M. Laird, and Donald B. Rubin. Maximum likelihood from incom- plete data via the EM algorithm. Journal of the Royal Sta- tistical Society, Series B, 39(1):1-38, 1977.
  5. [Domingos and Richardson, 2001] Pedro Domingos and Matt Richardson. Mining the network value of customers. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 57-66, 2001.
  6. [Golovin et al., 2011] Daniel Golovin, Andreas Krause, Beth Gardner, Sarah J. Converse, and Steve Morey. Dy- namic resource allocation in conservation planning. In Proceedings of the 25th Conference on Artificial Intelli- gence, pages 1331-1336, 2011.
  7. [Gomez-Rodriguez et al., 2012] Manuel Gomez-Rodriguez, Jure Leskovec, and Andreas Krause. Inferring networks of diffusion and influence. ACM Transactions on Knowledge Discovery From Data, 5(4):21, 2012.
  8. [Hanski, 1994] I. Hanski. A practical model of metapopu- lation dynamics. Journal of Animal Ecology, pages 151- 162, 1994.
  9. [Hanski, 1999] I. Hanski, editor. Metapopulation Ecology. Oxford University Press, 1999.
  10. [Kempe et al., 2003] David Kempe, Jon Kleinberg, and Éva Tardos. Maximizing the spread of influence through a so- cial network. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 137- 146, 2003.
  11. [Kumar et al., 2012] Akshat Kumar, Xiaojian Wu, and Shlomo Zilberstein. Lagrangian relaxation techniques for scalable spatial conservation planning. In AAAI Confer- ence on Artificial Intelligence, pages 309-315, 2012.
  12. [Leskovec et al., 2007] Jure Leskovec, Lada A. Adamic, and Bernardo A. Huberman. The dynamics of viral marketing. ACM Transactions on the Web, 1(1), May 2007.
  13. [Moilanen, 1999] A. Moilanen. Patch occupancy models of metapopulation dynamics: Efficient parameter estimation using implicit statistical inference. Ecology, 80(3):1031- 1043, 1999.
  14. [Myers and Leskovec, 2010] Seth A. Myers and Jure Leskovec. On the convexity of latent social network inference. In Advances in Neural Information Processing Systems, pages 1741-1749, 2010.
  15. [Neal and Hinton, 1998] Radford Neal and Geoffrey E. Hin- ton. A view of the EM algorithm that justifies incremental, sparse, and other variants. In Learning in Graphical Mod- els, pages 355-368, 1998.
  16. [Netrapalli and Sanghavi, 2012] Praneeth Netrapalli and Su- jay Sanghavi. Learning the graph of epidemic cascades. In ACM Joint International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS '12, pages 211-222, 2012.
  17. [Sheldon et al., 2010] Daniel Sheldon, Bistra Dilkina, Adam Elmachtoub, Ryan Finseth, Ashish Sabharwal, Jon Con- rad, Carla Gomes, David Shmoys, William Allen, Ole Amundsen, and William Vaughan. Maximizing the spread of cascades using network design. In Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence, pages 517-526, 2010.
  18. [Sriperumbudur and Lanckriet, 2009] Bharath Sriperum- budur and Gert Lanckriet. On the convergence of the concave-convex procedure. In Advances in Neural Information Processing Systems, pages 1759-1767, 2009.
  19. [ter Braak and Etienne, 2003] Cajo J.F. ter Braak and Ram- pal S. Etienne. Improved Bayesian analysis of metapopu- lation data with an application to a tree frog metapopula- tion. Ecology, 84(1):231-241, 2003.
  20. [Wang et al., 2012] Liaoruo Wang, Stefano Ermon, and John E. Hopcroft. Feature-enhanced probabilistic mod- els for diffusion network inference. In European confer- ence on Machine Learning and Knowledge Discovery in Databases, ECML PKDD'12, pages 499-514, 2012.
  21. [Wei and Tanner, 1990] Greg Wei and Martin Tanner. A Monte Carlo implementation of the EM algorithm and the poor man's data augmentation algorithms. Journal of the American Statistical Association, 85:699-704, 1990.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards