2010 InferringNetworksofDiffusionand

• (Gomez Rodriguez et al., 2010) ⇒ Manuel Gomez Rodriguez, Jure Leskovec, and Andreas Krause. (2010). “Inferring Networks of Diffusion and Influence.” In: Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2010). doi:10.1145/1835804.1835933

Subject Headings: Influence Propagation.

Cited By

• http://scholar.google.com/scholar?q=%22Inferring+networks+of+diffusion+and+influence%22+2010
• http://portal.acm.org/citation.cfm?id=1835933&preflayout=flat#citedby

Quotes

Abstract

Information diffusion and virus propagation are fundamental processes talking place in networks. While it is often possible to directly observe when nodes become infected, observing individual transmissions (i.e., who infects whom or who influences whom) is typically very difficult. Furthermore, in many applications, the underlying network over which the diffusions and propagations spread is actually unobserved. We tackle these challenges by developing a method for tracing paths of diffusion and influence through networks and inferring the networks over which contagions propagate. Given the times when nodes adopt pieces of information or become infected, we identify the optimal network that best explains the observed infection times. Since the optimization problem is NP-hard to solve exactly, we develop an efficient approximation algorithm that scales to large datasets and in practice gives provably near-optimal performance. We demonstrate the effectiveness of our approach by tracing information cascades in a set of 170 million blogs and news articles over a one year period to infer how information flows through the online media space. We find that the diffusion network of news tends to have a core-periphery structure with a small set of core media sites that diffuse information to the rest of the Web. These sites tend to have stable circles of influence with more general news media sites acting as connectors between them.

References

