nips nips2013 nips2013-288 nips2013-288-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Nan Du, Le Song, Manuel Gomez-Rodriguez, Hongyuan Zha
Abstract: If a piece of information is released from a media site, can we predict whether it may spread to one million web pages, in a month ? This influence estimation problem is very challenging since both the time-sensitive nature of the task and the requirement of scalability need to be addressed simultaneously. In this paper, we propose a randomized algorithm for influence estimation in continuous-time diffusion networks. Our algorithm can estimate the influence of every node in a network with |V| nodes and |E| edges to an accuracy of using n = O(1/ 2 ) randomizations and up to logarithmic factors O(n|E|+n|V|) computations. When used as a subroutine in a greedy influence maximization approach, our proposed algorithm is guaranteed to find a set of C nodes with the influence of at least (1 − 1/e) OPT −2C , where OPT is the optimal value. Experiments on both synthetic and real-world data show that the proposed algorithm can easily scale up to networks of millions of nodes while significantly improves over previous state-of-the-arts in terms of the accuracy of the estimated influence and the quality of the selected nodes in maximizing the influence. 1
´
[1] David Kempe, Jon Kleinberg, and Eva Tardos. Maximizing the spread of influence through a social network. In KDD, pages 137–146, 2003.
[2] Wei Chen, Yajun Wang, and Siyu Yang. Efficient influence maximization in social networks. In KDD, pages 199–208, 2009.
[3] Wei Chen, Yifei Yuan, and Li Zhang. Scalable influence maximization in social networks under the linear threshold model. In ICDM, pages 88–97, 2010.
[4] Amit Goyal, Francesco Bonchi, and Laks V. S. Lakshmanan. A data-based approach to social influence maximization. Proc. VLDB Endow., 5, 2011.
[5] Jure Leskovec, Andreas Krause, Carlos Guestrin, Christos Faloutsos, Jeanne M. VanBriesen, and Natalie S. Glance. Cost-effective outbreak detection in networks. In KDD, pages 420–429, 2007.
[6] Matthew Richardson and Pedro Domingos. Mining knowledge-sharing sites for viral marketing. In KDD, pages 61–70, 2002.
[7] Manuel Gomez-Rodriguez and Bernhard Sch¨ lkopf. Influence maximization in continuous o time diffusion networks. In ICML ’12, 2012.
[8] Nan Du, Le Song, Alexander J. Smola, and Ming Yuan. Learning networks of heterogeneous influence. In NIPS, 2012.
[9] Nan Du, Le Song, Hyenkyun Woo, and Hongyuan Zha. Uncover topic-sensitive information diffusion networks. In AISTATS, 2013.
[10] Manuel Gomez-Rodriguez, David Balduzzi, and Bernhard Sch¨ lkopf. Uncovering the tempoo ral dynamics of diffusion networks. In ICML, pages 561–568, 2011.
[11] Manuel Gomez-Rodriguez, Jure Leskovec, and Bernhard Sch¨ lkopf. Structure and Dynamics o of Information Pathways in On-line Media. In WSDM, 2013.
[12] Ke Zhou, Le Song, and Hongyuan Zha. Learning social infectivity in sparse low-rank networks using multi-dimensional hawkes processes. In Artificial Intelligence and Statistics (AISTATS), 2013.
[13] Ke Zhou, Hongyuan Zha, and Le Song. Learning triggering kernels for multi-dimensional hawkes processes. In International Conference on Machine Learning(ICML), 2013.
[14] Manuel Gomez-Rodriguez, Jure Leskovec, and Bernhard Sch¨ lkopf. Modeling information o propagation with survival theory. In ICML, 2013.
[15] Shuanghong Yang and Hongyuan Zha. Mixture of mutually exciting processes for viral diffusion. In International Conference on Machine Learning(ICML), 2013.
[16] Jerald F. Lawless. Statistical Models and Methods for Lifetime Data. Wiley-Interscience, 2002.
[17] Edith Cohen. Size-estimation framework with applications to transitive closure and reachability. Journal of Computer and System Sciences, 55(3):441–453, 1997.
[18] GL Nemhauser, LA Wolsey, and ML Fisher. An analysis of approximations for maximizing submodular set functions. Mathematical Programming, 14(1), 1978.
[19] Andreas Krause. Ph.D. Thesis. CMU, 2008.
[20] Jure Leskovec, Deepayan Chakrabarti, Jon M. Kleinberg, Christos Faloutsos, and Zoubin Ghahramani. Kronecker graphs: An approach to modeling networks. JMLR, 11, 2010.
[21] Manuel Gomez-Rodriguez, Jure Leskovec, and Andreas Krause. Inferring networks of diffusion and influence. In KDD, 2010.
[22] David Easley and Jon Kleinberg. Networks, Crowds, and Markets: Reasoning About a Highly Connected World. Cambridge University Press, 2010.
[23] Jure Leskovec, Lars Backstrom, and Jon M. Kleinberg. Meme-tracking and the dynamics of the news cycle. In KDD, 2009.
[24] Praneeth Netrapalli and Sujay Sanghavi. Learning the graph of epidemic cascades. In SIGMETRICS/PERFORMANCE, pages 211–222. ACM, 2012.
[25] Wei Chen, Chi Wang, and Yajun Wang. Scalable influence maximization for prevalent viral marketing in large-scale social networks. In KDD ’10, pages 1029–1038, 2010. 9