考虑用户和传播属性的节点影响力评估算法*

尚 焱,樊欣唯，于 洪

(北京邮电大学信息物理融合实验室，北京 100876)

考虑用户和传播属性的节点影响力评估算法*

尚 焱,樊欣唯，于 洪

(北京邮电大学信息物理融合实验室，北京 100876)

在微博的传播过程中，关键节点起着意见领袖的作用，在社交网络中发现关键节点对舆情的分析、控制等方面是非常有意义的，作为社交网络的传播节点，用户不仅与用户本身属性有关，还与微博消息的传播属性有关。对两种属性分别选取三个指标，利用层次分析法中构造判断矩阵的方法评估各个指标的权重，将用户系数和传播系数分别作为传播网络的节点和边的权值，形成双加权的网络拓扑图，然后建立考虑用户和传播属性的影响力评估算法来计算转发节点的影响力。通过与现有算法进行比较，表明本文的算法能够更加客观准确地评估关键节点在传播过程中的重要程度。

关键节点；用户系数；传播系数；层次分析法；NodeRank算法

1 引言

微博是一种通过关注机制[1]分享简短实时信息的广播式的社交网络平台，由于其自身的社交模式，决定了微博信息的传播是爆炸式的，而在传播过程中关键节点[2]是传播影响力的决定因素，合理客观地评估关键节点的影响力在控制消息的传播、舆论形势分析等方面具有重大的意义。微博的消息传播是通过产生转发关系进行的，整个传播过程可以抽象为网络拓扑图[3]，该图的节点是转发用户，图的边表示转发关系，在整个拓扑结构中，通过相应算法进行节点影响力评估，从而发现传播过程中的关键节点，为进一步进行舆情的分析与控制提供线索。

现阶段评估网络拓扑图中重要节点的方法有很多，其中大多数方法都是将传播过程抽象为网络拓扑结构，基于节点的度[4]、统计分析方法[5]、互信息的方法[6]以及Google的PageRank网页排名算法[7]。这些经典的算法都可以在不同维度上评估节点的重要程度，但是依然各有其局限性，由于评价指标单一，并没有真正考虑更加丰富的用户信息和传播过程中的因素，并不具备较高的客观性和真实性。其中PageRank算法在衡量关键节点具有独特的优势，该算法用于衡量特定网页相对于搜索引擎索引中的其他网页而言的重要程度，这和微博传播中的节点关系相类似。基于此思想构建了考虑用户和传播属性的节点影响力评估模型并提出了NodeRank算法，然后将微博的传播过程抽象为网络拓扑图，在真实的微博传播过程中，由于转发用户的属性和微博传播的属性存在差异，产生不同的影响效果。因此，微博的传播网络应该是一个节点和边都具有权值的加权传播网络，利用本文的NodeRank算法计算关键节点影响力，然后结合微博可视化工具，将实验结果与现有的算法结果进行对比，表明NodeRank算法可以更加准确合理地评估关键节点的影响力。

2 评估模型

用户属性和传播属性对微博的传播存在着不同的影响效果，消息传播属性更加依赖于微博的内容，用户属性则更加依赖用户本身的某些特性。本文中用户系数表示用户的属性，传播系数表示微博传播过程的属性，然后基于多目标决策的思想计算用户属性的系数和传播属性的系数，将网络传播拓扑图的节点和边分别赋予用户系数和传播系数，从而变为加权网络，然后通过NodeRank算法进行关键节点的挖掘与评估。用户自身属性包括是否通过V认证、粉丝量、好友数、评论量和转发量等特征，在消息传播过程中，不同属性的用户具有不同的影响力。本文选择活跃度[8]、关系强度[9]和权威系数作为衡量传播属性的指标，计算出用户系数作为传播网络节点的权值。微博传播过程中，由于传播过程的某些因素存在差异，比如用户的偏好[10]、爆炸性内容等造成不同类型的微博传播速度、互动程度[11]和转发层级不同，从而造成传播过程的差异。本文选择转发速度、传播深度和交互指数作为衡量传播属性的指标，计算传播系数作为传播拓扑网络边上的权值。

