5 10 15 20 25 30 35 中国科技论文在线 http://www.paper.edu.cn 微博用户排名算法的研究 徐慧，施晓倩* （中国矿业大学（北京）机电与信息工程学院，北京 100083） 摘要：随着社交网站的发展，对于其数据的挖掘与分析已经成为一个热门领域。在微博中， 用户排名是单纯根据粉丝人数进行排列的。而这种方法并不公平，并且带给用户很大困扰。 针对这一问题，结合基于网页排名算法，提出了新的排名算法。以用户节点为有向边，成立 概率转移矩阵，计算用户 TrustRank 值。这种算法能有效减少垃圾用户对微博排名的影响， 来提高排名的公平性与准确性。 关键词：数据挖掘；TrustRank；微博；排名算法 中图分类号：TP311.5 Research of ranking algorithm on micro-blog users XV Hui, SHI Xiaoqian engineering,Beijing 100083) (China University of Mining and Technology (Beijing), College of information and electrical Abstract: With the development of social networking,data mining and analysis has become a hot area. In weibo, user ranking is simply according to the order of the number of fans. And this method is not fair, which gives users a lot trouble. In order to solve this problem, combining based on web page ranking algorithm,we propose a new ranking algorithm. It came to pass, user nodes as directed, probability transfer matrix, computing TrustRank value by the user. This algorithm can effectively reduce waste of spam' influence on weibo ranking, which improves the fairness and the accuracy of ranking. Key words: Data mining; TrustRank; Weib; Ranking algorithm 0 引言 随着互联网的发展，微博在人们生活中的地位越来越重要，微博用户急剧增多。随着微 博用户不断增加，它已经不仅仅是一个社交平台，更多情况下他被视为一个媒体。人们用它 来获得更多的信息 [1] 。与传统媒体相比较，微博传播其消息的途径主要通过添加关注来实现。 人们希望得到那个领域，或者某些人的信息，便去添加这些微博用户，成为他们的粉丝。这 些用户一旦被大多数人所关注，他们发布的消息将会被更多的人所看到，他们的影响力将增 大 [2] 。 人们为了快速找到某领域的权威用户，或者具有特定特征的用户时，会利用微博的搜索 功能。但是搜索结果往往不是令人满意，人们搜索到的用户鱼龙混杂，他一定的排名顺序呈 现给用户，但是这个排名有时并不能让用户找到希望的那个。往往出现很多用户利用较高的 排名谋取利益，有些用户利用微博进行营销，一些非法用户利用微博恶意宣扬不好的言论， 或者僵尸粉丝，水军的存在都会给微博用户搜索排名带来影响。 为了改善这种现象，本文突破传统的网页排名的使用场景，将微博间的关注看作网页间 作者简介：徐慧，女，副教授，中国矿业大学副教授，硕士生导师，毕业于中国矿业大学（北京），获工 学硕士学位，并任计算机科学与技术系副主任 研究方向：数据库与数据挖掘. E-mail: sunnyhebei@126.com - 1 - 

中国科技论文在线 http://www.paper.edu.cn 的连接，将 TrustRank 值引入微博用户搜索中。利用微博用户和网页内在关系上所具有的相 似性更好的解决搜索结果的用户排名。 40 本文将以新浪微博为例，展开论证。 1 TrustRank 算法描述 1.1 算法概述 TrustRank 算法是基于一个基本假设：好网站很少会链接到坏的网站上。相反则不成立， 也就是说坏的网站很少会链接到好网站上的这句话并不成立。正相反，很多作弊网站会链接 到高权威、高信任指数的网站，意图提高自己的信任指数 [3] 。 由此，我们也可以引出 TrustRank 在微博搜索中用户的排名上。我们利用 TrustRank 的 主要思想得出以下结论：一些权威的用户（好网站）很少会关注恶意的用户（坏网页），相 反，企图利用微博牟取利益的恶意用户却更愿意关注一些权威用户，以此提高他们的声誉。 基于这个假设，如果可能挑出百分之百的“好用户”，这些用户的 TrustRank 值评为最 高，这些 TrustRank 最高的用户所关注到的用户信任指数稍微降低，但是也会很高。与此类 似，第二层被信任的用户关注的第三层用户，信任度继续下降。当然，由于种种原因，好的 用户也会不可避免的关注到一些恶意用户，不过离第一层用户距离越近，传播信任指数越高， 离第一级用户距离越远，信任指数依次下降 [4] 。这样，通过 TrustRank 算法，就能给所有用 户计算出相应的信任指数，离第一层网站越远，成为垃圾网站的可能性就越大。 以新浪微博为例，大 V 用户，指的是在微博上十分活跃并拥有众多粉丝的公众人物， 通常把粉丝超过 50 万的微博用户称为网络大 V。大 V 必须在一个特定的微博平台上获得个 人认证，经过认证，其微博昵称后便会附一个“V”形图标。之所以称“V”，大 V 几乎都 是网络上的意见领袖，有着不容小觑的号召力和影响力。因此，大 V 务必维护好自己的形 象，不传播未经核实的信息，不能成为谣言的传播者，否则，大 V 就成了“大谣”。因此， 我们从大 V 用户里挑选我们的好用户 [5] 。 1.2 计算模型 算法操作一般是：首先人工选取种子节点，并赋予较高的 TrustRank 值，然后通过下列 公式迭代处理，如公式（2.1）： )( iTR = 1( − α ) ⋅ ∑ iINj )( ∈ ( )( jTR )( jout ) + α ⋅ TR )0( 其中，TR（i）为节点 i 的 TrustRank 值，IN（i）集合为链向节点 i 的其他节点，|out(j)| 为链出节点 j 的个数, α为衰减因子（一般为 0.15），TR(0)是节点 i 的初始信任值，一般 TR(0) 值会进行归一化处理。然后，经过多次迭代最终收敛，TrustRank 值较高的越不可能是作弊 页面。从公式容易看出，TrustRank 的信任值进行传播时采取的策略是衰减和分裂。从链接 （关注）的层次来看，如果距离种子用户越远，那么从种子用户获得到的信任值就会越小。 假如一个用户从种子用户集中的某一个的出链接获得到信任值为γ，那么该页面的出链接指 向的用户则可以从该页面获得γ×γ的信任值，这种方法称之为信任值的衰减(Trust dampening)。另一方面，TrustRank 算法在用户的信任值传播的时候则采用信任值的分配(Trust splitting)。该分配策略通常是按照某一页面的出链接数对信任值进行平均分配，例如某个信 45 50 55 60 65 70 - 2 - 

