基于在线社会网络的用户影响力研究

许丹青，刘奕群，张 敏，马少平

(清华大学 计算机系,智能技术与系统国家重点实验室，清华大学信息科学与技术国家实验室(筹)，北京 100084)

基于在线社会网络的用户影响力研究

许丹青，刘奕群，张 敏，马少平

(清华大学 计算机系,智能技术与系统国家重点实验室，清华大学信息科学与技术国家实验室(筹)，北京 100084)

对大规模的在线社会网络图结构进行了较为系统的分析，结果表明社会网络的入度、出度、发文数等基本符合幂律分布。社会网络的小世界属性也使得强连通关系呈现“纺锤体”形状。该文从用户的阅读概率角度引入用户的发文行为、浏览行为与标签社区小世界属性等对用户的社会影响力模型进行建模。实验结果显示PTIM模型融合了发文行为与小世界属性等特性，在最具影响力用户节点、用户粉丝数、认证用户数与人工标注的相对用户影响力大小等指标上均表现出稳定的性能。

社会影响力;小世界属性;信息扩散;社会网络

1 引言

社交网络已经逐渐成为用户获取信息的一个不可或缺的工具。与传统的复杂网络不同，社交网络中的信息发布权不再只是被媒体编辑等少数人掌握，社交网络用户掌握了信息发布的自主权。社会网络逐步改变了用户与互联网的交互方式和互联网用户的行为习惯。新浪微博作为中国社交网络的一个典型代表，其发展速度也远远超过了之前任何传统媒体的普及速度。互联网从发展初期到用户量达到5 000万用了四年的时间，而微博仅仅用了14个月。截止2012年底，我国微博用户规模达到了3.09 亿，较2011年增长了5 873万，网民中微博用户比例达到了54.7%[1]。

在社会网络中，用户关注关系、发文转发等行为都对信息传播有着重要的影响[2-3]，不同影响力的用户在信息传播中也担当着不同的角色，社会影响力分析[4-5]也是社会态势分析的重要组成部分，影响力的分析可以帮助市场营销领域更好地定位宣传用户和垃圾用户[2-4]。本文中，我们搜集了约260万的社会网络用户数据，对社会网络的图结构进行详尽的统计分析。我们从用户阅读概率的角度出发对用户影响力进行定义，并引入用户的发文与浏览行为等假设构建不同的社会影响力模型。我们选取不同模型的最具影响力用户、粉丝数与认证用户的识别、基于人工标注的用户影响力相对大小等指标对不同的影响力模型进行评估。实验结果表明不同的模型适用于不同的小世界群体的影响力识别。

2 已有工作概述

根据广义的社会学理论[6]，一个用户的社会影响力被定义为他的某一行为引起或促使另一用户产生相应的行为的能力。基于现有的社交网络平台，很多的研究学者从不同角度对用户的社会影响力进行度量与评价[7-8]。初始的基于社交网络上的社会影响力是由用户的粉丝数来决定的，如果某用户拥有的粉丝数越多，说明其社会影响力越大[6]。然而，后续的分析结果发现单纯的基于关注关系图并不能对社会影响力进行全面而准确的描述。用户的话题分布、专业领域、发文内容与频率等均可能对用户的影响力评估产生一定的影响，而且同一用户可能对不同领域发挥的影响力很不同[8-10]。

前人的一些研究工作基于传统的Web中的PageRank[11]算法对社会网络中的节点影响力进行迭代度量；也有一些工作引入HITS[12]算法作为衡量社会影响力的方法之一。HITS算法假定每个节点的影响力都由自身的内容影响力与链接影响力两部分组成，而且好的链接影响力节点通常指向具有高内容影响力的节点。在PageRank 算法中，一个节点的影响力是所有关注这一节点的节点集合(或称为粉丝集合)的影响力之和，一个节点的粉丝集合的影响力之和越大，则表明这一节点所具有的影响力越高。诚然，这些传统Web网络中的著名算法假设[11-13]也同样适合于社会网络的影响力。在本文中，我们将用户的阅读概率引入到社会影响力的定义中，结合发文习惯、小世界属性、浏览假设等完成用户影响力模型的构建。

3 社会网络的图结构分析