2.1 用户属性指标

2.1.1 活跃度

微博用户相同时间内发布的微博数越多，说明该用户活跃程度越高，相比其他用户该用户的影响力越强，将用户平均每天发布的微博数目定义为用户的活跃度，用来衡量用户的活跃程度，记为A(Activeness)。

(1)

其中，WC(Weibo Counts)为用户已发布的微博数,t1为用户注册时间,t2为微博发布时间。

2.1.2 关系强度

基于效用函数思想，将用户的好友数与粉丝数的比值取负对数变换定义为关系强度，记为RI(Relation Intensity)。该指标衡量用户的社交属性，当该值大于0时，用户与其他人之间呈现一种弱关系，该用户更加趋向于自媒体特性，具有自媒体特性的用户大都是信息的生产者，影响力相对较大；相反，该值小于0时，说明该用户与其粉丝呈现“强关系”，也就意味着该用户在真实生活里相识的概率更大，与其他用户之间在线下具有真实的社交关系，这种用户更加趋向于社交特性，大都是信息的消费者，其影响力也就相对较小。

(2)

其中,FLC(Follower Counts)为用户粉丝数,FRC(FRiends Counts)为用户好友数。

2.1.3 权威系数

用户是否经过认证对其影响力有着显著的影响。通常来讲，认证用户更容易赢得其他用户的信任，其影响力显然比普通用户要大。通过统计认证用户的关系强度，发现大多数认证用户趋向于“弱关系”，也就是说，认证用户大多趋向自媒体特性，这与微博的认证条件相符合。用户认证条件是有一定知名度的演艺、体育、文艺界人士、在公众熟悉的某领域内有一定知名度和影响力的人、知名企业、机构、媒体及其高管，或者重要新闻当事人。通过认证的用户其影响力普遍高于普通用户，将认证用户与普通用户赋予不同的系数。是否通过认证定义为权威系数，记为AI(Authority Indicator )。

(3)

2.2 传播属性指标

2.2.1 转发速度

微博的传播依靠的是与其他用户产生转发关系，当产生转发关系时，微博消息才会传向下一级网络，才会对下一级用户产生影响。如果某微博消息传播速度越大，即单位时间内产生的转发关系越多，说明其影响力也越大。将单位时间内转发关系产生的个数定义为转发速度，记为RV(Report Velocity)。

(4)

其中,t为微博传播时间，CN(Comment Number)为微博评论量。

2.2.2 传播深度

微博消息被连续转发的次数越多，说明该微博的传播层级越大，传播层级越大说明该条微博传播深度越深，影响程度也越大，这里所讲的传播层级并不是任意一个用户转发次数，而是转发用户相对于原微博经历的连续转发次数，将所有转发用户中的最大连续转发次数定义为绝对传播深度。将某用户所处的传播层级与绝对传播深度的比值定义为相对传播深度，记为PD(Propagation Depth)。

(5)

其中,Lmax表示传播过程中的绝对传播深度，Li表示第i个用户相对于原微博所在的转发层级。

2.2.3 交互指数

微博的评论数或者转发数可以说明该微博的受关注程度，同时也说明该微博内容更符合某些用户的偏好。另一方面，具有自媒体特性的用户和具有社交属性的用户由于被关注量和好友数的不同产生的交互程度存在差异，该指标又与用户的关系强度有关。将交互指数定义为总的转发评论量与该用户好友数的比值，记为IC(Interaction Coefficient)。

(6)

其中,CN(Comment Number)为微博评论量,FRN为用户的好友数。

2.3 用户和传播影响系数

在微博节点的影响力评估过程中，对两种影响系数分别选择三个属性，为了确定用户属性和传播属性的权值，采用多目标决策分析法的思想，将三个评价指标合成为一个权值，并对每个指标数据进行归一化处理，使得两个权值落在相同的区间内。这种处理方法并不影响数据之间的相关性，能够保证原始数据的真实情况。通过分析得知，各个指标之间具有相关性，并且互相不可替代，适合用加法规则综合评定。为了使得属性权值更加准确，采用层次分析法[12]中构建判断矩阵的方法来评估各个指标的权重。构建用户属性和传播属性的判断矩阵分别记为A和B。

