Source-linked AI summary
Cascading Behavior in Large Blog Graphs
Jure Leskovec, Mary McGlohon, Christos Faloutsos, Natalie Glance, Matthew Hurst
TL;DR
The paper examines temporal and topological patterns in blog-linking cascades to understand how information propagates through social networks. It analyzes blog and post networks, then develops a simple generative model that mimics observed real-cascade behavior, including power-law patterns.
Problem
The paper asks how information spreads through social networks and what temporal, structural, and size patterns characterize information cascades.
Method
The authors analyze blog and post networks, use an SIS-based topic-propagation framework, and develop a simple generative model for observed cascade properties.
Results
Post popularity declines with a power law of slope ≈-1.5, while cascade sizes follow a Zipfian power law with slope =-2 and stars are the most popular cascade shape.
Takeaways & Limitations
The analysis identifies recurring temporal and topological propagation patterns, and the proposed model mimics the behavior of real cascades.
Takeaways & Limitations
The model does not account for post topics or particular-blog influence, assumes a common β, and generates tree cascades from a single starting point.
Abstract
from arXiv · showhide
How do blogs cite and influence each other? How do such links evolve? Does the popularity of old blog posts drop exponentially with time? These are some of the questions that we address in this work. Our goal is to build a model that generates realistic cascades, so that it can help us with link prediction and outlier detection. Blogs (weblogs) have become an important medium of information because of their timely publication, ease of use, and wide availability. In fact, they often make headlines, by discussing and discovering evidence about political events and facts. Often blogs link to one another, creating a publicly available record of how information and influence spreads through an underlying social network. Aggregating links from several blog posts creates a directed graph which we analyze to discover the patterns of information propagation in blogspace, and thereby understand the underlying social network. Not only are blogs interesting on their own merit, but our analysis also sheds light on how rumors, viruses, and ideas propagate over social and computer networks. Here we report some surprising findings of the blog linking and information propagation structure, after we analyzed one of the largest available datasets, with 45,000 blogs and ~ 2.2 million blog-postings. Our analysis also sheds light on how rumors, viruses, and ideas propagate over social and computer networks. We also present a simple model that mimics the spread of information on the blogosphere, and produces information cascades very similar to those found in real life.
1 Introduction
The paper examines temporal and topological patterns in blog information propagation and develops a simple model that generates realistic cascades. It focuses on how popularity changes, how cascades are shaped and sized, and how these patterns can support practical analysis.
- The study asks whether blog traffic is bursty or periodic, whether post popularity declines linearly or exponentially, and how information cascades are structured.
- Post popularity declines with a power law rather than exponentially, with exponent approximately −1.5.
- Cascade sizes follow a Zipfian power law with slope −2, while stars are the most popular cascade shape.
- The proposed flu-like model produces cascades that match several power-law properties observed in real cascades.The model is intended to generate realistic cascades for link prediction, link-spam detection, and what-if scenarios.
2 Related work
The related work situates blog-link analysis within research on burstiness, power laws, information diffusion, cascades, and epidemiological modeling. The paper distinguishes its approach by analyzing observed link propagation directly.
- Prior research reports bursty behavior in disk accesses, network traffic, web-server traffic, web visits, and response times.
- Power-law distributions describe heavy-tailed network attributes and produce linear patterns on log-log plots, with Zipf distributions arising when γ = −2.
- Human activity exhibits daily, weekly, and yearly periodicities, sometimes combined with burstiness.
- Earlier blog studies inferred relationships using crawling, text analysis, blog-rolls, topics, or activation models, whereas this work concentrates on link propagation.
- Information cascades describe ideas or actions becoming widely adopted through influence, and the paper relates its propagation model to SIS epidemiological modeling.In SIS models, entities become susceptible, infected, infectious, and susceptible again; β denotes transmission probability.
3 Preliminaries
The paper represents blogspace with blog-level and post-level networks, then extracts time-ordered information cascades from the post network. It defines cascade shapes and connector nodes for describing propagation structure.
- The Blog network collapses post-to-post links into weighted directed edges between blogs, while the Post network preserves links among individual posts.
- Post-network edges are labeled by the time difference Δ = t_u − t_v, which is positive because posts cannot link into the future and self-edges are excluded.
- A cascade starts with an initiator having no out-links and expands through posts that link to existing cascade members in time order.
- Stars are wide, shallow cascades centered on one post, whereas chains are deep cascades formed by successive links.
- A connector node joins otherwise separate cascades, such as when one post summarizes topics or links to multiple independent sources.
4 Experimental setup
The study analyzes an activity-biased blog dataset collected from linked conversation trees and represents it as a cleaned cluster graph. Cleaning removes links unsuitable for temporal diffusion analysis.
- The sample is biased toward active blogs because the study targets blogs and posts participating in discussions.
- Researchers began with highly cited August posts and traversed conversation trees forward and backward, limiting tree depth to 100 and links followed per post to 500.
- The dataset contains 2,422,704 posts from 44,362 blogs collected between early August and late September 2005.
- Posts are nodes clustered by parent blog, and hyperlinks between dataset posts become directed edges after structural cleaning.
- The analysis uses one-day time resolution to reduce timezone effects and removes future-pointing and self edges that do not represent diffusion.
5 Observations, patterns and laws
The blogosphere shows strong temporal and structural regularities: link popularity declines by a power law after an initial peak, while blogs and cascades exhibit heavy-tailed, mostly tree-like organization.
- Temporal dynamics of posts and links: Weekend activity drops sharply, revealing a seven-day periodicity in blog posting and blog-to-blog linking.The analysis therefore accounts for weekly traffic patterns when measuring temporal influence.
- Temporal dynamics of posts and links: Most links to a post occur within its first 24 hours, after which popularity generally declines; apparent Monday spikes reflect lower intervening activity, not unusual Monday linking.The Monday pattern is a visual consequence of the weekly cycle combined with natural popularity decay.
- Blog network topology: Blog in- and out-degree distributions are heavy-tailed, but their correlation is only 0.16, so highly attended blogs are not necessarily highly active.The blog network contains 44,356 nodes and 122,153 edges, with half of the blogs isolated from the largest connected component.
- Blog network topology: The post network is sparse: 98% of its 2.2 million posts are isolated, while its in- and out-degree exponents are −2.1 and −2.9.Its largest connected component has 106,000 nodes, and the second largest has 153.
- Cascade shapes and sizes: Cascades are overwhelmingly trivial and preferentially wide and shallow: 97% are isolated posts, while stars and shallow bursty forms dominate non-trivial structures.The dataset contains 2,092,418 cascades; only 1.2% are topologically more complex, and most cascades can be built from stars and trees.
6 Proposed model and insights
The paper proposes a one-parameter flu-like cascade model and evaluates it against real blog cascades. The model reproduces popular cascade shapes and several size and degree distributions, while biased extensions produce overly large cascades.
- Cascade generation model: The model treats information spreading as a flu-like process over the Blog network, using a single parameter for conversation-wide ease of spreading.Blogs can recover and participate multiple times, but topics and blog-specific influence are not modeled.
- Cascade generation model: β = 0.025 gives each infected blog a 2.5% chance of spreading to an uninfected neighbor.The model generated approximately 2 million cascades and averaged 10 simulations with different random seeds.
- Validation of the model: Top 7 generated cascades match the real data exactly, except that G4 and G5 exchange ranks.The remaining generated top-10 cascades also appear in the real data.
- Validation of the model: The model matches cascade size and in-degree distributions well, with the best agreement for overall cascade sizes.Chains and stars are slightly under-represented in the high-variance tail, and an in-degree spike at 52 is attributed to outlier blogs.
- Model variants: Biased starting points and edge-weight-scaled spreading produce cascades that are too large and lose the heavy-tailed cascade-size distribution.Popular blogs lie in the network core, making large cascades easier to generate from those starting points.
7 Discussion
The discussion interprets the observed power-law decay and proposes conversation mass as an influence measure. It also contrasts cascade behavior across blogs with different initiating-post patterns.
- Temporal interpretation: Post popularity declines with a power law rather than the exponential decay suggested by forgetting intuition.The authors relate this heavy-tailed pattern to linking behavior across many individual instances.
- Influence measurement: Conversation mass may better measure influence than in-links because it counts the total posts in downstream conversation trees, not only direct responses.The metric sums conversation-tree posts below each point where the blogger contributed.
- Blog-specific cascade behavior: 85% of BoingBoing posts initiated cascades that were generally wide but shallow, whereas 53% of MichelleMalkin posts initiated deeper and generally larger cascades.The examples connect different initiating-post rates with distinct cascade shapes and sizes.
8 Conclusion
The paper analyzes temporal and topological patterns in blog information propagation and introduces a generative cascade model. Its model matches several properties of real cascades, while incorporating post content remains future work.
- Contributions: The study analyzes the Blog network and Post network to characterize temporal and topological patterns in blog information propagation.It reports findings from a large collection of blog information and presents a generative model of real cascades.
- Temporal patterns: The decline of post popularity follows a power law with slope ≈-1.5.This slope agrees with a theory of heavy tails in human behavior.
- Topological patterns: Cascade sizes, blog sizes, and in- and out-degrees generally follow power laws, while stars and chains form basic cascade components and stars are more common.The number of in- and out-links of a blog is not correlated.
- Generative model: The SIS-inspired generative model matches real cascades in in-degree distribution, cascade size distribution, and popular cascade shapes.The model treats influence propagation between blog posts as a flu-like virus.
- Future work: Including post content is identified as a future direction for finding more accurate patterns of influence propagation.The conclusion also suggests detecting anomalies and link spam through deviations from observed patterns.