中国科技论文在线 http://www.paper.edu.cn 75 任用户仅关注一个用户，那么此链接所指向的用户就获得了较高的信任值；相反，如果该权 威用户关注了上百个用户，那么这些链接就会得到一个较低的信任值，这是由于如果某个用 户关注用户增多，那么其中的某一个就很有可能恶意用户。 2 算法设计 80 计算过程主要分两步，数据获取以及数据处理。我们首先需要通过新浪微博提供的 API[6] 85 90 采集用户数据，形成所需的计算矩阵，然后用应用 TrustRank 算法计算出 TR 值。 2.1 微博数据获取 新浪微博开放平台为开发者提供了丰富的微博 API，数据获取阶段主要调用这些 API。 在调用微博 API 之前，先要初始化两个用来存放用户 ID 的队列 P 和 Q ，队列 P 用来存放 需要遍历的用户 ID，队列 Q 用来存放已经遍历过的用户 ID，当队列 P 为空时，就进入到 数据处理阶段，非空时，就循环对队列 P 中用户 ID 进行遍历获取用户数据。 在此阶段中，主要需要用到有关用户关注、粉丝的 API。当队列 P 非空时，队头用户 ID 出列，通过 friendships /friends，friendships /followers 获取用户的关注列表和粉丝列表中 用户 ID，通过比较队列 Q ，若有不在队列 Q 中的用户 ID，则将其插入到队列 P 中，将用 户与关注用户和粉丝的关系存储到关系表 S ( 用户 1，用户 2，关系) 中，1 表示用户 1 关 注用户 2，0 表示用户 2 关注用户 1。 2.2 微博数据处理 在进行微博 PageRank 值之前，首先要初始化一个矩阵 A，将关系表 S 中的信息添加 95 到矩阵中，表示 a ij 与 j 的关系，1 表示 i 关注 j，0 则表示不关注。 根据微博的数据，需要对 TrustRank 算法重新定义。u 表示微博用户，I u 表示跟随用户 u 的粉丝集合，O u 表示用户 u 跟随的用户集合，则微博 TrustRank 值可以表示为: iTR )( = 1( − ) α ⋅ ∑ INj ∈ )u( ( TR out j )( j )( ) ⋅+ α TR )0( 有公式可知，用户的 TR 值由两方面组成，用户的初始 TR 值，以及经过迭代以后分到 100 种子用户的 TR 值。 设TrustRank 矩阵A，A 的成分 ija 可以表示为： a ij { = 1 0 i if j 跟随 i 不跟随 j if 105 如果用户总数为 N ，则这个矩阵就是一个 N × N 的方阵。但是重视的是用户被哪些 用户所关注，而不是着重用户关注哪些用户，并且存在某些悬垂用户，悬垂用户( dangling user) 指的是那些可能有很多人关注，但是本身却不是任何人的粉丝的用户。由于计算每个用户的 PageRank 值是通过求一个概率转移矩阵的唯一静态概率分布，这就需要该矩阵不可约且为 非周期的，另一个前提条件就是每个用户至少有一个跟随对象，不能出现某一行全为 0 的 情况。 解决这个问题的方法是：将这些悬垂用户从计算系统中移除，因为这些用户没有跟随对 - 3 - 

