Information diffusion through blogspace

ABSTRACT

We study the dynamics of information propagation in environments of low-overhead personal publishing, using a large collection of weblogs over time as our example domain. We characterize and model this collection at two levels. First, we present a macroscopic characterization of topic propagation through our corpus, formalizing the notion of long-running "chatter" topics consisting recursively of "spike" topics generated by outside world events, or more rarely, by resonances within the community. Second, we present a microscopic characterization of propagation from individual to individual, drawing on the theory of infectious diseases to model the flow. We propose, validate, and employ an algorithm to induce the underlying propagation network from a sequence of posts, and report on the results.

REFERENCES

• 1: Rakesh Agrawal , Ramakrishnan Srikant, Mining Sequential Patterns, Proceedings of the Eleventh International Conference on Data Engineering, p.3-14, March 06-10, 1995
• 2: Reka Albert, Hawoong Jeong, and Albert-Laszlo Barabasi. Error and attack tolerance of complex networks. Nature, 406, July 2000.
• 3: James Allan, Topic Detection and Tracking: Event-Based Information Organization, Kluwer Academic Publishers, Norwell, MA, 2002
• 4: Norman Bailey. The Mathematical Theory of Infectious Diseases and its Applications. Griffin, London, 2nd edition, 1975.
• 5: Venkatesh Bala and Sanjeev Goyal. A strategic analysis of network reliability. Review of Economic Design, 5:205--228, 2000.
• 6: Bela Bollabas and Oliver Riordan. Robustness and vulnerability of scale-free random graphs. Internet Mathematics, 1(1), 2003.
• 7: Daypop. http://www.daypop.com.
• 8: A. Dempster, N. Laird, and D. Rubin. Maximum likelihood from incomplete data via the EM algorithm. J. Royal Stat. Soc., 1977.
• 9: Jared Diamond. Guns, Germs, and Steel. Random House, 1997.
• 10: Victor M. Eguiluz and Konstantin Klemm. Epidemic threshold in structured scale-free networks. Physical Review Letters, 89, 2002. cond-mat/0205439.
• 11: Michelle Girvan, Duncan S. Callaway, M. E. J. Newman, and Steven H. Strogatz. A simple model of epidemics with pathogen mutation. Phys. Rev. E, 65(031915), 2002. nlin.CD/0105044.
• 12: Malcolm Gladwell. The Tipping Point: How little things can make a big difference. Little Brown & Co., 2000.
• 13: Jacob Goldenberg, Barak Libai, and Eitan Muller. Talk of the network: A complex systems look at the underlying process of word-of-mouth. Marketing Letters, 12(3):211--223, 2001.
• 14: Mark Granovetter. Threshold models of collective behavior. American Journal of Sociology, 83(6):1420--1443, 1987.
• 15: R. V. Guha and Rob McCool. TAP: A system for integrating web services into a global knowledge base.
• 16: Hans Haller and Sudipta Sarangi. Nash networks with heterogeneous agents. Working Paper Series E-2001-1, Virginia Tech, 2003.
• 17: 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]
• 18: Andrew King. The evolution of RSS. http://www.webreference.com/authoring/languages/xml/rss/1/.
• 19: Ravi Kumar , Jasmine Novak , Prabhakar Raghavan , Andrew Tomkins, On the bursty evolution of blogspace, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775233]
• 20: M. Mitzenmacher. A brief history of lognormal and power law distributions. In Allerton Comm. Control Comput., 2001.
• 21: Cristopher Moore and M. E. J. Newman. Epidemics and percolation in small-world networks. Phys. Rev. E, 61:5678--5682, 2000. cond-mat/9911492.
• 22: Stephen Morris. Contagion. Review of Economic Studies, 67, 2000.
• 23: M. E. J. Newman. The spread of epidemic disease on networks. Phys. Rev. E, 66(016128), 2002. cond-mat/0205009.
• 24: M. E. J. Newman, Stephanie Forrest, and Justin Balthrop. Email networks and the spread of computer viruses. Phys. Rev. E, 66(035101), 2002.
• 25: Romauldo Pasto-Satorras and Alessandro Vespignani. Epidemic spreading in scale-free networks. Phys. Rev. Letters, 86(14):3200--3203, April 2001.
• 26: Steven Strogatz, Sync: The Emerging Science of Spontaneous Order, Hyperion Press, 2003
• 27: Topic Detection and Tracking (TDT-2003). http://www.nist.gov/TDT.
• 28: D. Watts and S. Strogatz. Collective dynamics of 'small-world' networks. Nature, 393:440--442, 1998.
• 29: WebFountain. http://www.almaden.ibm.com/WebFountain/.
• 30: Fang Wu, Bernardo A. Huberman, Lada A. Adamic, and Joshua R. Tyler. Information flow in social groups. Manuscript, 2003.
• 31: H. Peyton Young. The diffusion of innovation in social networks. Sante Fe Institute Working Paper 02-04-018, 2002.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
  I.6 SIMULATION AND MODELING

  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES

General Terms:
Algorithms, Experimentation, Measurement, Theory

Keywords:
blogs, information propagation, memes, topic characterization, topic structure, viral propagation, viruses