nips nips2011 nips2011-234 nips2011-234-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Flavio Chierichetti, David Liben-nowell, Jon M. Kleinberg
Abstract: Motivated by the spread of on-line information in general and on-line petitions in particular, recent research has raised the following combinatorial estimation problem. There is a tree T that we cannot observe directly (representing the structure along which the information has spread), and certain nodes randomly decide to make their copy of the information public. In the case of a petition, the list of names on each public copy of the petition also reveals a path leading back to the root of the tree. What can we conclude about the properties of the tree we observe from these revealed paths, and can we use the structure of the observed tree to estimate the size of the full unobserved tree T ? Here we provide the first algorithm for this size estimation task, together with provable guarantees on its performance. We also establish structural properties of the observed tree, providing the first rigorous explanation for some of the unusual structural phenomena present in the spread of real chain-letter petitions on the Internet. 1
[1] E. Adar, L. Zhang, L. A. Adamic, and R. M. Lukose. Implicit structure and the dynamics of blogspace. In Workshop on the Weblogging Ecosystem, 2004.
[2] D. Aldous. The continuum random tree II: An overview. In M. T. Barlow and N. H. Bingham, editors, Stochastic Analysis, pages 23–70. Cambridge University Press, 1991.
[3] K. B. Athreya and P. E. Ney. Branching Processes. Dover, 2004.
[4] E. Bakshy, B. Karrer, and L. A. Adamic. Social influence and the diffusion of user-created content. In Proc. 10th ACM Conference on Electronic Commerce, pages 325–334, 2009.
[5] C. H. Bennett, M. Li, and B. Ma. Chain letters and evolutionary histories. Scientific American, 288(6):76–79, June 2003.
[6] M. Cha, A. Mislove, and P. K. Gummadi. A measurement-driven analysis of information propagation in the flickr social network. In Proc. 18th International World Wide Web Conference, pages 721–730, 2009.
[7] J. Earl. The dynamics of protest-related diffusion on the web. Information, Communication, and Society, 13(26):209–225, 2010.
[8] R. K. Garrett. Protest in an information society: A review of literature on social movements and new ICTs. Information, Communication, and Society, 9(2):202–224, 2006.
[9] B. Golub and M. O. Jackson. Using selection bias to explain the observed structure of internet diffusions. Proc. Natl. Acad. Sci. USA, 107(24):10833–10836, 15 June 2010.
[10] D. Gruhl, R. V. Guha, D. Liben-Nowell, and A. Tomkins. Information diffusion through blogspace. In Proc. 13th International World Wide Web Conference, 2004.
[11] J. L. Iribarren and E. Moro. Impact of human activity patterns on the dynamics of information diffusion. Physical Review Letters, 103(3), July 2009.
[12] J. Kleinberg. Cascading behavior in networks: Algorithmic and economic issues. In N. Nisan, ´ T. Roughgarden, E. Tardos, and V. Vazirani, editors, Algorithmic Game Theory, pages 613– 632. Cambridge University Press, 2007.
[13] R. Kumar, M. Mahdian, and M. McGlohon. Dynamics of conversations. In Proc. 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 553– 562, 2010.
[14] J. Leskovec, L. Adamic, and B. Huberman. The dynamics of viral marketing. ACM Transactions on the Web, 1(1), May 2007.
[15] J. Leskovec, A. Singh, and J. M. Kleinberg. Patterns of influence in a recommendation network. In Pacific-Asia Conference on Knowledge Discovery and Data Mining, pages 380–389, 2006.
[16] D. Liben-Nowell and J. Kleinberg. Tracing information flow on a global scale using Internet chain-letter data. Proc. Natl. Acad. Sci. USA, 105(12):4633–4638, Mar. 2008.
[17] E. Sun, I. Rosenn, C. Marlow, and T. M. Lento. Gesundheit! Modeling contagion through Facebook News Feed. In Proc. 3rd International Conference on Weblogs and Social Media, 2009.
[18] D. Wang, Z. Wen, H. Tong, C.-Y. Lin, C. Song, and A.-L. Barab´ si. Information spreading in a context. In Proc. 20th International World Wide Web Conference, pages 735–744, 2011.
[19] F. Wu, B. A. Huberman, L. A. Adamic, and J. R. Tyler. Information flow in social groups. Physica A, 337(1-2):327–335, 2004. 9