本文对微博中常见的问题的对应算法进行了简单的介绍,在实际应用中的算法比介绍的要复杂的多。当然,本文覆盖的主题并不全,比如好友推荐、热点跟踪等没有涉及到。但古人云“窥一斑而见全豹”,希望本文的介绍能帮助大家更好的理解微博这样的社交网络应用。
  微博是一个很多人都在用的社交应用。天天刷微博的人每天都会进行着这样几个操作:原创、转发、回复、阅读、关注、@等。其中,前四个是针对短博文,后的关注和@则针对的是用户之间的关系,关注某个人意味着你成为他的粉丝,而他成为你的好友;@某个人意味着你想要他看到你的微博信息。
  微博被人们认为是“自媒体”,即普通大众分享与本身相关的“新闻”的途径。近,有些人使用自己在自媒体上的影响力而盈利的报道屡见不鲜。那微博上个人影响力是怎样计算的呢?微博上还有哪些算法作为看不见的手在管理着我们?我们的每一个行为怎样影响着算法呢?
  直观上看,微博其实是人类社会的一个简单的缩影,微博网络的一些特点,也许可以启发我们得到真实的社会网络上的规律。得益于社交网络的爆发式发展,“社会计算”尤其是社交网络分析成为数据挖掘的新宠儿。下面我们针对微博网络分析的一些算法进行简单的介绍,其中的有些算法对于其他的社交应用可能也适用。
  如果你对新浪微博的架构感兴趣,你也可以读读这篇文章:亿级用户下的新浪微博平台架构
  标签传播
  微博用户量浩大,不同的人有不同的兴趣。挖掘每个用户的兴趣有助于更加的广告投放、内容推荐。为了得到每个用户的兴趣,可以为用户打上标签,每个标签代表用户的一个兴趣,用户可以拥有一个或多个标签。为了得到终的用户标签,先做第一个假设:
  每个用户的好友(或粉丝)中与该用户具有相同兴趣的人占多数。
  这引出了本文介绍的第一个算法,即标签传播算法。在这个算法中,每个用户的标签取其好友或粉丝中标签多的一个或多个。当然,可以将好友和粉丝的标签都考虑进来,整合的时候可以考虑赋予好友的标签和粉丝的标签不同的权重。标签传播算法的过程如下:
  1)对一部分用户给出初始标签;
  2)对每一个用户,统计其好友和粉丝的标签数目,赋予该用户出现次数多的一个或者多个标签。
  3)循环进行第2步,直到用户的标签不再发生大的变化为止。
  用户相似度计算
  标签传播算法实现起来比较简单,其缺点在于当所做的假设不符合事实时,比如为了社交上的礼貌,我们一般会把自己的亲友添加关注,这些人不一定和我们拥有同样的标签;该算法的结果会变得很差。解决的办法是通过计算用户之间的相似度来衡量好友或粉丝的标签对用户标签的贡献率。因而得到第二个假设:
  与用户越相似的好友或粉丝,其标签越可能是用户的标签。
  那么,如何衡量用户之间的相似度呢?这需要考虑到用户发表的微博信息了,包括转发的和原创的。这里是要考虑用户之间的相似度而不是用户微博之间的相似度,因而在实际计算时,将某个用户的所有微博信息聚集到一起进行计算。一个可选的方法是使用词袋法将微博信息表示成词语向量,然后直接使用余弦方法等计算其相似度。但这个方法太过简单,不容易达到好的结果,这里介绍一种基于LDA(隐含狄利克雷分布)的相似度计算方法。
  LDA仍然使用词袋法表示文本,但是在中间添加了一个主题层,形成了“文档-主题-词语”三层概率模型,即每篇文档看成是主题的一种概率分布,主题又被看成是单词的概率分布。在LDA模型下,文档可以被看成按照如下方式生成:
  1)对于每篇文档:
  2)从主题分布中抽取一个主题;
  3)从该主题的词语分布中抽取一个词语;
  4)重复第2步和第3步,直到该文档的所有词语都生成。
  LDA模型参数的估计算法不在本文的讨论范围之内。这里只需要知道,通过LDA可以得到每个用户的微博信息的主题分布。然后使用余弦方法、KL距离等计算相似度的方法来得到用户间主题分布的相似度,以之作为用户之间的相似度。而后使用该相似度对标签传播进行加权。
  时间因素和网络因素
  上述的算法还有什么缺点呢?
  随着时间的变化,用户的兴趣是会变化的,计算用户相似度的时候每次都把所有微博信息都聚合在一起不太合理。对此,可以通过选取距离当前时间较近的N条微博。比如,对每个用户,选取距离当前时间近的50条微博聚在一起放到LDA中训练。此处的N既不能太大也不能太小。太大则不容易反映用户兴趣的时间变化,太小则由于用户发表微博的随机性容易引起兴趣的漂移。为了使效果好,可以不拘泥于一个固定的N,比如可以考虑对每个用户按照其发表微博的时间序列做N值的自适应。
  至此,在算法中还没有考虑微博关系中由回复、转发、@等所构成的网络信息。以转发为例,如果在用户的微博中频繁的转发某个好友的微博,那么用户和该好友的相似度相比其他好友来说应该会更高。这里可以看做是假设三:
  用户转发某好友的微博的频率越高,用户与该好友的兴趣相似度越大。
  相似的,可以得到假设四:
  用户微博中@某用户的频率越高,用户与该好友的兴趣相似度越大。
  由此得到了计算相似度的另外的因素。有很多方法可以添加一个新的因素到原有的相似度计算方法中,比如可以考虑将转发频率量化为值,作为权重添加到相似度的衡量中去。
  社区发现
  微博社区是指在微博中关系紧密的人组成的团体,社区内部的人之间联系紧密,社区之间的联系则比较稀疏。这里所指的关系紧密有两层含义,第一是社区内部的人之间的兴趣相似度大;第二是指社区内部的人之间的关系要近,比如要求社区内部的两个用户不能超过二度关联,二度关联即好友的好友。
  兴趣相似度在上文已有叙述,关系相似度则需要利用用户之间的关注关系来进行计算。以用户的关注关系为单向链,可以将所有的微博用户之间的关系表示为一个巨大的有向图。用户之间的关系相似度可以简单的考虑,比如使用用户间的短路径的倒数。但是这种方法衡量的不精确,我们知道,在现实世界中,存在着六度理论,在微博网络及其他社交网络中,往往关系会更加紧密。因而这种简单的关系相似度只能有至多六个离散值,显然不够精确。
  为了达到更好的效果,这里不仅以短路径作为显式量度,还要考虑一些隐式的量度。这里先给出两个假设,分别为假设五和假设六:
  两个用户的共同好友越多,这两个好友的关系相似度越高。
  两个用户的共同粉丝越多,这两个好友的关系相似度越高。
  这里可以借鉴Jaccard相似度的计算方式,将这两种假设的量化函数表示为交集的大小与并集的大小之商。以假设五为例,其量化指标又被称为共指向性相似度,量化时使用两个用户共同好友的数目除以两个用户所有好友的数目。假设六的量化指标被称为共被指向性相似度,计算方式与共指向性相似度类似。从意义上讲,这两种相似度不仅仅是关系上的度量,在一定程度上也衡量了用户之间的兴趣相似程度,直观上看,两个用户共同关注的好友越多,他们的兴趣相似程度也越大。这两种相似度还有一个专业的名字,是基于结构情景的相似度计算。
  得到了短路径相似度、共指向性相似度、共被指向性相似度后,可以采用一种加权函数将它们融合起来,得到后的相似度。之后,可以采用一些聚类算法如K-Means、DBSCAN等进行聚类操作,得到后的社区簇。也可以采用相似度加权的标签传播算法,把具有相同标签的人作为一个社区。