3.1 入度、出度等图属性分析

我们将某一用户的粉丝数目定义为入度，关注数目定义为出度。现有的社会网络的入度分布见图1。与其他复杂网络相似，社交网络的入度频度由两段幂率分布组合而成。有相当多的用户被少于十个用户关注，这些用户主要由僵尸用户、不活跃用户与新用户组成。他们在社交网络中很常见，但是在社交网络中发挥的作用并不是很大，影响力相对都比较小，甚至有的会产生一些负影响力(如垃圾用户或水军)，经常推送广告或者发布一些垃圾信息等。另外的一部分用户拥有着很多的粉丝，被称为影响力大的用户，我们的统计结果表明，前30%的高入度用户影响着了大约80%的用户。

除了入度分布之外，我们也对社会网络的出度分布进行了分析,结果见图2。前人研究显示在小范围的社会关系图中出度频度也符合幂律分布。然而，我们的分析并不能与这一结果相吻合。我们实验中所引用的新浪微博服务有2 000 个关注的上限限制，导致了出度图中的数量截止现象的产生，这也导致了我们的频度分布与之前研究的差异产生。

图 1 入度分布

图2 出度分布

我们也对用户的粉丝数与关注数之间的关系进行了分析，如图3所示。 图中显示了一个很有趣的现象：对于那些拥有中等数目粉丝(粉丝数<=1 000)的用户，关注数与粉丝数呈现一个线性关系；然而，当粉丝数大于1 000之后(具有一定影响力的节点)，关注数与粉丝数之间的关系则不再是之前的线性关系，而变得相对复杂分散。影响力节点的关注行为相对分散，一部分用户仅仅关注他们感兴趣的用户；另一部分用户出于相互关注的礼貌性行为而关注更多的人,礼貌性互相关注行为被文献[8]所验证。图4展示的发文情况也大致符合幂率分布。

图3 入度与出度关系

图4 发文分布

3.2 强连通关系

基于已有社会网络，我们随机选取用户节点作为种子节点并使用广度优先策略进行强连通分析。关系网络中的节点可分为：IN、OUT、SCC与ISOLATE 四类。其中，SCC是关系网络中的一个最大强连通分支，分支中的任一节点到另一节点均存在至少一条可抵达的有向路径；IN集合中的任一节点都存在至少一条前向可抵达路径可以到达SCC中的任一节点，而不存在后向可抵达路径；OUT集合中的任一节点都存在至少一条后向可抵达路径可以由SCC某一节点抵达，并且不存在前向可抵达路径；ISOLATE集合也称为可分离集合，其与IN、OUT与SCC集合均不可以互相抵达，是相对独立的集合。

与Web网络的“蝴蝶结”形状不同[14]，社会网络图的连通关系更像一个纺锤体结构(图5)。基于我们收集到的2 631 342个用户节点的社会关系图，最大的强连通分支包含了2 161 844 个用户，占总用户数的82.15%。在社会关系图中，绝大多数的用户都处在最大强连通子图中，而且处于可分离集合的用户占了很小的比例，这可能与社会网络的社会属性有很大的关系。社会网络中用户的趋同性使得用户之间的连通关系加强。

图5 连通关系图

4 社会网络的影响力模型

基于在线社会网络的特点，我们将社会网络用户的影响力定义为：在某个特定的时间段内这一用户的发文被整个社会网络其他用户阅读到的概率。令整个社会网络为S，用户u的影响力定义为式(1)。

(1)

其中Read(u,v)表示用户u的发文被用户v浏览到的概率，其主要与用户u的发文生成函数G(u)、用户v的信息接收函数O(v)、用户u到用户D(u,v)的信息传播函数等因素相关。在接下来的工作中，我们分别基于不同的假设提出不同的影响力模型。

FLM(Follower Limited Model)模型：用户u的社会影响力由他的粉丝集合的浏览概率Read(u,v)累加形成。对于任一粉丝v，不妨假设v的关注集合Att(v)={a1,a2,...,an},同时u属于Att(v)，即v关注了u。那么用户u对用户v的影响力Inf(u,v)可以量化表示为用户u的发文被用户v浏览到的概率。FLM模型中用户u的影响力可以形式化定义为式(2)。

(2)

