郑昀 20100806
话说惠普有一个研究社会化网络数据挖掘的 Social Computing Lab（SCL） 实验室，领头的是 Bernardo Huberman 博士。
他们最近发布了一个研究报告《Influence and Passivity in Social Media》，基于250万用户的2200万 Tweets 数据。它的一个结论是：the correlation between popularity and influence is weaker than it might be expected，名气和影响力没什么关联，比人们期望的弱得多，High numbers of followers does not equal influence because those followers do not re-Tweet，名气和影响力是两码事，关注者多不等于有影响力，重要的是有多少人愿意转发你的消息。
最简单测量你的名气和影响力之间关系的是，发布一个能统计点击次数的短域名网址，看看到底有多少人从你的这条 Tweet 点击，别管你有多少万关注者，你是否有足够的影响力让人点击一个链接。
做PR或Ad的公司要注意这一点，想让微博客上的人帮你营销，不要只看他的 Followers/关注者/粉丝 数量，这数字没啥用，要精确测量他的真正影响力。
惠普的这个研究由于并不特定针对 Twitter ，所以它的结论也适用其他社会化网络。
加入了 Passivity 维度
大多数人都只是信息的消极接收者，他们并不会把东西转发到自己的网络里。为了让一个人有影响力，不应该仅仅停留在吸引别人的注意（眼球）从而变得有名上，还需要让用户克服他们的消极性(passivity)。
SCL 利用人在 Social Network 里的消极性，设计了一个影响力通用模型。它还开发了一个算法来量化网络中所有人的影响力，有点类似于HITS算法，综合考虑了网络的结构属性和用户之间的传播行为。
一个用户的影响力不仅依赖于他影响到的听众的多少，而且依赖于他们的消极性。
以前的影响力测量方法则主要基于一些个体的统计属性，比如关注者的数量，比如锐推(retweets)的数量。
SCL的这个算法有很好的预测能力，比如预测一个发布链接的点击次数上限会是多少。
SCL还发现那些高消极性的节点(node)，大多数都是垃圾制造者(spammers)或者机器人账户(robot users)。(注：不知道SCL如何评估@rtmeme这种机器人。)
实作
SCL 像锐推榜一样也是从Twitter Search API进去，查询包含 http 关键词的 Tweets ，试图收集齐提到链接的 Tweets(下称“链接推”)。历经300小时，获得了2200万条相关消息，其中1500万条的链接经过检查是有效格式。据他们评估，这2200万只是那个时间段内 Twitter 全部消息的十五分之一。
然后对这个集合中的用户，逐一通过 Twitter API 查询该用户的元数据，尤其是 followers/followings 的数量。
这样就得到了一个带着时间戳的 URL 集合，一个对应用户的完整的 Social Graph 。
user retweeting rate=用户A决定转发的URLs数量 / 用户A从他的 followings(他所关注的人)接收到的 URL 数量 。
audience retweeting rate=用户A发布的URLs中被 Followers(关注者)所转发的数量 / 用户A的一个 follower(关注者)从A这里所接收到的 URL 数量 。
很容易计算用户之间的 pairwise influence 关系，比如在 Twitter 里，要计算用户A对用户B的影响力，只需要统计B锐推A的次数即可。但你很难利用这种 pairwise influence 信息去计算一个用户(如@zhengyun)对整个网络的影响力。
SCL设计了 IP(Influence-Passivity) 算法，每一个用户都有一个 influence score 和 passivity score 。一个用户的 passivity 得分用来评估其他人想要影响到他有多难。
该算法有以下假设：
1、一个用户的 influence score 依赖于她所能影响的人数以及这些人的 passivity 。
2、一个用户的 influence score 还要考虑到，她所能影响的人专注程度(how dedicated)。
3、一个用户的 passivity score 依赖于这样一些人的影响力：她能接收到这些人的消息但却没有被影响到。
4、一个用户的 passivity score 还要考虑到，how much she rejects other user's influence compared to everyone else.
算法迭代计算 passivity 和 influence 得分，有点像 HITS算法 的寻找 Authority 页面以及指向它们的 Hub 页面。
给定一个加权有向图(weighted directed graph，也叫带权有向图) G = (N,E,W)，N是所有节点的集合(nodes)，E是弧的集合，W是权值。某条弧 e = (i,j) 的权值 Wij ，代表一个比率：i 对 j 的影响力 / i 试图施加在 j 上的全部影响力。
IP算法将这个 graph 作为输入。SCL 是这样构图的：
nodes是那些曾经发布过三条以上链接推的人。
如果用户 j 曾经至少锐推过用户 i 的链接推一条，那么弧arc (i,j)就存在。这条弧的权值计算公式为：Wij=Sij/Qi，其中，Sij是用户 i 发布的链接推中被用户 j 锐推的数量，Qi 是用户 i 发布的链接推数量。
最终计算时，SCL 的这个 graph 的节点数是 45万个，1百万条弧，平均权值是0.07。
在这个 graph 数据基础上，SCL 计算了 PageRank、Influence和Passivity 得分、Hirsch Index.
(注：H-index ，是一种评价学术成就的方法。一名科研人员的h指数是指他至多有h篇论文分别被引用了至少h次。h指数能够比较准确地反映一个人的学术成就。一个人的h指数越高，则表明他的论文影响力越大。例如，某人的h指数是20，这表示他已发表的论文中，每篇被引用了至少20次的论文总共有20篇。)
在 Twitter 里，一个用户的 H-index 是 h ，代表他的被人锐推了至少 h 次的链接推总共有 h 条。
（待续）