经过Matlab编程计算得到，用户属性的活跃度、关系强度、权威系数的权重分别为0.070 2、0.370 7、0.559 0，传播属性的传播速度、传播深度、交互指数的权重分别为0.671 6、0.265 4、0.062 9。将用户系数和传播系数分别定义为U和V，计算公式如下：

U=0.0702A+0.3707RI+0.5590AI

(7)

其中，U为加权网络拓扑图中的节点权值；A、RI、AI分别为公式(1)～公式(3)确定的用户属性的指标数值。

V=0.6716RV+0.2654PD+0.0629IC

(8)

其中，V为加权网络拓扑图中的边的权值；RV、PD、IC分别为公式(4)～公式(6)确定的传播属性的指标数值。

3 NodeRank算法

3.1 算法思想

基于PageRank的算法思想，提出考虑用户和传播属性的节点影响力评估算法，本模型的基本思想是：将节点的转发概率作为阻尼系数[13]，用来表征消息的传播概率[14]。同时，将用户系数和未转发概率的乘积值平均分配给未转发的用户，即未转发情况下，将节点的用户影响力平均分配给每个可能转发的关注者。在转发情况下，节点的所有转发用户的影响力和传播系数加权之后再求和，即边权乘上产生转发关系的用户影响力之和。该算法刻画出了转发过程中用户之间的转发关系，并且考虑了用户特性和传播状况，更加准确客观地评估了传播过程中节点的真实情况，同时反映了转发关系的重要性，体现了用户属性的影响程度，更加全面真实地评估了关键节点的影响力。

(9)

其中，P(i)是第i个节点的转发概率，公式如下：

(10)

以上两式中：ni为节点i的转发量，N为总的转发量，I(i)是第i个节点的综合影响力，I(j)是第j个转发节点的综合影响力，Ni是第i个节点的粉丝数，Sj是转发该用户微博的用户集合。

由式(7)得，Ui是第i节点的用户系数；由式(8)得，Vij是第i节点到第j节点的传播系数。

3.2 算法实现

根据用户和传播属性评估模型，得到用户系数和传播系数，也就得到了拓扑传播网络中节点的权值和边的权值。设加权传播网络为图G=(M，N)， 其中，M是所有节点的集合，即转发用户的集合；N是所有边的集合，即转发关系的集合，每一条边代表一次转发关系。根据加权之后的网络传播图，利用微博工具所提供的原始数据，将NodeRank算法代入进行关键节点的挖掘和评估。

Step 1 将采集到的数据带入用户和传播属性评估模型，得到六个指标的计算数值；

Step 2 利用Min-Max 标准化方法对六个指标的原始数据进行标准化处理，并利用层次分析法中构建判断矩阵的方法计算各个指标权重；

Step 3 将用户属性和传播属性的三个指标分别代入式(7)和式(8)得到用户影响系数和传播影响系数；

Step 4 构建加权传播网络图G=(V，U)，得到转发关系；

Step 5 通过式(10)各个节点的转发关系计算第i个节点的转发概率P(i)；

Step 6 将以上得到的指标数值代入NodeRank算法公式(9)计算各个用户的影响力；

第一，要立足于“我国是工人阶级领导的，以工农联盟为基础的人民民主专政的社会主义国家”的国家性质上，坚持“人民是国家的主人”原则，始终站在人民群众（即思想政治教育的受教育者）的根本立场上，做合乎民族的、符合人民群众的根本利益的思想政治教育工作。

Step 7 根据计算出的各个用户的影响力从大到小排序，得到最终影响力排序。

由以上步骤得知，该算法的复杂度主要集中在Step 6，虽然基于PageRank算法大大降低了计算的复杂度，但是对于微博这种实时的传播事件还要求进一步提高算法的效率，下一步的研究方向偏向于这方面内容。

