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

　　摘要：由于影响范围的重叠效应，单纯的影响力度量算法并不能解决微博网络中的影响力最大化问题，针对这一研究现状，提出一种用于微博网络中TopK节点挖掘的算法GABE。通过归纳决定微博用户影响力的关键因素，提出了节点间影响率的概念，进而建立了用于用户影响力度量的WIR算法；根据得到的WIR值提出了符合微博特性的影响力传播模型，运用贪婪算法挖掘出微博网络中的TopK节点。以爬取到的新浪微博数据进行了模拟验证，结果发现GABE在影响范围上与传统的最大化算法和影响力度量算法相比分别提高了7.7%和20%。这表明通过引入微博特性和贪婪思想，GABE较好地解决了微博网络中的影响力最大化问题。

　　关键词：微博；影响力度量；PageRank算法；影响力最大化；贪婪算法

　　中图分类号：TP393.094

　　文献标志码：A

　　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影响力度量算法。