基于粒子群算法的微博用户影响力研究

基于粒子群算法的微博用户影响力研究 分类号 学号 M201072295 学校代码 10487 密级 硕士学位 基于粒子群算法的微博用户影响力 研究 学位申请人: 钟 帅 学科专业: 计算机技术 指导教师: 文坤梅 博士 答辩日期: A Dissertation Submitted in Partial Fulfillment of the Requirements for the Degree of Master of Engineering Research on microblog user influence based on particle swarm optimization Candidate : Zhong Shuai Major : ComputerTechnology Supervisor : Dr. Kunmei Wen Huazhong University of Science & Technology Wuhan 430074, P. R. China May, 2012 独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的 研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已 在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名: 日期: 年 月 日 学位论文版权使用 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即:学校有权保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本 人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密?， 在 年解密后适用本授权书。 本论文属于 不保密?。 (请在以上方框内打“?”) 学位论文作者签名: 指导教师签名: 日期: 年 月 日 日期: 年 月 华 中 科 技 大 学 硕 士 学 位 论 文 摘 要 微博作为 Web2.0 时代一种新兴的社会网络平台，以其参与的低门槛，发布信息的 实时性以及社交性，迅速成为风靡全球的网络平台。对微博用户影响力的研究可以帮 助用户找到有价值的信息源，从而减少用户过滤信息的时间，提高用户效率。对用户 影响力的研究对公共传播与病毒营销也非常重要。 传统的微博用户影响力研究都是从复杂网络着手。影响用户影响力的因素有用户 行为和用户关系等。对微博用户的行为模式进行，可知其具有的特点与群体智能 的五项原则是一致的。 本文尝试基于群体智能对微博用户行为进行分析，改进粒子群算法以适应用户影 响力的计算。粒子群算法是一种以群体智能为基础的随机搜索优化算法。该算法利用 个体在社群间的信息交流来寻找最优解。相比其它群体智能算法，粒子群算法更容易 理解，参数更少且容易实现。粒子群算法也是以生物社会背景为基础的。通过将用户 的转发行为描述成该用户在影响力空间中的变量部分，这个部分包含有用户自身经验 以及周围网络对该用户的影响。根据上述分析对粒子群算法做出一定改进，该算法将 上述变量部分当作粒子群中的速度变化，对一段时间内的用户进行迭代计算，最后依 据该计算结果得到用户的影响力。 以新浪微博为数据集对提出的方法进行实验验证，最终的实验结果表明 基于粒子 群算法的用户影响力计算方法能够有效地找出影响力较高的用户。 关键词:用户影响力;粒子群算法;社会网络;新浪微博 I 华 中 科 技 大 学 硕 士 学 位 论 文 ABSTRACT As a new type of social network in Web 2.0 era, microblog becomes very popular because of its low threshold for participation, real time to publish information and sociability. Research on microblog user influence is useful for user to find some valuable information source, thereby improve user ’s efficiency on filtering information. This research is also important on public dissemination and viral marketing. Most traditional measures of calculating user influence are based on the theory of complex networks. There have some factors to determine user ’s influence like user behaviors and user relations. Particle swarm optimization PSO is a stochastic optimization algorithm based on swarm intelligence. The algorithm applies the concept of social interaction to find optimal solution. Microblog Users participate in network interact by publishing tweets and retweeting. The influences of microblog users are determined by the users’ behaviors, which exactly match the five principles of swarm intelligence. Therefore, this paper proposes an improved PSO algorithm to find the microblog users with the imum influence. Microblog users’ retweeting behaviors can be described as a variable of the user influence space, which contains user experiences and surrounding network. The variable is defined as the velocity change in our method. By iteratively calculating based on users’ behavior, the imum influence will be obtained. The experiments validate that our method can effectively identify the high- influence microblog users. Key words :Influence, Particle swarm optimization, Social network, Sina Weibo II 华 中 科 技 大 学 硕 士 学 位 论 文 目 录 摘 要 ................................................ I ABSTRACT ............................................. II 目 录.............................................. III 1. 概述 1.1 研究背景和意义 ....................................... 1 1.2 国内外研究现状....................................... 3 1.3 主要研究内容......................................... 9 1.4 论文的结构安排 ....................................... 9 2. 影响力分析概述 2.1 影响力分析的统计方法 ................................ 10 2.2 影响力与社会相似性 .................................. 13 2.3 影响力相关研究热点 .................................. 17 2.4 本章小结............................................ 17 3. 基于粒子群算法的用户影响力分析 3.1 标准粒子群优化算法................................... 19 3.2 改进的粒子群优化算法 ................................ 22 3.3 本章小结............................................ 30 4. 实验结果以及分析 4.1 实验数据集.......................................... 32 4.2 实验数据分析........................................ 32 III 华 中 科 技 大 学 硕 士 学 位 论 文 4.3 本章小结............................................ 38 5. 总结与展望 5.1 本文总结............................................ 40 5.2 展望 ............................................... 41 致谢 ................................................... 42 参考文献 ............................................... 44 附录 1 攻读硕士学位期间取得的研究成果.................... 50 IV 华 中 科 技 大 学 硕 士 学 位 论 文 1. 概述 随着互联网的发展，微博作为 WEB2.0 时代一种新兴的社会网络平台， 以其参与的 低门槛，发布信息的实时性以及社会网络共有的社会性，迅速成为风靡全球 的网络平 台。基于微博的在线社会网络研究也成为研究热点。 1.1 研究背景和意义 随着WEB 2.0 的兴起，博客、微博、社会网络、RSS、社会标注、维基百科等网站 应用系统蓬勃发展。相较于传统网络平台以应用为中心简单地提供资源， WEB2.0 时代 更注重用户与平台之间的交互以及用户与用户之间的互动。用户更加主动地参与其中， 与平台以及用户互相交流。网站系统转移到以用户为中心，提供更加个性化的平台， 为用户发现、分享和创造资源。社会网络的模式更有利于信息的聚合、传播和利用， 加速了资源的产生和消费。用户在网络社会中的相互交流日益频繁，虚拟网络社会中 人与人之间的距离在缩小，人与人之间的关系变得更加密切。 社会网络作为一种典型的复杂网络[1-3] ，主要研究人与人之间的关系。它指的是一 种社会个体之间因为互动与交流而建立关系，整个社会关系体系时刻存在变化但保持 相对稳定，主要研究的是个体与个体之间的互动和联系以及个体的社会行为之间的相 互影响。在现实生活中，社会网络的形成更多的是因为地理因素， 比如亲戚一般生活 在同一地区、邻居、同事和朋友一般也生活在同一地区。他们一般具有相同的价值观、 态度、抱负并且高度紧密联系在一起。网络的高速发展加速了人与人之间的交流，促 进了以往因地理距离而无法交流的人们之间的联系。WEB 2.0 也更加注重提供基础交互 平台，鼓励用户交流，从而在网络世界中基于用户之间的互相交流形成了一个虚拟的 社会网络，即在线社会网络。现实的社会关系因人与人之间面对面的交流而固定，在 1 华 中 科 技 大 学 硕 士 学 位 论 文 线社会关系的交流可能因单一兴趣或某次活动产生，也容易消失。在社会网络因用户 活跃、参与人数多而联系频繁、互动多且动态变化大。特别是以微博为代表的在线社 会网络的快速发展直接改变了们的网络行为和交流范围。资源的传播和分享也更加快 速便捷，信息的获取途径也更加广阔。在线用户的行为、联系以及社区结构的发现形 成了新的研究领域。 现实生活中获取社会网络数据的手段主要是依靠人工完成。这样获取数 据不仅费 时费力，而且因人工主观因素的干扰使得数据的噪音较大。而在线社会网络数据的获 取可以通过爬虫获取，不仅用户量大，而且包含用户基本信息和用户行为信息。这为 社会网络研究取得更全面具体的数据提供了可能[4-6] 。 近年来在线社会网络的理论研究和实际应用都有飞速发展。特别是近年来高速发 展的电子商务产业促进了基于商品的推荐系统的发展，使其准确度和用户个性化方面 有了较大的提高。近几年来，针对不同人群的在线社会网络如雨后春笋不断出现。众 多不同的社会网络给不同学科的学者带来多方面的研究热点。首先，在线社会网络给 每个用户提供了个性化的私人空间，方便用户管理、分享和创造信息，也方便有共同 兴趣爱好的用户交流，为研究用户的在线交流行为提供了渠道。其次，在线社会网络 是信息传播的高速公路，特别表现在群众舆论、观点表达和谣言传播等。由于不同于 以往的信息组织和传播机制，在线社会网络上的信息传播对信息检索如实时检索模型 及工程应用提出了新的挑战。用户之间的联系建立、取消和巩固，信息传播中关键用 户的挖掘都是新的研究点。如何缩短好友浏览距离和控制谣言传播，都因用户数量庞 大而成为有挑战性的课题。对于病毒营销而言，找到在线社会网络中影响力高的节点 并实施精确的营销策略能够最大化营销效果同时降低成本。最后，对于社会 学家和心 里学家而言，在线社会网络也为他们提供了新的研究群体和集体行为特征。 2 华 中 科 技 大 学 硕 士 学 位 论 文 微博正是新型在线社会网络中具有代表性的一种新型媒体，包括美国的 Twitter、 中国的新浪微博、网易微博和腾讯微博等。用户在微博上关注其他用户，收听这些用 户发布的各类信息。与此同时，该用户也被其他用户所关注，该用户发布的信息也被 其他用户收听。对于收到的微博信息，用户可以采取转发或评论等行为。微博上的信 息量是极其巨大的，这让用户对微博的使用出现了一个新的问题:用户在享受信息传 播实时性的同时也被大量冗余信息所困扰。这些冗余信息将更有价值的信息淹没，用 户需要花费更多的时间和精力对收到的信息进行过滤。对微博用户来说，收听影响力 高的用户可以有效减少冗余信息，从而提高使用效率。因此，研究如何找出社会网络 中影响力高的用户是社会网络研究中的一个重要研究方向。 社会网络中用户影响力受多方面因素的影响，包括网络拓扑和用户行为。其中用 户行为对影响力的动态变化更为重要。分析社会网络中的用户行为，可以发现用户行 为模式的特点与群体智能中的五项原则较符合。 粒子群算法(Particle Swarm Optimization, PSO)是一种以群体智能为基础的 随机搜索优化算法。该算法利用个体在社群间的信息交流来寻找最优解。相比其它群 体智能算法，粒子群算法更容易理解，参数更少且容易实现。粒子群算法也是以生物 社会背景为基础的。 考虑到用户影响力与用户行为的关系，并且用户行为与群体智能也具有较好的一 致性，因此可以将用户影响力与群体智能相结合，利用群体智能的算法对用户影响力 进行计算。本文将分析微博用户的行为特征与群体智能的相似之处，并对群体智能算 法加以改进，利用从新浪微博平台获取的用户数据与微博数据进行实验，并对实验结 果进行分析。 1.2 国内外研究现状 3 华 中 科 技 大 学 硕 士 学 位 论 文 用户影响力研究 社会网络的一个基础特点是趋同性。趋同性来自于几个方面:社会影响力，选择 [7] 行为以及未知因素。这三方面共同支撑起趋同性 。 Holme and Newman 提出了一个生成模型来平衡社会影响力和选择行为对趋同性的 [8] 影响 。他们的思路是最开始随机地将M 条边放入任意两个结点之间，同 时对任意结点 随机分配一个意见，当两个结点意见一致时，连接这两个结点(选择)，或者当一个结 点同意他的邻居的意见时改变该结点的意见 (社会影响力)。最后的结果显示选择行为 生成的是大量小规模的群组，而社会影响力形成的是大规模的连贯群组。也就是说， 虽然这两个方面生成的群组有很大的不一样，但都支持社会网络里的群组生成。 这个模型只支持一个结点只有一个意见，但对于真实的社会网络来说过于简单。 [9] 因此Crandall 等提出了一个多维的意见向量来对复杂的社会网络进行建模 。 Scripps 等对选择行为和社会影响力提出了数学定义[10] ，并提出一个矩阵框架对 这两方面如何影响用户之间建立关系进行分析。 加入领域概念后，Tang 等提出了 Topical Factor Graph TFG 进行领域级的影响 力分析[11] 。在这个模型中，作者提出了隐藏结点的概念，隐藏结点表示为最有可能在 某一特定领域内对该隐藏结点所对应的现实结点有影响力的某个现实结点。 社会影响力分析有不少现实应用。病毒营销侧重的是影响力最大化。而根据用户 的历史购买预测用户反应对直销有很大帮助。 总得来说，传统的社会网络用户影响力分析都是基于图模型的，在图模型的基础 [7] 上建立影响力的传播模型，并根据不同的社会网络的特点，采取不同的影响力算法 。 然而，基于微博的用户影响力分析与传统的有所不同。微博的信息传播具有实时 性，信息的传播是单向且一对多的。微博上信息的传播效率是很高的，这里的传播效 4 华 中 科 技 大 学 硕 士 学 位 论 文 率包括传播速度和传播精度(因为微博的用户可以跟随任意别的用户，所以用户更多 的去跟随他感兴趣的用户，接收他感兴趣的信息)[12] 。 微博也是一种社会化媒体。与纯粹的社交网站或工具比如 Facebook 或 相比， 微博具有媒体属性，而与媒体网站相比，微博又具有社交性。而与博客的不同在于， 微博篇幅短小，信息更多是突发事件或思想的火花，而博客的篇幅通常不短，信息量 更多，但不具有实时性，且需要花费更多的时间准备。 美国创业公司 Klout，从 2009 年开始研究 Twitter 用户的影响力指数[13]，2010 年 开始对 Facebook 网站及用户提供影响力测量产品。Klout 指数 Klout Score 表征用户 在 Twitter 和 Facebook 上的综合影响力，其值介于 1-100 间，反映了用户在Twitter 和 Facebook 上行为的 35 个变量。Klout 在衡量 Twitter 用户影响力时考虑的是三个方 面:True Reach，指的是你的受众的规模，基于你的 followers 和与你互动的活跃用 户;Amplification Probability，指的是你的信息引起反应的可能性;Network score， 指的是你的受众的影响力大小。Klout 指数认为“influence is the ability to drive people to action”。因此Klout 指数与点击，评论和转发高度相关。 [14] 国内的新浪微博也推出自己的影响力测量产品:“微数据” 。微数据衡量用户影 响力主要从三个方面考虑:覆盖度、传播力、活跃度。活跃度表示你每天主动发布、 转发、评论的微博的有效条数;传播力表示对你的微博进行转发或评论的用户数以及 微博数;覆盖度表示你的活跃粉丝数。 最新的研究表明用户的关注者数量对增加用户影响力的作用没有想象中的大。美 国人工智能发展协会 AAAI 指出[15] ，拥有大量的关注者不一定能够使 Twitter 用户享 有更大的影响力。他们的研究还指出，用户在 Twitter 上发布的消息在长期内被转发 多少次或用户被提到 mention 多少次是衡量其影响力的重要标准。 5 华 中 科 技 大 学 硕 士 学 位 论 文 目前衡量一个微博用户的影响力的常用方法有以下几种。 [9] 根据用户拥有的跟随者数来衡量影响力 。这种方法最便利最常用，但 已经被证明 并不能挖掘出真正有影响力的用户。 [9] 根据用户被转发的情况来衡量用户的影响力 。这种方法比单纯用follower 数好 很多，它将其他用户对该用户的反应纳入考虑。但它的缺点是没有考虑转发的 follower 的影响力，事实上，不同影响力的用户的转发对增加该用户的影响力有不同的贡献。 PageRank 算法。PageRank 算法用于 twitter 时，将用户当作网页，用户的关系比 作链接，以此算得用户的影响力[10] 。PageRank 将用户关系放入考虑因素之中，比单纯 靠 follower 数更可靠。PageRank 算法有许多变种，比如 Topic-sensitive PageRank[11], 是分主题对全部用户做 PageRank 算法，加入了一个 topic-biased teleportation vector;还有Topic-specific TwitterRank[16] ，它与上个算法的区别是分主题时也将 用户分开。这些算法考虑了 twitter 用户的主题倾向，但没有考虑用户的其他属性， 比如用户的活跃度等。 惠普实验室提出了 IP(Influence-Passivity)算法，增加了用户消极度的概念[17] 。 消极度指的是其他用户对该用户施加影响的困难度。用户消极度越高则该用户越不容 易对其他用户的行为产生反应，反之则越容易。高消极度的用户一般很少转发、点击 或评论，反之则频繁地对消息作出反应。算法是基于 HITS 算法的，有以下假设:1.一 个用户的影响力取决于他影响的人数以及他们的被动性。2.一个用户的影响力取决于 他影响的人有多专注。专注度根据一个用户和其他用户相比给予另一个用户的关注来 衡量。3.一个用户的被动性取决于那些展示在该用户面前，但并没有对该用户成功施 加影响的影响力。4.一个用户的被动分取决于他同其他人相比拒绝其他用户影响的次 数。通过对用户影响力和消极度进行循环嵌套计算，得出用户的影响分。这个算法既 6 华 中 科 技 大 学 硕 士 学 位 论 文 利用了网络的结构性特征，也将用户之间的扩散行为纳入考虑范围。 利用简单的统计用户的跟随者或转发数来衡量用户的影响力反映不了真实的用户 影响力。相比这些简单统计方法，类 PageRank 算法或 IP 算法在计算用户影响力时考 虑的因素全面得多。然而，类 PageRank 算法与 IP 算法都存在的不足之处在于对影响 力的动态变化反映不足。 粒子群算法研究 粒子群优化算法 PSO 是一种新兴的基于群体智能的启发式随机优化搜索算法，算 法的特点包括容易实现、容易理解、不需太多参数等，受到科学与工程领域的研究者 的广泛重视，是发展最快的智能优化搜索算法之一。 在 1995 年，受到鸟群与鱼群的社会行为的启发，Eberhart 和 Kennedy[18, 19]提出了 标准粒子群优化算法。在标准粒子群算法中，每个粒子都倾向于朝着自身历史最佳位 置和邻域群体历史最佳位置运动，最后集聚于最佳位置，这被称为粒子种群的快速趋 同效应。这种效应使得算法有很大缺陷:非常容易出现局部极值、早熟收敛或停滞现 象[20-22] 。同时，算法的性能对算法参数的依赖很大[23] 。为了解决算法的上述缺陷，各 国研究者随后发展了各种改进算法。 Maurice Clerc 的研究表明不同的粒子群初始化策略对算法性能有着很大的影响 [24] 。Maurice Clerc 指出采用随机数均匀分布的策略进行粒子群初始化 在低维空间中 效果不错，实现也简单，但对于高维空间来说算法性能并不好。除此之外，Maurice Clerc 还比较了其它三种粒子群初始化策略。Richard 和 Ventura[25]提出了基于 Centroidal Voronoi Tessellations CVTs 的种群初始化策略，该策略可以使初始种群在整个解 空间分布，并且尽量保持均匀。这种策略提高了算法的全局优化搜索能力。薛明志等 人[26]则在粒子群初始化时采用正交设计的方法;Campana 等人[27]将线性动态系统引入 7 华 中 科 技 大 学 硕 士 学 位 论 文 速度与位置迭代公式，并在初始化时使粒子与粒子的运动轨迹正交。 依据粒子的邻域的范围，粒子群算法可以划分为两种模型:邻域为整个 群体的全 [28] 局模型 gbest 和邻域仅为周边粒子的局部模型 lbest 。在 gbest 模型中，每个粒子 与整个群体进行信息交换，并朝着整个群体的历史最佳位置移动，算法有较 快的收敛 [29] 速度。Kennedy 指出，尽管在收敛速度上 gbest 模型有较大优势，但 该模型的缺点也 [29,30] 同样显著:经常出现局部极值。为了改善 gbest 全局模型的不足，Kennedy 随后提 出各种 lbest 局部模型，限制粒子之间进行信息交换的范围，弥补 gbest 模型的缺陷。 各国研究人员也提出了很多改进的参数选择策略。在加速参数方面，文 献[28, 31]建 [32] 议两个加速参数之和不大于 1，并通常取两个值都为 0.5。Ratnaweera 等 人 则提出 自适应时变调整策略，即个人加速参数随着进化代数从 2.5 线性递减至 0.5，社会加速 [33] 参数随着进化代数从 0.5 线性递增至 2.5。Riget 和 Vesterstr?m 提出一种增加种群 多样性的改进粒子群算法，将加速常数的取值范围扩展到负数，并根据粒子 群的多样 性调整加速常数的正负号，正号代表“吸引(Attractive )”，负号代表“扩散 (Repulsive)”，通过状态的转换来改善算法过早收敛的问题。 最初的标准粒子群算法没有设置惯性参数，Shi 和 Eberhart[34]在 1998 年提出了这 个参数，随后他们在文献[35] 中建议根据迭代次数的增加将惯性参数从 0.9 线性递减至 0.4。近年来有研究者提出了一种根据迭代次数将惯性参数递减至 0 的取值策略[36]，该 策略利用随机近似理论 Stochastic Approximation Theory 分析粒子群优化的动态过 程。Shi 和 Eberhart 还提出了一种收缩因子[37]。收缩因子与惯性参数在典型测试函数 [38] 上具有各自的优势 ，但采用惯性参数的粒子群算法有一个明显不足:惯性参数通常 采用随着迭代次数的增加而递减的策略，后果是这类算法在算法后期的惯性权值过小， [37] 从而失去探索新区域的能力。采用收缩因子的粒子群算法则不会出现这种问题 。 8 华 中 科 技 大 学 硕 士 学 位 论 文 1.3 主要研究内容 本论文的主要研究内容是研究如何将粒子群算法与微博用户影响力研究相结合， 具体内容包括:研究微博用户行为模式与群体智能的相似性以及用户行为与用户影响 力之间的联系，研究如何根据微博用户影响力研究的特点对粒子群算法进行改进。 1.4 论文的结构安排 本论文共分为 5 章，各章的具体内容安排如下: 第 1 章介绍了本文的研究背景和研究意义。以用户影响力为基础，介绍了当前社 会网络用户影响力研究的发展以及粒子群算法相关的背景，给出了本文的主要研究内 容。 第 2 章介绍了社会影响力的相关概念和方法，对研究社会影响力的基本统计方法 以及相关研究领域和应用做了简单的介绍。 第 3 章首先介绍了标准粒子群优化算法，然后分析了微博用户的行为特征以及与 群体智能和用户影响力的关联。根据用户影响力的特点，参考标准粒子群算法，提出 了改进的粒子群算法计算用户影响力，并对改进的算法与标准粒子群算法的不同之处 进行了分析。 第 4 章利用新浪微博的用户数据与微博数据进行了算法的验证实验，实验结果表 明改进之后的算法能够有效地对用户影响力进行计算。 第 5 章对整篇论文进行总结，并分析了本文的不足之处，最后给出了本文有待提 高和改进的地方，以及下一步研究的方向。 9 华 中 科 技 大 学 硕 士 学 位 论 文 2. 影响力分析概述 社会影响力体现在当一个人因为与他人、团体或社会的关系而改变自身行为时。 在社会网络里，影响力的概念早已被广泛接受，并且出现了很多基于影响力的应用， 比如市场营销，广告和用户推荐等。但在在线社会网络爆炸性增长之前，由于数据获 取的困难，在用户影响力的量化研究上进展不快。随着 Facebook 和 Twitter 等在线社 会网络的飞速发展，相关信息与数据的获取不再成为问题，对大规模人群的影响力量 化计算成为可能。 决定影响力强度有许多因素，比如网络中两人之间关系的强度，用户之间的距离， 情感因素，网络特征以及用户个人特征等。 2.1 影响力分析的统计方法 定义一个社会网络为 , ，其中 V 代表节点的集合，E 代表边的集合。E 中 的各条边连接各个节点，每条边代表一对节点之间的社会关系。从局部来看，A 对 B 的影响力代表从节点 A 对节点 B 的直接影响，与A 对 B 的关系强度相关。从全局来看， 一些节点因为网络结构的关系具有更高的影响力，这时网络中的节点比网络中的边对 影响力的重要性更高。下面是相关的一些概念与方法: 1 边相关的度量方法 边相关的度量方法是指涉及一对节点的关系的度量方法，描述的是简单的影响力 相关的过程以及独立节点之间的互动。 1 关系强度 根据 Granovetter 的开创性工作[39] ，两个节点之间的关系强度取决于这两个节点 的邻居的重合度。节点 A 与 B 具有越多的共同邻居，A 与 B 之间的关系强度越大。如果 10 华 中 科 技 大 学 硕 士 学 位 论 文 A 与 B 的邻居的重合度较高，则认为 A 与 B 之间有较强的关系，反之则关系较弱。关系 强度也成为嵌入度。如果两个节点的邻居高度重合，则这两个节点之间的边的嵌入度 较高。当两个独立节点之间的边的嵌入度较高时，节点之间更容易相互信任，因为双 方节点很容易通过高度重合的邻居揭穿对方的谎言[40] 。反过来说，当嵌入度为 0 时， 节点之间没有共同的朋友，双方不能通过共同的朋友来验证对方，因此更难信任对方。 关系强度理论的一个合理推论是三元闭合。该推论认为假如 A 与 B 具有强关系，B 与 C 也具有强关系，则A 与 C 更有可能是强关系，反之则 A 与 C 更有可能为弱关系。 2 弱连接 当A 与 B 的邻居重合度很小时，A 与 B 的连接被认为是弱连接。当 两个节点的邻居 重合度为 0 时，A 与 B 的关系是局部桥接[39] 。在一种极端情况下，移除 A，B 之间的连 接会导致 A 所在的群体与 B 所在的群体断开联系。这时，A 与 B 的关系又可以视为全局 桥接。换而言之，在真实网络中，全局桥接出现的情况远远少于局部桥接。尽管如此， 全局桥接与局部桥接的作用非常相近。 3 边介数 边介数是另一个重要的边相关的度量方法。它指的是网络中所有节点之间的所有 最短路径包括该条边的次数。Freeman[41 ,42]最先在社会学中提出介数的概念。图的分割 问题应用到了边介数，思路是逐步移除图中边介数最高的边，最后图中的节 点被划分 成互不连接的群体。 2 节点相关的度量方法 基于节点的中心性经常被用来衡量网络中节点的重要程度。作为研究社会网络的 工具，中心性吸引了很多研究人员的注意[42 ,43] 。相比于网络中的普通节点，具有高中 心性的节点在网络中的影响更大。研究人员根据影响力的精确定义提出了许多衡量中 11 华 中 科 技 大 学 硕 士 学 位 论 文 心性的方法，根据方法中运用的随机游走的类型可以分为两大类:径向方法和径间方 法[43] 。径向方法中给定随机游走的起点节点或终点节点，而径间方法则给定随机游走 的一个途经节点。径向方法可以进一步划分为两种:一种是给定随机游走的路径长度， 计算在给定路径长度之内的所有路径条数;一种是给定目标节点的路径条数，计算经 过给定节点的路径长度。下面对一些常用的节点中心性度量方法进行介绍: 1 度中心性 度中心性是最简单且最常用的一种度量方式。该方法是属于径向方法并给定路径 长度的。常规的度中心性指的是以该节点为起点的路径长度为 1 的所有路径数量。度 中心性有很多扩展，比如将路径长度扩展到 K，就得到了 K-path 中心性。 还有一类基于网络的扩散行为的度中心性。比如Katz 中心性[44]也是 计算从该节点 开始的路径数量，但更长的路径权重更小。Bonacich 中心性[45]与 Katz 中心性比较相 似，但它允许路径权重为负。 2 接近中心性 这一类是属于径向方法但给定目标节点数的。与前一类方法不同，这一类方法计 算路径长度。Freeman 提出的接近中心性度量方法[42]是最常用的方法，它通过计算该 节点与所有其它节点的平均最短路径得到接近中心性。 3 节点介数 与边介数相似，节点介数高的节点占据了网络结构中更重要的位置，因此也扮演 更重要的角色。一个紧凑型群体与外部网络的节点通常会有大流量的信息流通，这样 的节点被认为是高节点介数的。 节点介数的计算方法属于径间方法。这类方法之所以被称为“径间”是因为考虑 了所有经过某一给定节点的路径。最著名的径间方法是 Freeman 的介数中心性方法[41] 。 12 华 中 科 技 大 学 硕 士 学 位 论 文 它衡量的是一个给定节点位于多少其他节点之间的最短路径上。最直接的计算介数中 心性的方法需要将所有的最短路径考虑进计算中来。假设有n 个节点，m 条边，那么该 方法的时间复杂度为 3 ，空间复杂度为 2 ，计算开销很大。Brandes[46] 设计了一 种更快的算法，算法中利用了 n 个单源最短路径算法，时间复杂度为 和 + 2 ，空间复杂度为 + ，降低了算法开销。 Newman[47]基于随机游走提出了一种替代算法来计算介数中心性。它的主要思路是 不计算最短路径，取而代之的是计算所有可能的游走路径的介数。 4 结构洞 在一个网络中，当一个节点与多个局部桥接相连时，这个节点被称为结构洞。典 型例子是在一个公司或机构中担当与当地沟通任务的员工。当移除这个员工时，公司 网络中在当地就会出现一个空白。这就被称为结构洞。一个结构洞式的员工能够将两 个互不相连的组织连接起来，并为两者互通信息。因此，这个员工对沟通网络中不同 部分起到重要作用。有一点值得一提，就是结构洞式的员工与公司两者的利益可能出 现不一致。对于公司来说，通过寻找更多的沟通桥梁来加快不同群体之间信息的流通 是有益的，然而当前的结构洞式员工不会乐意更多的人来分享自己的地位，因而公司 寻找更多的沟通桥梁的代价是当前的结构洞员工可能调整(降低)群体之间的信息流 来维护自身地位。 2.2 影响力与社会相似性 社会影响力研究的一个主要问题是理解社会相似性与社会关系之间的相互影响[48] 。 目前已有许多研究尝试分析不同领域的社会网络的影响力与相识性的关系。 1 趋同性 [7] 趋同性 是社会网络最基础的特征之一，指的是社会网络中一个角色倾向于与他的 13 华 中 科 技 大 学 硕 士 学 位 论 文 邻居或“朋友”更相似。这个现象较易被理解，因为给定角色的邻居或“朋友”并不 是随机选取的人物的，他们通常与给定角色在各种维度上具有相似性，比如种族、年 纪、职业、兴趣或信仰等。Singla 等在真实社会网络中进行了大规模的趋同性实验[49] 。 他们从 MSN 中获取用户交流信息，还有一部分 2006 年的 Microsoft 的网络搜索数据。 通过实验他们观察到朋友之间的相似性显著大于随机抽取的人群，特别表现在年纪， 地区和查询分类的相似性上。他们的实验结果验证了在大规模在线社会网络上趋同性 的存在。 趋同性现象的出现通常有以下机制的原因: 1 社会影响力:指的是人们有模仿他们朋友的行为的倾向性。这种倾向性促使人 们采取之前被他们的邻居展示过的行为。 2 选择行为:指的是人们倾向于那些和他们自身相似的人建立关系。 3 未知因素:除了以上两种因素，还有一些未知因素对趋同性发生影响。 这三种因素通常混杂在一起，共同促使趋同性现象的出现。 Holme and Newman 提出了一种生成模型来平衡社会影响力和选择行为对趋同性的 [8] 影响 。该模型的思路是最开始随机地将 M 条边放入任意两个结点之间，同时对任意结 点随机分配一个意见，之后当两个结点意见一致时，连接这两个结点(选择行为)，或 者当一个结点同意他的邻居的意见时改变该结点的意见(社会影响力)。最后的结果显 示选择行为生成的是大量小规模的群组，而社会影响力形成的是大规模的连贯群组。 也就是说，虽然这两个方面生成的群组有很大的不一样，但都支持社会网络里的群组 生成。 Holme 和 Newman 的模型只支持一个结点只有一个意见，但对于真实的社会网络来 说过于简单。因此 Crandall 等提出了一个多维的意见向量来对复杂的社会网络进行建 14 华 中 科 技 大 学 硕 士 学 位 论 文 [9] 模 。Crandall 等也提出了一个生成模型，与 Holme-Newman 的模型相似，。但这个模 型更复杂，它基于个人自身历史行为，邻居的历史行为以及背景分布抽样描述个人的 活动。Crandall 的模型更为强大，但也需要更多的参数，因此需要更多的 数据训练参 数。 Script[10]在 Holme 和 Newman 之后提出了选择行为与社会影响力 的正式数学定义。 公式(2.1)与(2.2)分别为选择行为与社会影响力的数学定义。 | ?1 ? 1 1? 1 0, , 式 2.1 | ?1 1 0 其中分母为原先不相连的一对节点建立连接的条件概率，分子则为相 识度超过阀 值 的一对不相连节点建立连接的条件概率。当结果大于 1 时，就认为存在 选择行为。 ? ? ? ?1 ?1? | ?1 , , 0, 1 式 2.2 ? ? ?1 ?1? | 1 , , 0 其中分母为在时间 ? 1时两个节点不连接而在时间 两个节点的相似 度增加的条 件概率，分子与分母含义相似，只是在分子中两个节点在时间时相连。与选 择行为相 似，当结果大于 1 时，就认为存在影响力。 以上的方法可以用来分析选择行为与影响力，但不能衡量在不同领域 (话题)下 的影响力。为了计算在不同话题下的影响力，Tang 等提出一个 Topical Factor Graph (TFG)模型[11] 。该模型对话题级的社会影响力分析建模成一个统一的图模型，并提出 Topical Affinity Propagation (TAP)进行模型训练。该模型的目的是同时提取用户 话题分布(或用户兴趣)，用户之间的相识度以及网络结构加以综合分析。 2 影响力与行为 在社会网络中，影响力通常体现在用户社会行为的变化上。文献[50,51] 中利用用户 历史行为计算影响力，而文献[52,53]对在网络环境下用户行为的演化以及用户行为如何 被社会影响力所影响的进行了研究。 15 华 中 科 技 大 学 硕 士 学 位 论 文 Goyal 等[50]利用用户行为的历史日志研究影响力强度 (或称概率)。他们提出了用 户影响概率和行为影响概率两个概念。Goyal 等假设如果一个用户在某一时刻做出某个 行为，而这个用户的朋友随后也做出同样的行为，那么用户对他的朋友存在影响力。 Goyal 等研究影响力概率的目的是寻找一种模型(静态或动态)对网络中的用户影响以 及行为影响信息进行建模。公式(2.3)与(2.4)给出了这两种概率的定义。 用户影响概率: | | | ,? : , , ,? ?0?? 式 2.3 行为影响概率: | | ,? : , , ,? ? 0?? | 式 2.4 其中， ? 表示用户 做出行为的时间与用户 做出行为的时间的间隔， , , , 代表行为传播强度。Goyal 提出三种方法来计算 , , , ，一 种为静态模型，一种叫连续时间(Continuous Time, CT )模型,另一种为离散时间 (Discrete Time, DT)模型。他们的实验结果表明在这三种方法之中连续时间模型的 效果最好。 Goyal 的方法能够处理大规模社会网络，但局限是忽略了用户行为之间相关性以及 用户节点本身的属性。为了解决这个情况，Tan 等[54]提出了社会行为跟踪，主要研究 如何将社会网络结构，用户属性以及用户行为这三者随时间同时建模。 3 影响力与互动 除了用户行为与属性，用户之间的互动同样反映影响力，比如每个Facebook 用户 都有一个称为 Wall 的页面，该页面显示用户的朋友发布的信息。根据这些信息，用户 能够知道与哪些朋友的关系更亲密，哪些朋友只不过是点头之交。同样地，利用 Twitter 上 followers 和 following 的成员也可以看出关系强度。Xiang 等[51]提出了一种潜在 16 华 中 科 技 大 学 硕 士 学 位 论 文 变量模型，该模型基于用户档案相似度以及用户之间的互动活动计算关系强度，目的 是找出用户网络中的强关系。 影响力除了上述部分，还与友谊迁移、自相关、群组行为等相关，鉴于篇幅，不 再一一赘述。 2.3 影响力相关研究热点 在线社会网络的爆炸性发展为社会影响力的研究提供极好的数据来源，极大地促 进了社会影响力的研究。 目前影响力研究的热点领域主要集中在影响力最大化，扩散 影响力模型和影响力传播最大化等。主要应用在病毒营销，在线广告以及寻找有影响 力的博客等方面。 2.4 本章小结 社会影响力分析的主要目的就是定性以及定量地对人与人之间的影响 力进行分析。 随着在线社会网络日渐成为人们的日常活动平台，对社会影响力的理论研究以及现实 应用发展迅速。考虑到在线社会网络的规模巨大，因此更需要高效的社会影响力计算 方法。 本章介绍了社会影响力分析的相关基础概念和一些相关算法。首先是基础的度量 方法，比如中心性，接近性以及介数等。这些方法通常是在网络结构上进行统计，不 牵涉到复杂模型。接着介绍了影响力与相似性之间的联系，提出影响力的基础在于趋 同性。趋同性包括三个方面:影响力，选择行为以及未知因素。这三个因素通常混杂 在一起促使趋同性的出现。Script 提出了影响力与选择行为的具体定义。之后讨论了 影响力与用户行为的关系。Goyal 提出了一些模型来衡量影响力与行为之间的关系，并 认为影响力会改变行为，同时行为也可以改变影响力。除了这些，影响力还与互动、 17 华 中 科 技 大 学 硕 士 学 位 论 文 友谊迁移、自相关以及群组行为等相关。最后介绍了社会影响力的研究热点以及应用 热点。 总的来说，用户的影响力与用户的社会关系以及自身属性密切相关，两方面的因 素都对影响力的产生发生作用。同时，随着在线社会网络的飞速发展，对社 会影响力 分析的需求也日渐重要，并且在社会网络的各方面发挥着重要作用。 18 华 中 科 技 大 学 硕 士 学 位 论 文 3. 基于标准粒子群算法的用户影响力分析 3.1 标准粒子群优化算法 粒子群优化算法是Kennedy和Eberhart在1995年提出来的，这两位研究者受人工生 命研究结果的启发，对鸟群觅食过程中的群体行为进行模拟，进而提出该算法。1995 年IEEE国际神经网络学术会议发表了题为 “Particle Swarm Optimization”的论文， [18,19] 标志着PSO算法诞生。粒子群算法是一种以群体智能为基础的随机搜索优化算法 。 与其他进化算法一样基于 “种群”和 “进化”的概念，粒子群算法通过个体之间的信 息交流，在解空间中实现对问题最优解的搜索;与其他算法的不同之处在于，粒子群 算法不对个体进行交叉、变异、选择等各种进化算子操作，而是将个体看作是在解空 间中的一个粒子，每个粒子根据自身与邻域的历史最佳位置确定自己的速度，以该速 度在解空间中搜索，最终搜索到问题的最优解。粒子(Particle)没有质量，也没有 体积。粒子群算法具有生物社会背景[39] ，算法的特点包括容易实现、容易理解、不需 太多参数等，在非线性、多峰问题上表现出很好的全局搜索能力, 受到科学与工程领 域的研究者的广泛重视。 标准粒子群优化算法 粒子(Particle)没有质量，也没有体积，每个粒子以一定的速度在解空间中进 行搜索运动，粒子个体的经验以及个体与群体之间交流的经验决定粒子的速度，粒子 运动的方向主要由自身历史最佳位置和邻域历史最佳位置确定，最终搜索到问题的最 优解。 标准PSO的算法流程如下: 1 对每个粒子的位置和速度等进行初始化; 19 华 中 科 技 大 学 硕 士 学 位 论 文 2 评价每个粒子的适应度; 3 为每个粒子更新它的自身历史最优位置，方法是比较粒子目前位置与之前的自 身历史最优位置的适应度，自身历史最优位置取适应值更好的位置; 4 更新全局历史最优位置，方法是比较上一步中最好的位置与全局历史最优位置 的适应度，全局历史最优位置取适应值更好的位置; 5 根据速度与位置进化方程为每一个粒子更新速度以及位置; 6 如果迭代次数没有达到预设值或者适应值不够好，即没有达到算法的终止条件， 跳回第(2)步。 对粒子群进行初始化的方法通常是在解空间中随机地安排粒子位置，速度也是随 机安排的。粒子当前位置初始化为自身历史最优位置，而全局历史最优位置则选择所 有粒子中最好的位置。 根据求解的问题不同设置不同的适应度函数，即意味着适应度的值直接表示解的 好坏。 粒子群优化算法的核心是速度进化公式，粒子根据该公式更新自身速度。 公式(3.1)为标准粒子群算法的速度进化方程: + 1 + ? + ? 式 3.1 1 1 2 2 其中 + 1 为粒子j 在第t次迭代的速度;为惯性参数， 与 为个体部分与社 1 2 会部分的加速参数， ， 为随机参数; 为当前位置， 为自身历史最佳位置， 1 2 为邻域历史最佳位置。 标准 PSO 的速度进化公式可以分成公式(3.2)中的三个部分: + 1 + + 式 3.2 其中 20 华 中 科 技 大 学 硕 士 学 位 论 文 ， ? ， ? 1 1 2 2 第一部分表示粒子之前速度所起的惯性作用。 第二部分为“个体认知”部分，表示粒子基于自身的经验所做出的考虑， 这个部 分里不考虑群体中其他粒子施加的影响。 第三部分为“社会认知”部分，表示群体中其他粒子与该粒子之间存在的信息交 流，与第二部分相反，这里不考虑粒子自身的经验。 算法的参数选择 惯性参数 的作用是粒子的运动保持一定的惯性，使粒子不会过快陷入收敛，而是 保持扩展搜索空间的能力，对解空间中新的区域进行探索。 加速参数 和 分别代表粒子在更新自身速度的过程中对“个人认知”与“社会认 1 2 知”这两部分的权重。加速参数高则粒子朝向最优位置运动的速度快，在接近最优位 置时可能会发生震荡;加速参数低则粒子朝向最优位置运动的速度慢，在接 近最优位 置的过程中可能会受更多干扰而徘徊在目标区域之外。 当方程只有惯性参数时，即加速参数都为 0，即粒子的速度不会改变方向，只会按 照惯性参数衰减，直到解空间的边界。在这种情况下，粒子群在解空间中的搜索范围 很有限，求得最优解的可能较小。 当方程只有后两个加速参数时，即惯性参数为 0，即粒子的速度不再具有延续性， 只取决于粒子当前的位置和它们历史最优位置。在某种情况下，比如一个粒子的位置 的适应值恰好是全局最好的，这个粒子的速度将为 0，静止在目前的位置上(也是全局 最优位置)。其它粒子则根据自身历史最优位置和全局历史最优位置确定本 身的速度。 这样，粒子群的搜索范围将是以当前最优位置为中心的一个区域而忽视掉解空间的其 他区域，算法的全局搜索性能严重不足。 21 华 中 科 技 大 学 硕 士 学 位 论 文 从以上两种情况可以看出，惯性参数可以使粒子对解空间进行更充分的搜索。因 此在不同的问题中，根据该问题的特点可以改变惯性参数来适应问题，平衡算法的全 局搜索和局部搜索能力。 当方程没有第一个加速参数时，即1 0，则粒子的个人认知能力不存在，算法转 变成 “只有社会 social-only ”模型。在这个模型中，粒子除了惯性参数代表的速度 惯性外，只会朝向全局最优位置运动。这种情况下粒子能够对解空间进行较充分的搜 索，并且比标准粒子群算法更快地收敛，但是不足之处在于针对复杂问题时，也比标 准粒子群算法更容易出现局部收敛。 当方程没有第二个加速参数时，即2 0 ，算法则变成另一种模型:“只有认知 cognition-only ”模型，即粒子群中各个粒子之间没有信息交流。在这个模型中， 粒子的速度基本由自身历史最优位置决定。这样粒子基本上只在以自身位置为中心的 一片范围内进行搜索。粒子之间没有信息交流，从整个粒子群来看已不具有群体智能 的特征了，并且这种模型进行搜索优化最优解的效果很差。 3.2 改进的粒子群优化算法 传统的标准粒子群算法并不适应于在社会网络领域计算用户影响力。针对微博领 域的特征，本论文对标准粒子群优化算法加以改进。 微博用户行为分析 微博的特点有实时性、快捷性以及现场感。每天都有大量微博用户在微博平台上 发布信息和与网友互动等。这些用户以及用户的行为共同构成了整个微博平台的环境。 微博用户除了自己发布信息，每天还接收大量来自于该用户所关注的用户的信息。 用户从中发现一些有用的微博信息，并对这些信息进行转发或评论。通常， 微博用户 22 华 中 科 技 大 学 硕 士 学 位 论 文 的行为有以下几种类别:发布信息、转发其他用户的微博信息以及对其他用户的微博 信息进行评论等。 用户任何时候都可以发布微博信息，微博的内容没有明确限制，但字数不能超过 140个字。该用户所有的跟随者可以看到用户发布的信息。转发的对象是该用户跟随的 其他用户的信息，该用户是被转发用户的跟随者。当用户看到其跟随的用户所发布的 信息时，该用户挑选出被认为有价值的信息，对该信息进行转发。该用户所有的跟随 者都可以看到该用户转发的信息，同时被转发的用户也因此获得关注。评论的对象也 是该用户跟随的其他用户的信息，但它与转发的主要区别是评论只能被相关的两个用 户看到，其他用户则看不到该评论信息。 从信息传播的角度来说，用户发布的信息能够被用户所有的跟随者们看到，这时 信息的传播面是基于用户跟随者的数量的。但是转发能扩展被转发信息的传播面，使 得更多的用户能够看到该信息，因此要提高信息的传播面最主要的是提高信息的转发 率。评论则不同，因为评论用户的微博信息只会被相关的两个用户看到，其他用户看 不到该评论信息，因此评论别人的微博这种行为对信息传播的影响较小。 转发信息对转发方和被转发方都有益处。被转发的用户因为转发扩大了信息的传 播面，而转发的用户则因为转发信息的高价值而受益。 考虑到微博平台的社会性，用户的这些行为受到自身与网络两方面影响: 1 自身因素。用户发布信息、转发以及评论等行为都是与用户自身的认知水平以 及价值观相关的。不同的用户发布的信息内容也大多不同，转发与评论也是如此。在 通常情况下用户的认知和价值观的改变是很缓慢的，因此可以认为用户自身因素对用 户行为施加的影响基本是稳定的。 2 网络因素。在线社会网络中，微博用户不是孤立的节点，相反微博用户与网络 23 华 中 科 技 大 学 硕 士 学 位 论 文 中相邻的用户经常保持互动。当网络邻居在与该用户互动时，网络邻居的认知与价值 观也会影响到用户自身的认知与价值观，随之影响到用户的行为。比如，当用户跟随 的其他用户都在讨论一个话题时，该用户会看到这些用户讨论的内容，通常该用户也 会加入到讨论中来。还有，如果某类信息经常被用户的跟随者转发，这代表着这类信 息更符合其跟随者的价值观，用户基于这些正面反馈，会加强该方面内容的发布，反 之则会减少。 群体智能与微博用户行为 群体智能的研究起源于对自然界中一些生物群体的观察，比如蚂蚁，鸟类以及鱼 类等，这些生物单个智能并不出色，然而当它们聚在一起生活时，这个群体经常会表 现出超越标准的智能，比如蚁群、鸟群以及蜂群寻找食物等，这种群居性生物通过群 体之间的交流所表现出的行为特征在宏观上具有超越个体智能所能达到的水平，因此 被称为群体智能。 具有群体智能的群体之中的单独个体智能并不高，个体所执行的行为大多都很简 单，然而许多个体通过个体与个体之间的互相交流，依靠每个个体对自身简单行为的 调整，可以完成更复杂的任务。整个群体表现出来的复杂行为是自组织性的，不存在 一个控制中心，而是通过简单个体的交互而突现出来的。这种突现智能(Emergent Intelligence)被分布式的个体控制，能够适应目前流行的分布式工作环境，而且不 会由于某些特定节点的故障而影响整个群体的工作，具有较强的鲁棒性。个体之间的 通信并不是直接的交换信息，而是一种被称为“激发工作”的方式，即个体在背景环 境中留下某些信息，当其它个体也处在这个环境中时，它们对之前留下的信息做出反 应。由于个体之间不需要建立直接联系的通道，因而在维护大量个体之间的通信的开 销较小，具有可扩充性。 24 华 中 科 技 大 学 硕 士 学 位 论 文 除了上述的的特点，群体智能还包括这五条基本原则: 1 就近原则 (Proximity Principle)，群体之中的个体具有简单的智能，能够对 空间和时间进行简单计算; 2 品质原则 (Quality Principle)，个体能够对环境的变化做出响应; 3 多样性反应原则 (Principle of Diverse Response)，个体的行动范围不应该 太窄; 4 稳定性原则 (Stability Principle)，个体在环境变化时通常会保持稳定，不 会每次都对自身行为作出改变; 5 适应性原则 (Adaptability Principle)，个体在环境变化时会对改变行为评 估所需的代价，当个体觉得改变行为是适当的并且不需太高代价时，个体改变自身的 行为。 微博用户群体在宏观上也表现出分布式和自组织性。微博用户所表现的行为特征 与群体智能的五项原则在本质上是一致的。 1 微博用户具有传播能力，该能力无需用户具有太多知识储备，任一个正常的用 户都能做到; 2 微博用户能够感受到周边用户发生的变化，并作出响应; 3 每个微博用户的行为都有自己的特点，这保证了微博环境的多样性; 4 微博用户对信息都会有自己的判断，这些判断是以自身较稳定的知识水平和价 值观为基础的，因此用户的行为不会轻易改变; 5 尽管如此，微博用户也会根据本身阅历以及知识水平的变化对自身行为进行修 正。 25 华 中 科 技 大 学 硕 士 学 位 论 文 从以上分析可以看出，微博用户所表现出的行为特征与群体智能的五项基本原则 基本相符合。 影响力与微博用户行为 社会影响力体现在当一个人因为与他人、团体或社会的关系而改变自身行为。从 微博上看，具体有三个方面能够表现用户影响力: 1 用户的粉丝数是基础。一定量的粉丝数保证了该用户发布信息的初始传播范围， 当粉丝数过低的时候，信息的传播被局限在小范围里，并且因为粉丝数过低，使得信 息被接受并扩散出去的可能性降低了。在这种情况下，用户的影响力很难提升。然而， 很多研究表明并不是粉丝数越多影响力就越大，当粉丝数达到一定数量之后，用户影 响力更多的取决于其他因素。 2 用户微博信息的被转发数。一般来说，用户的信息被转发表明了转发该信息的 用户认同这条信息的价值。信息被转发的次数越多表明对该信息的认同越多，因此用 户的被转发数在很大程度上表明了用户被其他用户所接受的程度。 3 其它因素。除了以上两点，用户自身特征也会对影响力产生影响，比如被影响 的用户的影响力等。 事实上，用户影响力不是一成不变的，它会随着用户在网上的各种行为而变化。 当用户A 发出的信息被用户 B 转发，A 的影响力会增加，因为B 的转发使得更多的用户 看到 A 发出的信息。而当 A 转发用户 B 的信息时，A 的影响力同样会增加，因为A 的转 发行为加强了信息的传播。以上两种情况下，计算用户 A 的影响力变化时需要考虑到 用户 B 自身的影响力。 计算用户影响力的改进粒子群算法 26 华 中 科 技 大 学 硕 士 学 位 论 文 因为用户行为具有群体智能的特征，同时用户行为对用户影响力具有决定性的作 用，基于以上分析，本文提出一种改进的粒子群算法用来计算用户影响力。 1 影响力公式 公式(3.3)表示当用户A 与用户 B 之间发生转发或被转发行为后，用户 A 的影响 力增量 。 ? ? 式 3.3 其中 为该行为的影响因子。 则表示用户 B 的影响力。 这样，得到在用户集合 1, 2, 3 „ 中用户A 的影响力。公式 (3.4)定义了 用户 A 的影响力。 + 1 + ? ? 式 3.4 综合 (3.3)和(3.4)式，得到用户影响力公式(3.5)。: + 1 式 3.5 其中 [ , , „ ]，为用户 A 对用户集合 U 中所有其它用户的行 1 2 3 为的影响因子向量， [ , „ ]，为用户集合 U 的影响力 1 1 1 向量。 2 位置与速度的定义 对于用户集合 1, 2, 3 „ ，可以将整个用户集合可以看作 N 维空间，用户 A 在每一维上的位置可以通过用户 A 与该维所对应用户的影响因子来表示，那么用户 A 在空间中的位置可以用 [ , , „ ]表示。 1 2 3 粒子群算法将速度分为三个部分:“惯性部分”、“个人认知部分”以及“社会部分”。 对应于用户影响力，当用户 A 与 B 之间发生某种行为后，A 与 B 的相对应维度的影响因 子发生了改变，并且这种改变具有某种持续性，因为用户 A，B 对之前的交互行为存在 27 华 中 科 技 大 学 硕 士 学 位 论 文 记忆，而这种记忆使得用户 A，B 对未来的行为产生预期，这种预期随着时间逐渐降低。 相对应的是用户 A，B 之间的影响因子也会保持同样的延续性并会随着时间而降低。 与此同时，用户的行为一直伴随着个人与社会的双重影响。用户 A 在微博上接受 大量来自于该用户关注的其他用户发布的微博信息，通过对这些微博信息进行评价， 用户 A 挑选出有价值的信息进行传播(即转发);同时用户 A 在发布微博信息(包括自 创微博信息以及转发微博)之后，得到粉丝们的反馈(主要是被转发)。在这个过程中， 用户 A 的个人经验来自于粉丝们的反馈，这些反馈使得用户 A 能够改进自己的行为; 社会经验则来自与他所接受到的信息，用户 A 从中挑选出有价值的信息的过程也影响 了A 的行为。 将用户通过各种行为而发生的影响因子变量看作是速 度 ，参照PSO 的速度公式， 得到公式(3.6)。 + 1 ? + + 式 3.6 被转发 转发 式中第一部分为惯性部分，为惯性参数。 第二部分中， 为个人权重参数， 为用户 A 在时间 t 至 t+1 之间的个人经 被转发 验。通过计算用户A在该时间段内被用户B转发的被转发率 衡量用户A 的个人经验， 公式(3.7)为该参数的计算公式。 ? 转发微博数 式 3.7 ? 总微博数 ? ? 上式中 转发微博数 表示用户 A 被用户 B 转发的微博条数， 总微博数 表示用 户 A 发布的微博总条数。 扩大到整个用户空间 1, 2, 3 „ ，得到用户 A 的个人经验 公式(3.8)。 [ ， ， „ ] 式 3.8 被转发 1 2 3 28 华 中 科 技 大 学 硕 士 学 位 论 文 第三部分中， 为社会权重参数， 为用户A 在时间 t 至 t+1 之间的社会经验。 转发 通过计算用户A在该时间段内转发用户B 的转发率 衡量用户A 的社会经验，公式(3.9) 为该参数的计算公式。 ? 转发微博数 式 3.9 ? 总微博数 ? ? 上式中 转发微博数 表示用户 A 转发用户 B 的微博条数， 总微博数 表示用户 B 发布的微博总条数。 扩大到整个用户空间 1, 2, 3 „ ，我们得到用户 A 的社会 经验公式(3.10)。 [1 ，2 ，3 „ ] 式 3.10 转发 这样，得到了在用户空间中的影响因子的速度与位置更新公式。公式(3.11)为 粒子的位置更新公式。 + 1 ? + + 被转发 转发 + 1 + + 1 式 3.11 3 对算法的一些解释 考虑到用户位置是基于用户行为的，而用户行为是无法被定义为最优的，因此改 进的算法舍弃了自身历史最优位置与全局历史最优位置。算法利用用户行为的不确定 性来保证粒子运动的随机性。同时，算法对于收敛性没有要求，原因在于影响力是一 个动态变化的值，不存在最优解。 4 与基本 PSO 的改进之处 计算用户影响力与一般粒子群算法应用的问题有较大的区别，因此改进的粒子群 算法与标准算法相比，也有一些创新的思路。 标准粒子群算法用来寻求最优解，利用个人最佳位置与历史最佳位置与当前位置 29 华 中 科 技 大 学 硕 士 学 位 论 文 的距离确定速度，这样可以保证粒子的运动大方向是朝向最优位置的，并且通过随机 参数保证粒子运动的随机性与多样性。而改进的粒子群算法是用来计算微博用户影响 力，单个微博用户的影响力是不存在最优解的，因此不需要记忆最佳位置。用户的行 为本身存在随机性，因此也不需要随机参数。因为不需要寻找最优解，因此本文的方 法不存在收敛的问题。 标准粒子群算法利用一个适应值函数计算位置的优劣度，并以此决定是否更新最 优位置。而在本文的方法中，用影响力公式 3.3 代替适应值函数，通过该公式，可以 得到用户当前的影响力，更新之前的影响力。 3.3 本章小结 粒子群优化算法是 Kennedy 和 Eberhart 在 1995 年提出来的，这两位研究者受人 工生命研究结果的启发，对鸟群觅食过程中的种种群体行为进行模拟，进而提出该算 法。粒子群算法是一种以群体智能为基础的随机搜索优化算法。与其他进化算法一样 基于 “种群”和 “进化”的概念，粒子群算法通过个体之间的信息流通，在解空间中 实现对问题最优解的搜索;粒子群算法将个体看作是在解空间中的一个粒子，每个粒 子根据自身的与邻域的历史最佳位置确定自己的速度，以该速度在解空间中搜索，最 终搜索到问题的最优解。粒子(Particle)没有质量，也没有体积。粒子群算法的特 点有容易实现、容易理解、不需太多参数等，受到科学与工程领域的研究者的广泛重 视。 微博用户影响力与用户行为之间存在紧密的关联关系，而用户群体所呈现的行为 特征符合群体智能的五项原则，这为利用基于群体智能的算法来计算用户影响力提供 了理论支持。 在本章中，首先介绍了标准粒子群算法，分析了作为算法核心的速度进化公式中 30 华 中 科 技 大 学 硕 士 学 位 论 文 的核心要素，并且解释了算法的各项重要参数。然后分析了微博用户行为， 并阐述了 微博用户行为与微博用户影响力之间的联系。之后对用户群体的行为特征与群体智能 的五项原则做了对比，这两者的相似性为改进粒子群算法提供了理论基础。最后提出 了计算微博用户影响力的改进粒子群算法，对算法中各部分含义进行了具体阐述，分 析了与标准粒子群算法的不同之处。 改进的粒子群算法运用了标准粒子群算法的思想，针对微博用户影响力领域的特 点，对标准粒子群算法进行改进，具有一定的创新性。在下一章中，将对改进的算法 进行实验验证。 31 华 中 科 技 大 学 硕 士 学 位 论 文 4. 实验结果以及分析 社会网络的快速发展为用户参与提供了广阔的平台，用户有多种途径参与到虚拟 网络生活中。网络社会的用户有多种行为，而这些行为构成了网络生活的主体并造成 用户之间错综复杂的各种关系。上一章从微博用户的行为出发，分析出用户行为与影 响力、用户行为与群体智能的关系，并提出了改进的粒子群算法。 本章以新浪微博为数据来源，从中获取用户行为数据，并利用改进的粒子群算法 进行用户影响力计算。之后对实验结果进行分析，检验算法的有效性。 4.1 实验数据集 论文的实验数据来自新浪微博。新浪微博是国内由新浪公司于2009 年 8 月推出的 一个类 Twitter 平台，占据了中国微博用户总量的一半以上。 使用新浪微博 API，先从种子用户出发，连续爬取一个月，最后得到共计有 56 万 个用户，3600 万条微博信息，其中有 160 万个用户关系。因为新浪微博API 对爬取用 户数据有一定的限制，获取的用户信息和用户关系以及微博信息并不能覆盖完整的用 户社会网络。因此本文从中选取了 1151 个用户的数据进行实验，其中有 16781 个用户 关系，还包含这些用户在 2011 年 4 月 1 日至2011 年 4 月 30 日之间所发的全部微博信 息，共计 36166 条。 4.2 实验数据分析 本文对微博信息进行了初步的统计，图4.1 是在 2011 年 4 月期间每日的微博总条 数以及被转发的微博条数。图 4.2 是被转发的微博条数与微博总条数之比。从图 4.1 中可以看到，每日微博总条数变化很大，最多达到 2000 多条，最低不到 500 条，而被 32 华 中 科 技 大 学 硕 士 学 位 论 文 转发的微博条数更少。被转发微博条数在总微博数中占的比例很低，最高为 11%，最低 为 2%。原因在于统计转发微博时，去掉了转发双方不在选定用户集中的情况，只考虑 了转发双方都在该用户集的情况，这样统计得到的数值会偏低。 2500 the number of retweets 2000 the number of s t e all tweets e w t 1500 f o r e b m 1000 u n e h t 500 0 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 date 图4. 1 2011 年4 月期间微博信息条数 12.00% 10.00% s t e e 8.00% w t e r f 6.00% o o i t a r 4.00% e h t 2.00% 0.00% 1 3 5 7 9 11 13 15 17