4 实验结果

4.1 数据来源

WeiboEvents[15]是北京大学可视化与可视分析研究组开发的微博传播分析工具，通过直观的视图清晰地呈现出一个事件中微博转发的过程，能够迅速地发现事件中的关键人物、关键微博、重要观点，同时通过可视化的方式帮助更好地分析微博中事件的发生与发展过程，并可以下载文中各指标的原始数据。利用WeiboEvents，将原创微博的URL输入到该工具中，通过后台的采集得到原始数据，并通过可视化分析为下一步的算法分析奠定基础。

4.2 数据预处理

利用Min-Max 标准化方法对六个指标的原始数据进行标准化处理，消除不同指标数据之间因量纲不同带来的数值级数上的影响，并且Min-Max标准化方法保留了原始数据之间的相关关系。Min-Max标准化方法是对原始数据进行线性变换。具体算法如下：

设Xmin和Xmax分别为某种属性的最小值和最大值，将属性的一个原始值X通过Min-Max标准化映射成在区间[0，1]的值X′，其公式为：

4.3 计算结果及可视化分析

通过对原始数据的处理和模型的计算结果，将结果代入到本文的影响力评估算法中，计算得到七个影响力较大的关键节点，这七个节点的用户系数、传播系数、节点的转发概率以及最终的影响力和排序结果如表1所示。

Table 1 Results of the NodeRank algorithm

由表1可得，“21世纪经济报道”具有最大的影响力，这与图1的可视化结果相符合，这也不难解释，因为该用户是原创微博，属于内容的生产者，所以影响力最大。由于该微博经过“李开复”的转发形成二次较大的爆发，其引起的转发量比原创微博还要略高，但由于其传播影响系数较低，使得综合影响力并不突出，“薛蛮子”影响力排第三，该结果与图1和图2的可视化结果完全一致。由图1和图2所示，“洪晃ilook”具有第四影响力，但结果却排在“李佳佳Audrey”之后，原因是李佳佳节点是引起微博二次爆发至关重要的连接节点，正是由此节点之后的转发才引起了大规模的二次爆发，而在“薛蛮子”之后爆发规模并不大，所以该节点应比“薛蛮子”更重要，即若没有此节点，就没有该微博消息的第二次较大规模的爆发。

Figure 1 Hierarchy chart of a broadcast tree图1 树状转发层次图

Figure 2 Topological graph of Weibo spread图2 微博传播网络拓扑图

对比发现，“李佳佳Audrey”的用户影响系数和传播影响系数均为最低，说明本文的算法可以挖掘关键节点。用户“朱骏”的用户影响系数比“21世纪经济报道”要高，但由于其传播影响系数与其相差悬殊，导致“朱俊”影响力并不大。用户“环保董良杰”的转发量比用户“洪晃ilook”要大，但是其用户影响系数和传播影响系数都比“洪晃ilook”小，导致其综合影响力偏小。通过对各个用户的对比分析表明，本文的算法可以更加准确、合理、客观地评估用户影响力，其排序结果与可视化结果一致，并且可以挖掘关键节点，计算结果可以作为舆情分析等工作的参考。

4.4 不同算法的对比分析

在理论介绍部分，已经介绍了几种经典的评估节点重要程度的算法，这些算法都从不同角度进行影响力评估。我们选择基于节点的度、互信息算法和PageRank算法三种经典算法与NodeRank算法进行对比，通过Matlab编程和Excel数据处理最终得到三个对比算法的计算结果，如表2所示，对三种算法的计算结果进行排序得到最终影响力的排名，如表3所示。

Table 2 Computational results of different algorithms

通过与基于节点的度和互信息算法的对比，我们发现：两种对比算法都将用户“李佳佳Audrey”排在最后，通过分析可知，该用户是连接两次大规模爆发的关键节点，重要程度明显不小，说明本文算法更加合理。进一步与基于互信息的算法对比，当除去用户“李佳佳Audrey”时，与本文算法计算

Table 3 Sorted results of different algorithms

结果完全一致，说明两种算法在计算爆发量比较大的用户影响力时，准确性是相当的，而基于互信息的算法对于爆发量相对较小的重要节点的挖掘不够准确。

通过与传统的PageRank算法对比发现：传统的PageRank算法认为用户“李佳佳Audrey”是最重要的，说明该算法在发现关键节点上具有良好的准确性，但该结果有失客观性，该用户为关键节点但并不比爆发量较大用户更具影响力。对比发现，基于NodeRank算法更胜一筹，基于节点的度和互信息算法并不可以发现用户“李佳佳Audrey”的重要性，将其排在最后，PageRank算法又低估了爆发节点的影响力，而NodeRank算法既可以发现关键节点又准确地评估了爆发节点，说明本文的算法更具有客观性、合理性和准确性。

5 结束语

本文基于PageRank算法思想，提出了一种考虑用户和传播属性的节点影响力评估算法——NodeRank算法。利用微博分析工具进行数据采集和可视化分析，将传播网络抽象为双加权拓扑网络，根据WeiboEvents所提供的原始数据，将算法代入，对传播过程中的关键节点进行挖掘和评估。通过与现有三种经典算法的实验对比，NodeRank算法具有较好的准确性，能够发现至关重要的关键节点和极具影响力的爆发节点，并客观地评估其重要程度。对于实时的微博事件，计算的复杂度还有待提高，降低计算复杂度以便快速高效地挖掘关键节点，将是下一步研究的重点。

[1] Wang Xiao-yun.Research on the mechanism of following-based topics of microblogging social network [D]. Wuhan:Huazhong University of Science &Technology,2013.(in Chinese)

[2] Sahelices-Pinto C,Rodríguez-Santos C. E-WoM and 20 opinion leaders[J].Journal of Food Products Marketing,2014,20(3):244-261.

[3] Zhao Ying,Yi Ping-ke.A dynamic worm propagation model based on social network [J].Computer Engineering & Science,2013,35(12):34-38.(in Chinese)

[4] Qiu Jun,Liu Gong-shen. A relationship-based importance algorithm for micro-blog network system [J]. Information Security and Communications Privacy,2013,1(1):51-53.(in Chinese)

[5] Yu Hong,Yang Xian. Information propagation on microblogging using statistical analysis technique [J]. Digital Communication,2013,40(2):6-10.(in Chinese)

[6] Zhang Yi,Liu Yu-hua,Xu Kai-hua,et al. Evaluation method for node importance based on mutual information in complex networks [J]. Computer Science,2013,38(6):88-109.(in Chinese)

[7] Li Xing,Zhong Zhi-nong,Jing Ning,et al.Reaserch on community detection method [J]. Computer Engineering & Science,2012,34(9):154-159.(in Chinese)

[8] Wang Chen-xu,Guan Xiao-hong,Qin Tao,et al.Who are active? An in-depth measurement on user activity characteristics in Sina microblogging[C]∥Proc of Global Communications Conference (GLOBECOM),2012:2083-2088.

[9] Han Zhong-ming,Yuan Li-ling,Yang Wei-jie,et al. Algorithm for discovering influential nodes in weighted social networks [J]. Computer Applications,2013,33(6):1553-1557.(in Chinese)

[10] Kandiah V,Shepelyansky D L.PageRank model of opinion formation on social networks[J].Physica A:Statistical Mechanics and its Applications,2012,391(22):5779-5793.

[11] Li Xiang,Cheng Shao-yin,Chen Wen-long,et al. Novel user influence measurement based on user interaction in microblog[C]∥Proc of 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), 2013:615-619.

[12] Liu Xin-xian，Zhu Dao-li. Selection and judgment:AHP [M]. Shanghai:Shanghai Science Popularization Press,1990.(in Chinese)

[13] Chen Wen-long,Cheng Shao-yin,He Xing.InfluenceRank:An efficient social influence measurement for millions of users in microblog [C]∥Proc of the 2nd International Conference on Cloud and Green Computing / 2nd International Conference on Social Computing and its Applications,2012:563-570.