用户u的影响力由其所有的粉丝到用户u的阅读概率累加而成。FLM模型从用户的发文角度对用户的影响力进行刻画。

SWDM(Small World Diffusion Model)模型：对于用户u的任一粉丝v而言，如果u与v同属于一个小世界群体，我们认为他们之间的信息传播呈双向传递趋势，u到v的影响力扩散大小与这两个用户现有的影响力差值成正比；如果不存在同一群体，则信息传播更加偏向于单向传递，其影响力的扩散差值取决于用户u的影响力。SWDM模型的形式化定义如下：

• 如果u与v同属于某个小世界群体(同时编辑了某个标签)且v关注了u，则用户u到v的影响力扩散值见式(3)：

(3)

• 如果他们不属于小世界群体，仅仅存在着关注关系(v关注u)，则用户u到v的影响力扩散值为式(4)：

(4)

接着，我们对FLM与SWDM进行线性迭代，形成了PTIM (Posting and Tagging Incorporated Model)模型，它将用户的发文行为和标签信息引入到影响力模型中。

5 模型评估分析

在本文中，我们将选取前人类似的评价方法对影响力模型的性能进行评价。首先，我们对比不同模型得到的最有影响力的前N个用户，并进行影响力对比分析；接下来，我们将分析不同模型的影响力排名下用户粉丝数、获得认证的人数等特征的召回情况；最后，我们人工选取并标注了一部分用户的影响力相对关系，并对不同模型的相对影响力识别性能进行评估。

5.1 最具影响力节点的方法评估

最具影响力用户的定位研究，如何挑选最少的(符合一定规模的)用户，可以影响覆盖到最多的用户，是在线社会网络的一项重要工作，在广告推广、市场营销等领域有着广泛的应用前景。我们将最具影响力节点识别作为我们的评估方法之一。表1列出了不同的社会影响力模型下计算出来的前五个最具影响力用户。

表1 不同模型下前五个最具影响力的用户

FLM模型的最具影响力节点与其他四个模型结果相差最大。FLM模型的影响力主要由两部分决定：用户发文数以及用户的粉丝数，越高的发文数与粉丝数形成了用户越大的影响力。用户的发文行为是衡量社会影响力的一个重要方面，FLM 模型将用户的发文行为量化地引入到了社会影响力的模型中。SWDM模型与TrustRank 模型的前五 位影响力最高的用户均为娱乐或者行业的名人，PageRank与PTIM模型的结果相对比较多元化。“冷笑话精选”与“头条新闻”在PageRank模型中分列影响力第四与第五位，他们分别以发笑话或者热门事件相关内容为主，经常有着很大的转发量，对于公众而言有着广泛的影响力。

PTIM模型的结果最具多样化，前五个最具影响力的用户分散在不同的领域，覆盖更广泛的人群。PTIM模型将用户的发文行为、用户链接关系与标签的社区行为等因素均考虑入内，因此，它在识别最具影响力用户上表现出了很好的性能。

5.2 粉丝数目与认证用户特征的交叉评估

用户粉丝数一直被认为是在线社会网络的影响力评估的一个重要特征。我们以多粉丝用户与少粉丝用户的识别作为评估指标之一。在我们的实验中，如果一个用户的粉丝数大于5 000，则我们称之为多粉丝用户；如果粉丝数少于100，则我们称为少粉丝用户。我们将对我们的模型对于多粉丝用户与少粉丝用户的甄别情况进行对比分析。

图6(a)列出了五种模型在不同的影响力排名下对于多粉丝用户的甄别情况。在同等影响力排名情况下，多粉丝用户占到的比例越多，则可以认定其对影响力较大的用户识别效果越好。结果显示FLM 模型识别的多粉丝用户要明显少于其他四种模型，其他四个模型在多粉丝用户的识别上有着相似的性能，PageRank模型在少粉丝用户的识别上性能最差。少粉丝用户的识别性能对比见图6(b)图。通常意义上，少粉丝用户中有相当大的比例是属于不活跃用户、新用户或者僵尸用户，这些用户通常的在线社会影响力较小，其排名越靠后，则模型的识别效果越好。图6(b)显示PageRank 模型对于这类少粉丝用户的识别效果较差。与Web中网页重要性一样，TrustRank模型仍旧在识别小粉丝用户上体现除了很好的性能。PTIM模型在这类用户的识别上体现出了卓越的性能。结果表明发文行为、标签与链接关系等特征的结合对于衡量用户影响力起着至关重要的作用。

