CWYAlpha

Just another WordPress.com site

Thought this was cool: 围脖局部影响力计算example

leave a comment »


最近看了一篇SIGIR 09年的paper,介绍的是如何区分一个用户是expert还是spammer,其实也就是对用户的expertise进行排名。

文中讲到的算法spear,是基于HITS(Hypertext Induced Topic Search)算法改进的,是SPamming-resistant Expertise Analysis and Ranking的缩写。文中的实验数据是用delicious的数据。算法中做了两个基本的假设是

(1)Mutual reinforcement of user expertise and document quality

专家级的用户更加倾向于产生高质量的document,而高质量的document常常由高水平的用户tag

(2)Discoverers v.s. followers

专家级的用户往往是一个“发现者”,也就是说他们更加倾向于第一个bookmark和tag高质量的document,然后将这些好的document带入到用户社区中。这个好比高水平的学者。

spear算法将会给早期发现新信息的discovers更多的credit,具体多少credit将会由一个credit function 计算得到。

这幅图介绍了spear算法的具体实现,首先是根据数据集生成一个带权重邻接矩阵和两个分数向量,邻接矩阵中的元素a(i,j)表示第i个用户在第j个document上的credit score。两个向量分别表示用户的expertise score 和 document的quality score。这里score function 是一个可以自己定义的函数,要保证discovers的分数要高于后面followers的分数,但分数的差距又不能差太多。(具体的参数可以参考后面的文献)

然后通过几百次的迭代计算,就可以得到一个收敛的E和Q,也就对user expertise进行了排名。

由于这篇paper是为了证明他们的算法可行,所以不但用了从delicious.com爬下来的真实数据,并且根据user behavior做了六类仿真用户混在真实数据中,以检验算法的效果。

用在我们这里,计算围脖局部影响力的时候,就不必设置仿真用户了。只需要将同一个圈子里的若干users的围脖信息考虑进来做计算就可以了。在选择种子用户的时候,参考了@clickstone的这个结果(http://weibo.com/1641544424/eB2mq72b8ai)。从这个user列表中爬他们关注的user形成整个user圈子,同时爬下他们发布的围脖信息,(围脖的id和timestamp,这里如果是用户原创的围脖则记录该围脖id和该条围脖发布的timestamp;如果这条围脖是用户转发的,则记录被转发的这条原始围脖的id以及该用户转发这条围脖时的timestamp)这样的话,我拿到的数据格式就是(timestamp,userid,weiboid),这里围脖对应着paper中的webpage。然后用spear算法计算得到了下面的结果:

http://expertise.sinaapp.com/show.php

这里是top50的排名。大家可以对比一下一年前@clickstone的计算结果

http://weibo.com/1641544424/eB2mq72b8ai

参考文献(点我下载

1、Telling Experts from Spammers:Expertise Ranking in Folksonomies

2、SPEAR:Spamming-Resistant Expertise Analysis and Ranking in Collaborative Tagging Systems

from 阿俊的博客: http://somemory.com/myblog/?post=48

Written by cwyalpha

五月 22, 2012 在 3:09 上午

发表在 Uncategorized

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s

%d 博主赞过: