Jure kdd09

Citation

Jure Leskovec, Lars Backstrom, Jon M. Kleinberg: Meme-tracking and the dynamics of the news cycle. KDD 2009: 497-506.

Online version

[1]

Summary

This is a highly cited KDD paper presenting an unsupervised approach to Temporal information extraction. Specifically it introduces a framework for tracking topic shifts in news and events, over short time scales.

The key idea is to track news by short, distinctive phrase, which acts as the analogue of "genetic signatures" for different topics. It also produces quantitative analysis of the news cycle on their large-scale and relatively representative news data set.

Method

Some words alternation in a phrase during the quotation (called textual mutation) could inhibit the accurate tracking. To solve this problem, the authors propose a robust method to cluster textual variants of quotes consisting of two stages namely phrase graph construction and clustering.

Pre-processing

First of all, pre-processing is conducted to eliminate the noisy phrases within the data set including:

1. remove the phrases whose word-length is less than 4.

2. remove the phrases whose term-frequency is less than 10.

3. eliminate the phrases whose domain-frequency is at least 25% (avoid spammers).

Graph construction

Each node $p$ in the phrase graph $G$ represents a phrase extracted from the corpus. An edge $(p,q)$ is included for every pair of phrases p and q, which always points from shorter phrases to longer phrases. Two phrases are connected either the edit-distance (treating a word as a token) is smaller than 1 or there is at least a 10-word consecutive overlap between them. In other words, the edge implies the inclusion relation between the phrases and since the direction is strictly pointing to longer phrases the graph becomes a directed acyclic graph (DAG).

The authors fail to elaborate how the weight $w_{pq}$ on each edge is calculated. They only state that the weight is increased as the directed edit distance as well as the frequency of q grows.

Clustering

The goal of Clustering is to retrieve all single rooted components so that all phrases in a component are closely related by deleting a set of edges of minimum total weight. The single rooted indicates a directed acyclic sub-graph if it contains exactly one root node (out-degree = 0). As other clustering problem, it proves to be a NP-hard problem. Therefore the authors propose three heuristic towards a feasible clustering solution. And the authors claim using the heuristic (although, in my opinion , the contribution of the heuristic is obscure) they found that keeping an edge to the shortest phrase yields 9% improvement over the baseline, 12% improvement keeping an edge to the most frequent phrases and 13% greedily assigning the node to the cluster with the most edges(Hill Climbing). The experimental result (Network Structure Analysis) demonstrates that the volume distribution for both phrase (solid blue) and phrase cluster (dashed green) generated by their cluster method follows power law distribution .

Data set

90 million news and blog articles 390GB collected over the final three months of the 2008 U.S. Presidential Election (from August 1 to October 31 2008).

Experimental Result

Based on the 35,800 non-trivial clusters (at least two phrases), the author extracted 50 largest threads which can be regarded as the cluster of the cluster containing some phrases and the threads are depicted in the following famous figure.

From the above figure we can not only obtain a clue about the news cycle but also get an idea about the popular news in each period. In addition, the authors also conclude their findings by global analysis and local analysis.

Global Analysis

The authors compare the dynamics of news threads to the follicular development within an ecosystem and claims two ingredients affecting the dynamics: imitation (different sources imitate one another) and recency (up-to-date news are always favored to old ones). Based on the idea, the authors propose a generation model based on the famous preferential attachment model (BA model). At each discrete time step $t=1,2,3...$, a source chooses thread j with probability proportional to $f(n_{j})\delta (t-t_{j})$, where $f(\cdot )$ is a monotonically increasing function and $n_{j}$ denotes the #stories about thread j; $\delta (\cdot )$ is a monotonically decreasing function and $t_{j}$ is the first time j was proposed. Intuitively the attachment is governed by the two factors and is preferential to "richer threads" (imitation) and the novelty of the threads (recency).

An interesting theoretical property of the dynamics is that:

Suppose we focus on thread j and let $X(t)$ be the thread's volume at time t and $t_{j}=0$ then we have:

$X(t+1)=cf(X(t))delta(t)$

Subtracting X(t) and dividing $\delta (t)$ on both sides we have:

${\frac {X(t+1)-X(t)}{\delta (t)}}={\frac {dX}{d\delta }}=cf(X(t))-{\frac {X(t)}{\delta (t)}}$ which is essentially an differential equation. For certain $f(\cdot )$ and $\delta (\cdot )$ we can obtain closed form for X.

Local Analysis

The authors find some interesting observations through local analysis:

1. News stories will gradually diffused to Blog after its cycle.

2. Quotes can migrate from blogs to news media

3. Different sites have different respond time for a phrase.

Notes

[2] Support website

[3] J. Leskovec, M. McGlohon, C. Faloutsos, N. Glance, M. Hurst. Cascading behavior in large blog graphs.SDM’07.

[4] X. Wang and A. McCallum. Topics over time: a non-markov continuous-time model of topical trends.Proc. KDD, 2006.

[5] X. Wang, C. Zhai, X. Hu, R. Sproat. Mining correlated bursty topic patterns from coordinated text streams.KDD, 2007.