• 1. Supporting Website. Http://snap.stanford.edu/netinf.
• 2. Eytan Adar, Lada A. Adamic, Tracking Information Epidemics in Blogspace, Proceedings of the 2005 IEEE/WIC/ACM International Conference on Web Intelligence, p.207-214, September 19-22, 2005 doi:10.1109/WI.2005.151
• 3. .-L. Barabási. The Origin of Bursts and Heavy Tails in Human Dynamics. Nature, 435:207, 2005.
• 4. .-L. Barabási and R. Albert. Emergence of Scaling in Random Networks. Science, 286:509--512, 1999.
• 5. . Clauset, C. Moore, and M. E. J. Newman. Hierarchical Structure and the Prediction of Missing Links in Networks. Nature, 453(7191):98--101, 2008.
• 6. . Crane and D. Sornette. Robust Dynamic Classes Revealed by Measuring the Response Function of a Social System. Proceedings of the National Academy of Sciences, 105(41):15649--15653, October 2008.
• 7. . Edmonds. Optimum Branchings. Journal of Resesearch of the National Bureau of Standards, (71B):233--240, 1967.
• 8. . Erd\Hos and A. Rényi. On the Evolution of Random Graphs. Publication of the Mathematical Institute of the Hungarian Academy of Science, 5:17--67, 1960.
• 9. . Friedman and D. Koller. Being Bayesian About Network Structure. A Bayesian Approach to Structure Discovery in Bayesian Networks. Machine Learning, 50(1):95--125, 2003.
• 10. . Friedman, I. Nachman, and D. Pe'er. Learning Bayesian Network Structure from Massive Datasets: The "Sparse Candidate" Algorithm. In: Proceedings. UAI, 1999.
• 11. Daniel Gruhl, R. Guha, David Liben-Nowell, Andrew Tomkins, Information Diffusion through Blogspace, Proceedings of the 13th International Conference on World Wide Web, May 17-20, 2004, New York, NY, USA doi:10.1145/988672.988739
• 12. . Katz and P. Lazarsfeld. Personal Influence: The Part Played by People in the Flow of Mass Communications. Free Press, 1955.
• 13. David Kempe, Jon Kleinberg, Éva Tardos, Maximizing the Spread of Influence through a Social Network, Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, August 24-27, 2003, Washington, D.C. doi:10.1145/956750.956769
• 14. Samir Khuller, Anna Moss, Joseph (Seffi) Naor, The Budgeted Maximum Coverage Problem, Information Processing Letters, v.70 n.1, p.39-45, April 01, 1999 doi:10.1016/S0020-0190(99)00031-9
• 15. . Knuth. The Art of Computer Programming. Addison-Wesley, 1968.
• 16. Ravi Kumar, Jasmine Novak, Prabhakar Raghavan, Andrew Tomkins, Structure and Evolution of Blogspace, Communications of the ACM, v.47 n.12, December 2004 doi:10.1145/1035134.1035162
• 17. Jure Leskovec, Lada A. Adamic, Bernardo A. Huberman, The Dynamics of Viral Marketing, Proceedings of the 7th ACM Conference on Electronic Commerce, p.228-237, June 11-15, 2006, Ann Arbor, Michigan, USA doi:10.1145/1134707.1134732
• 18. Jure Leskovec, Lars Backstrom, Jon Kleinberg, Meme-tracking and the Dynamics of the News Cycle, Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, June 28-July 01, 2009, Paris, France doi:10.1145/1557019.1557077
• 19. Jure Leskovec, Christos Faloutsos, Scalable Modeling of Real Graphs Using Kronecker Multiplication, Proceedings of the 24th International Conference on Machine Learning, p.497-504, June 20-24, 2007, Corvalis, Oregon doi:10.1145/1273496.1273559
• 20. Jure Leskovec, Jon Kleinberg, Christos Faloutsos, Graphs over Time: Densification Laws, Shrinking Diameters and Possible Explanations, Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery in Data Mining, August 21-24, 2005, Chicago, Illinois, USA doi:10.1145/1081870.1081893
• 21. Jure Leskovec, Andreas Krause, Carlos Guestrin, Christos Faloutsos, Jeanne VanBriesen, Natalie Glance, Cost-effective Outbreak Detection in Networks, Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, August 12-15, 2007, San Jose, California, USA doi:10.1145/1281192.1281239
• 22. Jure Leskovec, Kevin J. Lang, Anirban Dasgupta, Michael W. Mahoney, Statistical Properties of Community Structure in Large Social and Information Networks, Proceeding of the 17th International Conference on World Wide Web, April 21-25, 2008, Beijing, China doi:10.1145/1367497.1367591
• 23. . Leskovec, M. McGlohon, C. Faloutsos, N. Glance, and M. Hurst. Cascading Behavior in Large Blog Graphs. In SDM '07: Proceedings of the SIAM Conference on Data Mining, 2007.
• 24. . Leskovec, A. Singh, and J. M. Kleinberg. Patterns of Influence in a Recommendation Network. In PAKDD '06: Proceedings of the 10th Pacific-Asia Conference on Knowledge Discovery and Data Mining, Pages 380--389, 2006.
• 25. . Liben-Nowell and J. Kleinberg. Tracing the Flow of Information on a Global Scale Using Internet Chain-letter Data. Proceedings of the National Academy of Sciences, 105(12):4633--4638, 25 Mar. 2008.
• 26. . D. Malmgren, D. B. Stouffer, A. E. Motter, and L. A. A. N. Amaral. A Poissonian Explanation for Heavy Tails in E-mail Communication. Proceedings of the National Academy of Sciences, 105(47):18153--18158, November 2008.
• 27. . Nemhauser, L. Wolsey, and M. Fisher. An Analysis of Approximations for Maximizing Submodular Set Functions. Mathematical Programming, 14(1):265--294, 1978.
• 28. . M. Rogers. Diffusion of Innovations. Free Press, New York, Fourth Edition, 1995.
• 29. . Wallinga and P. Teunis. Different Epidemic Curves for Severe Acute Respiratory Syndrome Reveal Similar Impacts of Control Measures. American Journal of Epidemiology, 160(6):509--516, 2004.
• 30. . J. Watts and P. S. Dodds. Influentials, Networks, and Public Opinion Formation. Journal of Consumer Research, 34(4):441--458, December 2007.

}},

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2010 InferringNetworksofDiffusionand	Jure Leskovec Andreas Krause Manuel Gomez Rodriguez			Inferring Networks of Diffusion and Influence		KDD-2010 Proceedings		10.1145/1835804.1835933		2010