nips nips2010 nips2010-190 nips2010-190-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Seth Myers, Jure Leskovec
Abstract: In many real-world scenarios, it is nearly impossible to collect explicit social network data. In such cases, whole networks must be inferred from underlying observations. Here, we formulate the problem of inferring latent social networks based on network diffusion or disease propagation data. We consider contagions propagating over the edges of an unobserved social network, where we only observe the times when nodes became infected, but not who infected them. Given such node infection times, we then identify the optimal network that best explains the observed data. We present a maximum likelihood approach based on convex programming with a l1 -like penalty term that encourages sparsity. Experiments on real and synthetic data reveal that our method near-perfectly recovers the underlying network structure as well as the parameters of the contagion propagation model. Moreover, our approach scales well as it can infer optimal networks of thousands of nodes in a matter of minutes.
[1] A. Ahmed and E. Xing. Recovering time-varying networks of dependencies in social and biological studies. PNAS, 106(29):11878, 2009.
[2] N. T. J. Bailey. The Mathematical Theory of Infectious Diseases and its Applications. Hafner Press, 2nd edition, 1975.
[3] A.-L. Barab´ si and R. Albert. Emergence of scaling in random networks. Science, 1999. a
[4] M. Choudhury, W. A. Mason, J. M. Hofman, and D. J. Watts. Inferring relevant social networks from interpersonal communication. In WWW ’10, pages 301–310, 2010.
[5] N. Eagle, A. S. Pentland, and D. Lazer. Inferring friendship network structure by using mobile phone data. PNAS, 106(36):15274–15278, 2009.
[6] J. Friedman, T. Hastie, and R. Tibshirani. Sparse inverse covariance estimation with the graphical lasso. Biostat, 9(3):432–441, 2008.
[7] L. Getoor, N. Friedman, D. Koller, and B. Taskar. Learning probabilistic models of link structure. JMLR, 3:707, 2003.
[8] Z. Ghahramani. Learning dynamic Bayesian networks. Adaptive Processing of Sequences and Data Structures, page 168, 1998.
[9] L. Giot, J. Bader, C. Brouwer, A. Chaudhuri, B. Kuang, Y. Li, Y. Hao, C. Ooi, B. Godwin, et al. A protein interaction map of Drosophila melanogaster. Science, 302(5651):1727, 2003.
[10] M. Gomez-Rodriguez, J. Leskovec, and A. Krause. Inferring networks of diffusion and influence. In KDD ’10, 2010.
[11] S. Hill, F. Provost, and C. Volinsky. Network-based marketing: Identifying likely adopters via consumer networks. Statistical Science, 21(2):256–276, 2006.
[12] R. Jansen, H. Yu, D. Greenbaum, et al. A bayesian networks approach for predicting proteinprotein interactions from genomic data. Science, 302(5644):449–453, October 2003.
[13] G. Kossinets and D. J. Watts. Empirical analysis of an evolving social network. Science, 2006.
[14] J. Leskovec, L. A. Adamic, and B. A. Huberman. The dynamics of viral marketing. ACM TWEB, 1(1):2, 2007.
[15] J. Leskovec, L. Backstrom, and J. Kleinberg. Meme-tracking and the dynamics of the news cycle. In KDD ’09, pages 497–506, 2009.
[16] J. Leskovec and E. Horvitz. Planetary-scale views on a large instant-messaging network. In WWW ’08, 2008.
[17] J. Leskovec, A. Singh, and J. M. Kleinberg. Patterns of influence in a recommendation network. In PAKDD ’06, pages 380–389, 2006.
[18] D. Liben-Nowell and J. Kleinberg. The link prediction problem for social networks. In CIKM ’03, pages 556–559, 2003.
[19] N. Meinshausen and P. Buehlmann. High-dimensional graphs and variable selection with the lasso. The Annals of Statistics, pages 1436–1462, 2006.
[20] M. Middendorf, E. Ziv, and C. Wiggins. Inferring network mechanisms: the Drosophila melanogaster protein interaction network. PNAS, 102(9):3192, 2005.
[21] M. Schmidt, A. Niculescu-Mizil, and K. Murphy. Learning graphical model structure using l1-regularization paths. In AAAI, volume 22, page 1278, 2007.
[22] L. Song, M. Kolar, and E. Xing. Time-varying dynamic bayesian networks. In NIPS ’09.
[23] B. Taskar, M. F. Wong, P. Abbeel, and D. Koller. Link prediction in relational data. NIPS ’03.
[24] J. Vert and Y. Yamanishi. Supervised graph inference. NIPS ’05.
[25] M. J. Wainwright, P. Ravikumar, and J. D. Lafferty. High-dimensional graphical model selection using ℓ1 -regularized logistic regression. In PNAS, 2006.
[26] J. Wallinga and P. Teunis. Different epidemic curves for severe acute respiratory syndrome reveal similar impacts of control measures. Amer. J. of Epidemiology, 160(6):509–516, 2004.
[27] S. Wasserman and K. Faust. Social Network Analysis : Methods and Applications. Cambridge University Press, 1994. 9