基于微博网络的影响力最大化算法

　　0引言

　　微博作为一种迷你型博客，在近年来得到了广泛的应用。据统计，Twitter当前在全球多个国家拥有超过18种语言的用户近2亿，现有的四大微博即新浪微博、腾讯微博、搜狐微博、网易微博的发展呈爆炸式状态，据CNNIC统计，2012年微博注册人数已超过3亿。与传统社会网络中通过互相认证的好友关系建立拓扑结构不同，微博是通过“关注”行为构成了具有广播性质的信息扩散网络，其信息传播的速度、广度和效率都得到了极大的提高。微博已经成为消息扩散和舆论传播的主要平台。因此，在微博中具有影响力的少数用户非常值得关注，这部分用户在信息传播、舆论形成中起到关键作用。挖掘微博网络中的影响力节点，解决微博网络中的影响力最大化问题在市场营销、舆情管控等方面具有重要意义。

　　社会网络中的影响力研究由来已久，Richardson等[1]将影响力最大化问题定义为如何选择K个初始节点使最终的影响力扩散范围最大化。Kempe等[2]在线性阈值模型（LinearThresholdModel，LTM）的基础上提出了一种自然的爬山贪心算法，它在每一步都选择当前“最具影响力”的节点作为初始传播对象进行传播。所谓“最具影响力”的节点，即是当前能够激活最多节点的节点。但是贪心算法也存在着明显的缺陷，在数据规模较大的情况下，贪心算法的时间复杂度极高。针对这个问题，Leskovec等[3]进行大量工作后提出无全称等CELF改进算法将算法执行效率提高了数百倍，Chen等[4]也提出自己的改进算法可以以较高的运算效率在大规模数据集上进行计算。Narayanam等[5]提出了基于合作博弈的Shapley值解概念的SPIN算法，大幅度提高了计算影响力最大节点集合的效率。田家堂等[6]提出了一种两步骤的启发式算法，以此提高运行效率。近年来，随着微博应用的兴起，挖掘微博网络中的影响力用户成为研究者关注的热点。初期的研究集中在对微博影响力的定性分析及定义上[7-8]。Cha等[9]使用粉丝数量和微博转发数量对用户影响力进行了衡量，结果表明粉丝数量多的用户微博不一定会得到很多的转发或者评论。郭浩等[10]基于用户消息传播范围对用户影响力进行量化定义，并给出用户影响力的计算方法。随着研究的深入，当前的研究大多借鉴了PageRank算法的思想，对微博中的用户影响力进行排名。Weng等[11]利用PageRank算法的思想，设计了TwitterRank算法来衡量一个用户在某一主题内的影响力。杨长春等[12]引入了博主传播能力的概念，提出InfluenceRank算法来评估博主影响力。

　　目前关于微博的影响力研究主要集中在对微博用户的影响力度量排序上，这种度量方法由于在结果上的聚合特性以及传播范围上的重叠性，忽视了微博网络中的弱连接结构，无法挖掘出使影响范围最大化的节点，因此不能解决微博网络中的影响力最大化问题。而社会网络中的影响力最大化算法由于没有建立可以体现微博特征的影响力传播模型，并不适用于微博网络。针对这一问题，本文的解决思路是将微博中的影响力度量与TopK节点挖掘算法相结合，具体为：1）通过引入影响率的概念建立一种WIR（WeiboInfluenceRank）算法对微博用户影响力进行度量；2）利用WIR值建立一种新的扩展的线性阈值传播模型，并在此基础上运用贪婪算法，最终形成基于微博网络的影响力最大化算法。

　　1微博用户影响力度量

　　用户的影响力本质上是用户之间的相互作用，一个用户能够对其他用户发生的作用越大，该用户的影响力也越大。社会网络中的用户影响力定义多以节点度数为依据，度数大的节点发布的信息将被更多的用户接收到，因此具有更大的影响力。这种定义方式无法体现出微博平台的应用特点，本文将微博网络中的影响力定义如下：

　　定义微博用户影响力。微博网络中的用户影响力体现为一个用户通过发布微博行为激发另一用户发生评论或转发行为的潜力。

　　依据微博用户影响力的定义，本章将首先分析决定影响力的关键因素，并在此基础上综合考虑用户之间的影响程度和用户活跃程度，借鉴PageRank算法的思想，提出一种WIR影响力度量算法。

　　1.1微博用户影响力关键因素分析

　　决定微博用户的影响力的关键因素有：

　　1）用户间亲密程度。两用户之间的历史转发及评论数体现了两个用户之间的亲密程度和影响能力，越高的历史转发及评论数说明未来用户之间产生信息行为的可能性也越大。

　　2）用户活跃程度。用户的活跃度可以表示为用户单位时间内发表的微博数量。有的用户经常发表微博或者发表评论，有的用户则很少发微博。因此，用户的活跃度反映了用户的参与程度、积极程度。活跃程度越高，发布的微博被转发或评论的机会越大，影响其他用户的可能性也越大。

　　3）用户粉丝数及粉丝的影响力。粉丝数量是微博用户影响力的一个重要因素。一般来说，一个用户的粉丝越多，那么该用户的影响力也越大，用户的粉丝越多，激发另一用户产生信息行为的潜力就越大，越容易影响到其他人，且所花费的代价也越小，反之亦然。同时，粉丝与粉丝之间也不能同等对待，粉丝自身的影响力以及网络的用户规模也是衡量用户影响力的重要指标。

　　1.2WIR算法描述

　　2微博网络影响力最大化算法

　　影响力最大化问题定义为如何选择K个初始节点使得最终的传播影响范围最大化，由上一章的分析可知，通过计算用户的WIR值，可以得到用户的影响力排序，然而若直接选择WIR值靠前的K个节点作为初始节点，并不能保证最终的影响范围最大化，这是由于微博用户的粉丝影响力越大，则用户影响力也就越大，导致K个节点有很大的可能性聚集在同一簇内，忽视了网络结构中的弱连接节点。如图1所示，节点[1，2，3，4，5，6]构成了一个社团，其社团中的节点度数相对较高，因此影响力度量算法更容易将此社团内的节点排序到前几位，然而这样得到的结果并不能使影响范围最大化，因为其忽视了节点[8，9，10]所构成的一些较小社团。

　　2.2基于ELTM的微博网络影响力最大化算法

　　改进后的线性阈值模型体现了微博特征，节点之间的信息传递概率取决于节点的传播影响力，在ELTM的基础上运用贪婪算法可以实现针对微博网络的影响力最大化算法，基于此，本文提出了基于ELTM的贪婪算法（GreedyAlgorithmBasedonELTM，GABE）。算法的核心思想包括三个阶段：