[14] Wang Jin-hui，He Li-jian，Zhang Wei，et al. Research of user preference based information dissemination in microblog [J]. Computer Engineering & Science,2013,35(3):140-144.(in Chinese)

[15] Ren Dong-hao,Xin Zhang,Wang Zhen-huang,et al. WeiboEvents:A crowd sourcing Weibo visual analytic system[C]∥Proc of 2014 IEEE Pacific Visualization Symposium (PacificVis) Notes,2014,:330-334.

附中文参考文献:

[1] 王小云.基于主题的微博社会网络关注机制研究[D]. 武汉:华中科技大学,2013.

[3] 赵英,易平科.基于社交网络的蠕虫动态传播模型[J].计算机工程与科学,2013,35(12):34-38.

[4] 仇钧,刘功申.基于关系的微博重要度算法研究[J].信息安全与通信保密,2013,1(1):51-53.

[5] 于洪,杨显.基于统计分析的微博信息传播规律研究[J].数字通信,2013,40(2):6-10.

[6] 张翼,刘玉华,许凯华,等.一种基于互信息的复杂网络节点重要性评估方法[J].计算机科学,2013,38(6):88-109.

[7] 李星,钟志农,景宁,等.社区挖掘技术研究[J].计算机工程与科学,2012,34(9):154-159.

[9] 韩忠明,苑丽玲,杨伟杰,等.加权社会网络中重要节点发现算法[J].计算机应用,2013,33(6):1553-1557.

[12] 刘新宪，朱道立. 选择与判断：AHP[M].上海:上海科学普及出版社,1990.

[14] 王金辉，贺利坚，张伟，等.微博中基于用户偏好的信息传播研究[J].计算机工程与科学,2013,35(3):140-144.

尚焱(1990-),男,山东宁津人，硕士生，研究方向为Web 搜索和数据挖掘。E-mail:shang.yan@foxmail.com

SHANG Yan,born in 1990,MS candidate,his research interests include web search, and data mining.

樊欣唯(1992-),女,上海人，硕士生，研究方向为数据中心网络路由策略。E-mail:20151202026t@cqu.edu.cn

FAN Xin-wei,born in 1992,MS candidate,her research interest includes routing policy of data center network.

于洪(1972-),女,重庆人，博士，副教授，CCF会员(E200010612M)，研究方向为数据挖掘、粗糙集理论和Web智能等。E-mail:yuhongcq@aliyun.com

YU Hong,born in 1972,PhD,associate professor,CCF member(E200010612M)，her research interests include data mining, rough set theory, and web intelligence.

A novel node influence measurement algorithm based on characteristics of users and propagation

SHANG Yan，FAN Xin-wei，YU Hong

(Laboratory of Cyber-Physical Systems,Beijing University of Posts and Telecommunications,Beijing 100876,China)

During the spreading process of microblogs, key nodes play an important role as “attitude leaders”. It is essential to figure out those key nodes for analyzing and monitoring public sentiments. As propagation nodes, users’ variety not only depends on their own characteristics, but also the characteristics of propagation. We select three indicators among two characteristics and adopt the evaluation array of the analytic hierarchy process to assess these indicators. User coefficient and propagation coefficient are used as the node weight and the edge weight respectively, thus forming a double weighted topological graph. Then we establish a novel node influence measurement algorithm of nodes based on the characteristics of users and propagation to evaluate the influence of each node. Compared with existing algorithms, the proposed algorithm can evaluate the importance of key nodes more accurately and objectively during propagation process.

key nodes;user coefficient;propagation coefficient;analytic hierarchy process;NodeRank algorithm;

1007-130X(2015)11-2105-07

2015-01-07;

2015-08-11

国家自然科学基金资助项目(61379114)

TP391

A

10.3969/j.issn.1007-130X.2015.11.017

通信地址：100876 北京市海淀区西土城路10号北京邮电大学信息物理融合实验室教四

418Address:Laboratory of Cyber-Physical Systems，Beijing University of Posts and Telecommunications,Beijing 100876,P.R.Chin