中国科技论文在线 http://www.paper.edu.cn 110 象，所以并不会影响整体 PageRank 的计算，只需要在 PageRank 值计算出来以后，再将这 些用户重新纳入进来即可，事实证明，那些被移除关系的用户的转移概率只会受到轻微的影 响。 写出这个实验的伪代码： 输入：Web 图 G，好种子集合信任向量 s， 输出：TrustRank 分数向量 t begin： st ← Repeat TrustRank 公式计算信任值向量 t until 收敛 Return t End 115 3 实验分析 本文实验平台配置如表 1： 操作系统 CPU 内存 硬盘 表 1 实验环境 Linux Ubuntu 11.10 操作系统 双核 Intel Core i3 2.10GHz 4G 500G 120 同时 PC 机上安装 JDK1.6+MyEclipse8.5 为开发环境，以 java 为开发语言进行程序的编 写。 文章通过新浪微博开放 API 获取了部分用户的相关数据信息。鉴于僵尸粉丝[]更多出现 在粉丝数目庞大的认证名人微博用户中，兼顾算法可行性与实验结果普遍性，我们选出三位 名人的粉丝作为实验数据，对我们的观点进行论述。我们通过比较新浪微博粉丝前 300 名中 僵尸粉丝比率，和用我们的算法的出来的值进行比较来分析实验。 我们选取三位具有代表性的三位微博用户：李开复，NBA，头条新闻 对于僵尸粉丝的判断，本实验采用以下方法： *已注销用户； *粉丝数少于 5； *微博数少于 5； 注：判断标准可能过于粗犷，但是无碍于得出定性的结论。 我们得到的实验结果如下表： - 4 - 125 130 135 

中国科技论文在线 http://www.paper.edu.cn 表 2 实验结果 新浪微博排名 本算法排名 李开复 17% 2.4% NBA 12% 1.3% 头条新闻 18% 0.5% 140 注： 表格中数字代表前 300 名粉丝所含僵尸粉丝比率 4 结论 本文文中针对微博单纯通过对比粉丝人数的排名，提出了一种新的根据粉丝重要性的排 名算法。将传统网页排名 TrustRank 的计算方法来计算微博用户的 TR 值，得到的结果比现 有的排名更具公平性。而实验结果也说明根据 TR 值的比较，微博排名会发生变化。然而， 由于单纯计算 TR 值［12］，并无法区分微博用户在各自领域的排名，也就是无法体现出用 户的主题相关性，并且只是单纯地考虑了用户之间的关注布尔型，而没有将用户关系进行量 化，这些都是以后研究的主要工作内容。 5 致谢 145 150 在本文结束时，我特想给予我帮助的朋友们表示真挚的感谢！ 首先要感谢的是我的导师徐慧老师，在研究初期，我也遇到过很多困惑，多亏许老师悉 心指导，耐心敦促，无论在论文的选题、创新点的选取，都给了很多指导，同时徐老师渊博 的专业知识、严谨的治学态度，精益求精的工作作风，诲人不倦的高尚师德，朴实无华、平 易近人的人格魅力对我的影响深远。 155 感谢宿舍兄弟和实验室的师兄师姐、师弟师妹，他们在生活和学习上给予我很多的帮助， 在此表示真诚的感谢。 感谢我的家人，特别是我的母亲，多年来对我的学业的支持和生活上的帮助，在未来的 日子里，我会更加努力的学习和工作，不辜负您对我的殷切期望! 160 最后，向所有帮助过我的人，道一声“谢谢！没有你们的支持与帮助我很难顺利完成我 的研究课题。” [参考文献] (References) 165 170 (2011,1,21) [2013,5,7]. of Milan,2007. [1] 余剑来． 社交网络化的发展方向［J］． 世界科学， 2011( 1) :59－60. [2] 李纲． Struts2 权威指南［M］． 北京: 电子工业出版社，2008． [3] Yahoo! Research. Web Spam Collections [DB/OL]. Crawled by the Laboratory of Web Algorithmics， University . research.yahoo.net/webspam/datasets/. [4] 贾志洋, 夏幼明, 高 炜, 等. 搜索引擎垃圾网页检测模型研究[J]. 重庆文理学院学报(自然科学版), 2011 年 10 月, 第 30 卷(第 5 期)：53-58. [5] 新浪. 个人认证[OL].[2013.07].http://verified.weibo.com/verify/help?fr=applystd&frpos=leftnav [6] Ling Zhang，Zheng Qin． The Improved Pagerank in Web Crawler［C].The 1st International Conference on Information Science and Engineering ICISE． Piscataway，N． J． : IEEE Press， 2009.1889－1891． http://law.dsi.unimi.it/. http://barcelona - 5 -