Identifying influential bloggers: WSDM 2008

Citation

Nitin Agarwal, Huan Liu, Lei Tang, Philip S. Yu, "Identifying the Influential Bloggers in a Community", Proceedings of the International Conference on Web Search and Web Data Mining (WSDM), 2008.

Online version

Available at Citesteer

Summary

This paper aims at identifying most influential bloggers in a blogging community. The paper first proposes some metric for assessing how influential a blog post is. Then the authors perform some experiments on blogs from few blog sites and qualitatively evaluate their results.

What makes a Blog influential

Recognition: An influential blog post is recognized by many, which can be judged by the number of in-links ($\iota$), i.e. the number of other posts referencing the particular post.
Activity Generation: A blog post that generates more activity is supposedly more influential. This is measured by the number of comments made on the blog post ($\gamma$).
Novelty: Novel ideas are supposed to be more influential [1]. A post that references more other posts (or has more out-links) is supposed to have lesser novel ideas. So novelty can be taken as negatively correlated with the number of out-links ($\theta$) Eloquence: More eloquent posts are more influential [1]. Authors use the length of the blog post ($\lambda$) as a measure of eloquence.

The Math behind this

Reader Measure

Given the full set of comments to a blog, the authors construct a directed reader graph $G_{R}:=(V_{R},E_{R})$. Each node $r_{a}\epsilon V_{R}$ is a reader, and an edge $e_{R}(r_{b},r_{a})\epsilon E_{R}$ exists if $r_{b}$ mentions $r_{a}$ in one of $r_{b}$’s comments. The weight on an edge, $W_{R}(r_{b},r_{a})$, is the ratio between the number of times $r_{b}$ mentions $r_{a}$ against all times $r_{b}$ mentions other readers (including $r_{a}$). The authors compute reader authority using a ranking algorithm, shown in Equation 1, where $|R|$ denotes the total number of readers of the blog, and d is the damping factor.

$A(r_{a})=d*1/|R|+(1-d)\Sigma W_{R}(r_{b},r_{a})*A(r_{b})............(1)$
$RM(w_{k})=\Sigma tf(w_{k},c_{i})*A(r_{a})...............................(2)$
The reader measure of a word $w_{k}$, denoted by $RM(w_{k})$, is given in Equation 2, where $tf(w_{k},c_{i})$ is the term frequency of word $w_{k}$ in comment $c_{i}$.

Quotation Measure

For the set of comments associated with each blog post, the authors construct a directed acyclic quotation graph $G_{Q}:=(V_{Q},E_{Q})$. Each node $c_{i}\epsilon V_{Q}$ is a comment, and an edge $(c_{j},c_{i})\epsilon E_{Q}$ indicates $c_{j}$ quoted sentences from $c_{i}$. The weight on an edge, $W_{Q}(c_{j},c_{i})$, is 1 over the number of comments that c_j ever quoted. The authors derive the quotation degree $D(c_{i})$ of a comment $c_{i}$ using Equation 3. A comment that is not quoted by any other comment receives a quotation degree of $1/|C|$ where $|C|$ is the number of comments associated with the given post. $D(c_{i})=1/|C|+\Sigma W_{Q}(c_{j},c_{i})*D(c_{j})...........(3)$
$Q_{M}(w_{k})=\Sigma tf(w_{k},c_{i})*D(c_{i})..................(4)$
The quotation measure of a word $w_{k}$, denoted by $QM(w_{k})$, is given in Equation 4. Word $w_{k}$ appears in comment $c_{i}$.

Topic Measure

Given the set of comments associated with each blog post, the authors group these comments into topic clusters using a Single-Pass Incremental Clustering algorithm presented in [1]. The authors conjecture that a hotly discussed topic has a large number of comments all close to the topic cluster centroid. Thus they propose Equation 5 to compute the importance of a topic cluster, where $|c_{i}|$ is the length of comment $c_{i}$ in number of words, $C$ is the set of comments, and $sim(c_{i},t_{u})$ is the cosine similarity between comment $c_{i}$ and the centroid of topic cluster $t_{u}$.

$T(t_{u})=1/\Sigma |c_{j}|*\Sigma |c_{i}|*sim(c_{i},t_{u})......................(5)$
$TM(w_{k})=\Sigma tf(w_{k},c_{i})*T(t_{u})......................................(6)$

Equation 6 defines the topic measure of a word $w_{k}$, denoted by $TM(w_{k})$. Comment $c_{i}$ is clustered into topic cluster $t_{u}$.

Overall Word Representativeness or Importance Score

The representativeness score of a word $Rep(w_{k})$ is the combination of reader-, quotation- and topic- measures in ReQuT model. The three measures are first normalized independently based on their corresponding maximum values and then combined linearly to derive $Rep(w_{k})$ using Equation 7. In this equation $\alpha$, $\beta$ and $\gamma$ are the coefficients (0 ≤ $\alpha$, $\beta$, $\gamma$ ≤ 1.0 and $\alpha$ + $\beta$ + $\gamma$ = 1.0).

$Rep(w_{k})=\alpha *RM(w_{k})+\beta *QM(w_{k})+\gamma *TM(w_{k}).......................(7)$

Sentence Selection Criteria

Density Based Selection: Based on representativeness score of keywords and the distance between two keywords in a sentence. In equation 8, K is the total number of keywords contained in i^th sentence $s_{i}$, $Score(w_{j})$ is the representativeness score of keyword $w_{j}$, and $distance(w_{j},w_{j}+1)$ is the number of non-keywords (including stopwords) between the two adjacent keywords $w_{j}$ and $w_{j}+1$ in $s_{i}$.

$Score(s_{i})=1/K*(K+1)*\Sigma Score(w_{j})*Score(w_{j+1})/distance(w_{j},w_{j+1})^{2}............................(8)$

Summation Based Selection: Based on the number of keywords contained in a sentence. In equation 9, $|s_{i}|$ is the length of sentence $s_{i}$ in number of words (including stopwords), and $tau$ ($tau$ > 0) is a parameter to flexibly control the contribution of a word’s representativeness score.

$Rep(s_{i})=1/|s_{i}|*(\Sigma Rep(w_{k})^{\tau })^{1/\tau }................................(9)$

Results

Two metrics were used: R-Precision and NDCG. NDCG is described in [2].

References

[1] D. Shen, Q. Yang, J.-T. Sun, and Z. Chen. Thread detection in dynamic text message streams. In Proc. of SIGIR ’06, pages 35–42, Seattle, Washington, 2006.
[2] K. Jrvelin and J. Keklinen. IR evaluation methods for retrieving highly relevant documents. In Proc. of SIGIR ’00, pages 41–48, Athens, Greece, 2000.