谈谈新浪微博背后的那些算法
作者:网络转载 发布时间:[ 2015/4/10 17:09:34 ] 推荐标签:算法 新浪微博
影响力计算
在社区发现中,使用微博中的关系网络可以提高相似度计算的精确度。但关系网络能做的事情还有很多,影响力计算便是其中比较重要的应用。
说到影响力的计算,这里借鉴了网页排名中的算法。网页排名中广为人知的算法当属PageRank了,该算法由google创始人拉里·佩奇和谢尔盖·布林发明,随着google在商业上的成功而声名鹊起。该算法根据网页之间的链接来确定网页的排名,其核心在于一个假设,质量高的网页所指向的网页的质量必定也高。
根据PageRank的思想,可以得到微博上影响力的假设,称之为假设七:
影响力高的用户关注的用户的影响力必定也高。
将用户看成是PageRank中的网页,将关注关系看做是网页中的链接关系。从而,可以根据PageRank的算法流程得到在微博关注网络上的影响力计算算法:
1)赋予所有用户相同的影响力权重;
2)将每个用户的影响力权重按照其关注的人数等量分配;
3)对每个用户来说,其影响力等于其粉丝分配给他的权重之和;
4)第2步和第3步迭代,直到权重不再发生大的变化为止。
在网页排名中,基于网络关系的算法还有HITS、HillTop算法等,这些算法也可以借鉴到影响力计算中来。
上面的算法有什么缺点呢?
如果只是基于关系网络的话,那么很容易造成,粉丝数目多的人影响力必然会很高。这样导致有些用户去购买一些僵尸粉可以达到很高的影响力了。这样的算法显然是不能应对实际情况的,因为还有太多的信息没有用到。
用户的影响力除了他的微博关系之外,还与他的个人属性有很大的关系,比如用户的活跃度、微文的质量等。用户的活跃度可以使用其发表微博的频度来衡量,微文的质量可以采用其被转发的数目、被回复的数目来得到。通过对这些值进行衡量,再加上上面算法的结果,可以得到更加精确的影响力结果。
当然,也可以这样考虑,用户之间的回复关系、转发关系、@关系均可以构成网络,它们也有相应的假设,分别为假设八、假设九、假设十:
影响力越高的用户回复的微博的影响力越高,从而使该微博主人的影响力变高。
影响力越高的用户转发的微博的影响力越高,从而使该微博原创作者的影响力变高。
影响力越高的用户倾向于在其微博中@影响力高的用户。
这样又得到了转发网络、回复网络、@网络三种网络,借鉴PageRank算法,可以得到另外的三种影响力结果。将它们与关系网络的影响力结果进行融合,可以终的影响力结果了。这里的融合可以简单的考虑成结果的加权和,复杂的融合方法不在本文的范围之内。
话题因素和领域因素
得到了影响力的计算方法之后,可以做些什么呢?
可以对当前的热点话题进行影响力分析,得到谁在微博上成为当前热点话题的意见。具体做法是这样,找到和当前热点话题相关的微文,从而找到参与当前热点话题的用户。如何找到和当前热点话题相关的微文呢?有话题标签的微文自不必说,对于没有话题标签的微文来说,可以使用上文中介绍的LDA算法,它可以在用户的所有微文中找到用户的主题分布,也可以对一条微文找到主题分布,一般来说,由于微文的字数限制在140以内,比较短,因而一条微文包含的主题数目不会太多,取该微文的主题分布中概率高的主题当做其主题即可。
找到话题对应的微文与用户之后,运行影响力计算算法,可以得到该话题中影响力较大的用户了。这也是舆情监测、社会热点监控的一个方面。
对于标签传播算法得到的结果,对同一标签下的用户运行影响力计算算法,可以得到该标签下的影响力排名,即领域内影响力排名。比如,李开复在全部领域内的影响力或许不是高的,但在IT领域,其影响力是数一数二的。
垃圾用户识别
在影响力计算中,提到要避免僵尸用户对影响力计算的干扰。在算法中,如果可以识别这样的用户,在计算影响力时将其排出在外,不仅可以提高效果,还可以降低计算量。
与影响力计算相似,垃圾用户的识别要同时考虑用户属性与链接关系两方面的因素。
对于垃圾用户来说,有一些统计上的特征与正常用户不同。比如如下几点:
垃圾用户一般发微文具有一定的时间规律性,可以使用熵值对此进行衡量,熵是衡量随机性的一种量度,随机性越大,熵值越小。具体做法为将一定的粒度进行时间切片统计,得到每个时间片内的博文概率,然后依照概率进行熵值的计算。熵值越大代表用户发微文的时间越有规律,越有可能是垃圾用户。
垃圾用户有些倾向于在微文中恶意的@其他人,因而有些垃圾用户的微文中@使用的比例比一般用户高。
有些垃圾用户的微文中为了进行广告的推广,添加大量的URL。可以通过微文中的URL比例进行衡量。也有些用户为了骗取URL的点击,微文中的内容与URL对应界面的内容不一致,这时需要判断微文与URL内容的一致程度,简单的做法可以使用词袋法将微文与URL对应界面表示成词语向量,查看微文中的词语在URL对应网页中出现的频度。
对于那些为做广告推销的用户,还可以对其微文进行文本分类,判断其微文是否是广告,如果某用户的相当一部分微文是广告,则该用户可能是垃圾用户。
垃圾用户一般随意的关注用户,故其粉丝数目与好友数目的比例与正常用户会有差别。而且正常用户一般是通过好友关系添加好友的,这样会形成关注三角形,如A看到其好友B关注了C,那么若A也去关注C,形成了A关注B、C,B关注C的三角形。一般来说,由于垃圾用户关注的随意性,其关注三角形的比例与正常用户不同。
当然,垃圾用户与正常用户的不同之处不止这些,本文不再一一枚举。垃圾用户的识别本质上是一个二分类问题,获得了这些属性之后,可以将这些信息输入到一个机器学习的分类模型中,比如逻辑斯蒂回归(LR)、决策树、朴素贝叶斯等,可以对其进行分类了。
当然,还没有用到链接信息。一般来说,垃圾用户会去关注正常用户,而正常用户不会关注垃圾用户。这即是假设十一:
正常用户不倾向于关注垃圾用户。
这样可以再次使用PageRank算法来对用户是否是垃圾用户的概率进行计算。这里需要注意的是,算法初始化时采用上面的分类器结果,将垃圾用户的概率设为1,正常用户的概率设为0。在PageRank计算过程中,不能通过简单的求和公式计算,比如如果一个用户关注了多个垃圾用户的时候,求和后概率可能大于1;因而需要使用一些归一化方法或指数族函数进行概率的更新。
结语
本文对微博中常见的问题的对应算法进行了简单的介绍,在实际应用中的算法比介绍的要复杂的多。当然,本文覆盖的主题并不全,比如好友推荐、热点跟踪等没有涉及到。但古人云“窥一斑而见全豹”,希望本文的介绍能帮助大家更好的理解微博这样的社交网络应用。
在文中,可以看到黑体标出的假设,这些假设看起来都与我们的直观感觉一致。而根据这些可以引申出很多有效的算法。所以有时候,只要你肯发现,算法在身边。
本文内容不用于商业目的,如涉及知识产权问题,请权利人联系SPASVO小编(021-61079698-8054),我们将立即处理,马上删除。
相关推荐
更新发布
功能测试和接口测试的区别
2023/3/23 14:23:39如何写好测试用例文档
2023/3/22 16:17:39常用的选择回归测试的方式有哪些?
2022/6/14 16:14:27测试流程中需要重点把关几个过程?
2021/10/18 15:37:44性能测试的七种方法
2021/9/17 15:19:29全链路压测优化思路
2021/9/14 15:42:25性能测试流程浅谈
2021/5/28 17:25:47常见的APP性能测试指标
2021/5/8 17:01:11热门文章
常见的移动App Bug??崩溃的测试用例设计如何用Jmeter做压力测试QC使用说明APP压力测试入门教程移动app测试中的主要问题jenkins+testng+ant+webdriver持续集成测试使用JMeter进行HTTP负载测试Selenium 2.0 WebDriver 使用指南