图6 不同模型对多粉丝用户、少粉丝用户与认证用户的识别情况

名人身份认证策略是微博服务的独特的特征之一，新浪微博中现有超过三亿的注册用户，其中认证用户约30万。通常意义上来讲，认证名人都具有较高的影响力。本文也对不同模型的认证用户识别情况进行了对比，结果见图6(c)。PTIM模型与FLM模型中都将发文行为作为重要的特征之一引入到影响力的构建中，这样很容易给予那些发文很多的营销或者广告用户一个很好的影响力得分。在同等情况下，TrustRank模型与SWDM模型对于认证用户的识别效果最佳，FLM模型与PTIM效果较差。SWDM模型是基于在线社会网络的小世界属性而提出假设建立的。认证用户之间的互相关注强，存在着明显的小世界属性，这与我们的实验结果刚好吻合。

5.3 基于人工标注的用户影响力相对关系评估

粉丝数目、认证用户识别等都是社会网络评估用户影响力重要的特征，另外，我们也基于人工标注的用户影响力对的方法进行进一步的评估。首先，我们选择十个具有代表性的标签(代表着不同的用户群)，它们分别是“音乐”、“摄影”、“清华大学”、“数据挖掘”、“法律”、“电影”、“互联网”、“中医”、“心理学”等。这些标签覆盖了传统意义上的自然科学、社会科学、人文艺术和其他热门领域，因此其有一定的代表意义。在这十类的标签用户集合中，我们随机抽取部分认证用户并进行随机不重复进行配对组合作为我们的实验评估集合。我们总计收集到1 345对认证用户并将其进行人工标注。两个经过专业训练的标注人员完全独立地对这些抽取出来的用户对的相对影响力大小进行标注。对用户的相对影响力定义如下：如果前者的影响力明显大于后者，则标记为1；如果明显小于后者，则标记为-1，如果不能区分或者无明显差异，则标记为0。这两个标注人员的Kappa 系数为0.84。

我们基于人工标注之后的用户相对影响力情况对不同模型的性能进行评估，实验对比结果见图7。对于“法律”标签，FLM模型体现了最好的性能，发文行为在法律领域对于用户影响力的识别起到了更加至关重要的作用。这可能与“法律”这一小世界高度专业集中且专家易识别有关，结果显示发文情况在社会影响力的评估中显得尤为重要。"音乐"是最大的用户社区，有195 542个用户将其作为他们的标签之一,用户分布分散复杂。实验结果显示FLM模型在音乐领域的性能很差，标签关系、关注链接信息对于衡量用户影响力是非常重要的。PTIM模型将以上的这些特征有效地结合起来，在“音乐”群体中性能最好。

图7 基于人工标注的用户相对影响力在不同模型的性能情况

总体而言，PTIM模型在大多数标签集合上均表现出了较好的性能，PageRank与TrustRank模型在各个用户集合中有相似的性能。实验结果对比显示不同的影响力模型在不同的用户群体中所表现的性能也截然不同，这与不同的标签集合中用户影响力与不同的因素影响有很大的关系。PageRank与TrustRank模型主要将用户链接关系信息以不同的形式引入；FLM模型与SWDM模型分别仅仅侧重用户的发文行为、小世界属性，性能相对不稳定。PTIM模型将发文行为、链接关系、小世界属性等有效地结合起来，在各种评估指标均表现出了相对稳定的性能。

6 总结与展望

本文中，我们首先分析了大规模在线社会网络的图结构关系，社会网络的强连通关系呈现“纺锤体”形状。我们引入了用户的阅读概率从用户的发文、浏览等行为对社会影响力进行建模。我们使用用户粉丝数、认证用户数等常见的传统特征对模型的实验结果进行交叉评估，并基于人工标注的用户相对影响力关系对进一步对比不同影响力在不同领域的变化情况。PTIM模型将用户的发文行为、小世界属性与用户关注关系进行有效融合，性能表现稳定。

尽管我们的模型取得了一定的成效，仍旧存在一些问题亟需改进。我们在引入小世界属性时扩散方式单一，然而实际情况下不同社区的信息扩散很复杂，未来我们将引入不同的扩散函数；另外，不同的用户的影响力因素也不尽相同，区分不同用户适用不同的影响力模型也是我们未来的主要研究工作之一。

[1] 中国互联网络信息中心. 第31次中国互联网络发展状况统计报告[R], 2013.

[2] A Anagnosopoulos, R Kumar, M. Mahdian. Influence and correlation in social networks[C]//Proceedings of the 14th ACM International Conference on Knowledge Discovery and Data Mining, 2008: 7-15.

[3] D Kempe, J M Kleinberg, E Tardos. Maximizing the spread of influence through social network[C]//Proceedings of the 9th ACM International Conference on Knowledge Discovery and Data Mining, 2003, 137-146.

[4] P F Lazarsfeld, B Berelson, H Gaudet. The people’s choice: How the voter makes up his mind in a presidential campaign[M]. Columbia University Press, 1944.

[5] W Chen, Y Wang, S Yang. Efficient influence maximization in social network[C]//Proceedings of the 15th ACM International Conference on Knowledge Discovery and Data Mining, 2009.

[6] J R P French, B Raven. The bases of social power[J]. Studies in Social Power, 1959： 150-217.

[7] J Tang, J Sun, C Wang， et al. Social influence analysis in large-scale networks[C]//Proceedings of the 15th ACM International Conference on Knowledge Discovery and Data Mining, 2009.

[8] J Weng, E Lim, J Jiang, et al. TwitterRank: finding topic-sensitive influential Twitters[C]//Proceedings of the 3th ACM International Conference on Web Search and Data Mining, 2010: 1-10.

[9] G R Manuel, L Jure, L Andreas. Inferring networks of diffusion and influence[C]//Proceedings of the 16th ACM International conference on Knowledge Discovery and Data Mining, 2010: 141-150.

[10] N Friedkin. A structural theory of social influence[M]. Cambrige University Press, 1998.

[11] L Pages, S Brin, R Motwani, et al. Wingorad. The page rank of citation ranking? Bringing order to the Web. Technical report, SIDL-WP-1999-0120, Standford University, 1999.

[12] L Li, Y Shang, W Zhang. Improvement of HITS-based Algorithms on Web documents[C]//Proceedings of the 11th International World Wide Web Conference.2002: 35-44.

[13] Z Gyongyi, H Garcia-Molina, J Pedersen. Combating Web spam with TrustRank[C]//Proceedings of the 30th VLDB Conference, 2004: 576-587.

[14] A Broder, R Kumar, F Maghoul, Graph structure in the Web[C]//Proceedings of WWW2009, 2009.

Study on User Influence in Online Social Networks

XU Danqing, LIU Yiqun, ZHAMG Min, MA Shaoping

(State Key Lab of Intelligent Technology and Systems, Tsinghua National Laboratory for Information Science and Technology, Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China)

Based on the large-scale social network dataset, this paper conducts a multi-feature statistical analysis on graph structure and finds that the indegree, outdegree and posts of social networks generally fit power law distribution. The “small-world” property makes the strongly connected structure of social network show the “spindle” shape. Furthermore, this paper incorporates users’ posting behaviors, browsing behaviors and social communities’ properties into social influence modelings. Experimental results show that the PTIM model combining users’ behaviors and link relationships has a stable performance on identifying the numbers of fans, authenticated users, the relative influence of users’ pairs and other indices.

social influence, small world, information diffusion, social network

许丹青(1987—)，硕士。E⁃mail：xudanqing06@gmail．com刘奕群(1981—)，博士，副教授，主要研究领域为信息检索与用户行为分析。E⁃mail：yinqunliu@tsinghua．edu．cn张敏(1977—)，博士，副教授，主要研究领域为信息检索与推荐系统。E⁃mail：z⁃m@tsinghua@edu．cn

1003-0077(2016)02-0083-07

2013-10-15 定稿日期： 2014-04-15

国家863高科技项目(2011AA01A205)；国家自然科学基金(60903107，61073071)

TP391

A