基于用户行为和结构洞的用户影响力评价模型

魏建冬 覃锡忠 贾振红 牛红梅

关键词： 用户影响力; 非冗余信息; 用户行为; 结构洞; 网络约束系数; 覆盖率

中图分类号： TN911?34; TP393                    文献标识码： A                     文章编号： 1004?373X（2019）05?0164?05

User influence comprehensive evaluation model based on user behavior

and structure hole principle

WEI Jiandong1， QIN Xizhong1， JIA Zhenhong1， NIU Hongmei2

（1. College of Information Science and Engineering， Xinjiang University， Urumqi 830046， China;

2. Department of Network Monitoring， China Mobile Communications Group Xinjiang Limited， Urumqi 830046， China）

Abstract： Since the non?redundant information is not fully considered in current most user influence measurement methods， the user influence comprehensive evaluation model based on user behavior and structure hole principle is constructed. The user behavior is quantified， and integrated into the edge weight of the network. On this basis， the network constraint coefficients are improved by means of structural hole method to consider the influence of user behavior on the edge weight of the network， and solve the problem of three?layer topological relationship among the node， adjacent node and subjacent node. The user influence comprehensive evaluation model is constructed， and verified with the data from Sina MicroBlog. The results of sequencing experiment and coverage ratio experiment show that the user influence measurement of the model is accurate and valid.

Keywords： user influence; non?redundant information; user behavior; structural hole; network constraint coefficient; coverage ratio

0  引  言

用户影响力度量是在线社交影响力分析的核心问题之一，用户影响力指通过用户等受其他用户的影响而变化的现象[1]，它可以应用到推荐系统、网络信息传播的预测、链路预测、病毒式营销、突发事件预测等领域[2?3]。

目前用户影响力的度量方法大多基于网络拓扑结构、用户交互行为（转发、评论、提及）两个角度[4]。这些方法各有侧重点，但对用户间的非冗余信息考虑不全[5]。基于网络拓扑结构的方法中，度中心性[6]、聚类系数[7]等方法从局部角度出发，考虑了节点与邻居节点的数量关系，对节点间拓扑结构欠缺考虑，对节点间的非冗余信息考虑不足[1];Closeness和Betweeness[8]等方法从全局角度出发，以网络平均路径衡量用户影响力，无法兼顾节点间的非冗余信息，且要求全连通网络且计算复杂度高，不适用于大型社交网络[4];基于用户交互行为的方法基于用户的评论、转发、提及等行为，文献[9]将用户行为与PageRank算法[10]相结合，同时考虑用户文本，对用户影响力进行度量;文献[11]从消息的转发和时间角度对用户影响力度量，没有考虑网络拓扑的影响。这类方法多考虑了邻近节点间的用户行为，对非冗余信息的考虑同样不足。

针对用户影响力度量中非冗余信息考虑不全的问题，研究发现[12]：结构洞节点可以从网络中获得更多的非冗余信息，更好地观测信息的流向，评价用户影响力。文献[13]实验发现，在线社交网络Twitter上1%的结构洞用户决定了用户之间25%的信息传播。文献[14]提出一种小范围度量方法寻找目标网络中的结构洞节点。文献[15]提出识别Top?[k]结构洞关键节点的HIS算法和MaxD算法，文献[5]基于平均距离寻找结构洞节点，文献[16]结合评价结构洞的多个指标，利用排序学习算法对节点影响力进行评价。这些方法都未考虑用户行为对网络边权的影响，同时未考虑节点与邻近节点、次邻近节点的三层拓扑结构。文献[17]研究发现，在线社交网络中91.6%的消息连续传播在3次以内，考虑三层节点的拓扑结构能全面地评价用户节点的影响力。

针对用户影响力度量非冗信息考虑不全的问题，本文引入结构洞理论，同时针对结构洞评价中存在的问题，对结构洞评价方法——网络约束系数进行改进，最后构建基于用户行为和结构洞的用户影响力评价模型。通过新浪微博对用户影响力进行度量实验，说明本文模型度量用户影响力的有效性与准确性。

1  理论与方法

1.1  结构洞理论

假设存在用户节点[A]，[B]，[C]，[D]，节点间连接情况如图1所示。非冗余信息[5]指通过不同用户的联系获得的非重叠信息，节点[A]和节点[D]没有直接连接而存在非冗余信息。文献[14]指出，结构洞是连接两个非冗余用户的桥梁，用户间的非冗余联系即为结构洞。节点[C]分别与[A]和[D]，[B]和[D]构成了结构洞关系，[C]作为结构洞节点。而由于[A]和[B]有连接，存在冗余联系，则[C]与[A]和[B]不能构成结构洞关系。

1.2  结构洞评价方法分析

为了描述节点间的闭合程度，文献[14]提出网络约束系数（CT），描述节点运用结构洞的程度：

[Cij=pij+qpiqpqj2]  （1）

式中：[Cij]表征节点[j]与节点[i]的约束大小，[q≠i，j]，节点[q]是节点[i]和[j]的共同相邻节点;[pij]为节点[i]花费在节点[j]上的精力占[i]花费总精力的比例，[pij=zijk∈Γ（i）zik]，[zij]表示[i，j]两节点的连接情况，有连接其值为1，反之为0，[Γi]表示节点[i]的邻居集合。那么节点[i]的网络约束系数[Ci]为：

[Constri=jcij]  （2）

上述方法进行节点重要性评价时，存在两个问题：

1） 没有考虑用户行为（评论、转发等）对网络边权的影响。如图2所示，该方法依据节点的度进行计算，对于节点[D]和[E]，根据式（1），节点[i]与节点[E]、节点[D]的网络约束系數表示为：[CiD=（piD+piBpBD）2=（16+16×13）2=0.049 4=CiE]，两者的网络约束系数大小相同，但节点[i]与[E，D]以及[E]与[K，D]与[L]连接的边的权值不同，两节点重要性显然有差异，同时节点间的用户行为也没有考虑，这一点结构洞评价没有兼顾到。

2） 节点与邻居节点间的两层拓扑结构无法反映部分节点的重要性差异。如图2所示，对于节点[E]和[F]，根据式（1），两节点有共同的邻居节点[A]，计算得：

[CiE=（piE+piApAE）2=（16+16×14）2=0.043  4=CiF]

网络约束系数只考虑了节点与其邻居节点的两层拓扑结构，但节点[E]与节点[F]在本文网络中的重要性是不同的，节点[F]由于与和多节点存在联系的节点[G]有联系，重要程度显然强于节点[E]。换言之，节点[i]在与节点[F]保持联系投入的精力较节点[E]要多，这一点在结构洞的评价中没有兼顾到。

2  用户影响力评价模型

本文在进行用户影响力度量时引入结构洞理论，同时针对1.2节结构洞评价方法的两个问题，做了相应改进，本文算法流程如图3所示。

2.1  融入用户行为的网络边权

为考虑用户行为对网络边权的影响，本节首先对用户行为进行量化，然后融入到网络边权计算中。以新浪微博网络为例，在考虑用户行为（转发、评论等）的基础上，定义网络边权值。通过收集微博用户的三种用户行为关系，定义网络拓扑结构为[G{V，（E，D）}]，[V]代表用户节点集合，[E]代表边集合，[D]代表边权值集合，它由评论权值集合[C]、转发权值集合[T]、提及权值集合[M]三部分构成。其中，[C={cij}]，[cij]代表评论权值，其大小为用户[vj]对用户[vi]所发微博的评论总数。

同理，可得转发权值[tij]和提及权值[mij]，且[T={tij}]，[M={mij}]。融入用户行为的边权为：

[dij=w1cij+w2tij+w3mij]    （3）

本文默认三种用户行为重要性是一样的，定义[w1=w2=w3=1]，最后得到网络的边权[dij]。

2.2  结构洞评价方法的改进

为更全面地体现用户在网络中的地位，本节考虑节点与邻近节点、次邻近节点的三层拓扑结构对网络约束系数计算方法进行改进，最后实现用户影响力的度量。

在2.1节加权网络[G{V，（E，D）}]的基础上，定义网络节点[i]的权值度为：

[wi=j∈Gdij]   （4）

式中[dij]为网络边权值。节点[i]的权值度为与节点[i]连接的所有边的边权之和，改进基于节点的度的计算方法为结合2.1节网络边权的计算方法。

定义节点[i]的总权值度为：

[Wi=j∈Γiwj]  （5）

式中[Γi]表示节点[i]的邻居集合。为反映节点间的三层拓扑结构，定义节点的总权值度。节点[i]的总权值度为与节点[i]相连的所有节点的权值度之和。

定义节点[i]花费在节点[j]上的精力比例[pij]的计算方法如下：

[pij=wjm∈ΓiWm] （6）

改进之后用户节点[j]与用户节点[i]的网络约束系数为：

[CTij=pij+q（piq×pqj）2] （7）

图2中，根据式（7）得：对于节点[D]和[E]，经计算得：[CTiD=0.022  5]，[CTiE=0.022  6]，两者的网络约束系数存在差异，这是考虑用户行为对网络边权影响的结果，符合实际情况。对于节点[E]和[F]，有[CTiE=0.022  6]，[CTiF=0.049  3]，由结果可知，节点[i]向节点[F]投入的精力比向节点[E]投入的精力多，考虑了两节点的三层拓扑结构，符合实际情况。

最后，提出本文的用户影响力评价模型：

[Si=j=1nCTij] （8）

3  实验分析

3.1  数据抓取

通过新浪微博平台，以一部分用户作为起点，获取其发表、转发等微博内容信息，轮流抓取用户的关注用户作为新起点，重复以上操作。本文抓取了自2017?05?27—2017?07?01的微博数据。其中包括14 543个用户和127 426条微博。

3.2  评价指标

1） 为验证本文模型度量用户影响力的准确性，对比不同算法模型下，影响力排序后用户中大V用户所占比例，通过比较说明本文模型的准确性。

2） 为验证本文模型对用户影响力度量的有效性，采用覆盖率[18]（Coverage Ratio，CR）对模型进行评估。它表征用户的传播能力，覆盖率越大，同时随着用户的传播能力变强，用户的影响力也会变大。覆盖率定义为：

[覆盖率=传播范围总节点数×100%]         （9）

總节点数表示用户通过自身行为形成的网络拓扑图中的节点个数;传播范围指网络拓扑图中受到用户行为和结构洞原理的影响，信息通过用户行为传递，波及到的用户节点数量。

3.3  实验及结果分析

3.3.1  用户影响力度量准确性实验

将本文模型[Si]、度中心性[6]、原始网络约束系数CT、PageRank算法[10]、基于用户?内容分析的TURank模型[9]用在数据集上，对比影响力排序结果见表1。

表1中为各算法模型筛选的影响力排名前10的用户（英文简写）。 最后一行表示筛选用户中的大V用户数，本文模型筛选的大V用户有“雷军”“王煜全”“卢健生”“王自如ZEALER”等8人，准确性最好;网络约束系数CT识别关注更多的是社团间的连接用户，而忽略了用户行为因素与三层节点网络拓扑因素的影响，如排名10号的“小米王川”虽然与高影响力节点“雷军”等用户有联系，但互动频率低，这点CT没能兼顾;度中心性没有考虑用户之间的互动行为和节点在网络中的位置，对非冗余信息考虑不足，效果最差;PR值用户的粉丝数相关过高，仅识别出“雷军”“卢健生”大V用户，而其他用户“僵尸粉”用户过多，实验结果不准确;TURank综合考虑用户文本和用户行为，效果较好，但缺乏对节点三层结构的考虑，相较本文算法不能充分评价非冗余信息。

本文进一步比较各模型影响力Top100用户中的大V用户数，结果表明，本文模型识别大影响力用户数最多，如图4所示。

3.3.2  用户影响力度量有效性实验

进行下一步实验之前，首先进行数据预处理，剔除“僵尸粉”用户的干扰，这类用户往往以增加目标用户人气、广告推销为目的，基本没有有效的用户行为。本文筛选出已收集数据集中网络边权[dij]大于3的用户，把它作为标准集。

把本文模型[Si]、PageRank算法、TURank模型用在此标准集上，对比覆盖率，结果如图5所示。

图5中，各算法模型随着用户数量的增加，信息传播的范围逐渐增大，传播范围增长率大于节点数的增长率，覆盖率逐渐增大，而随着用户数量的上升，会出现一些独立的用户节点，覆盖率增长速度会变缓并稳定在一定水平。PageRank算法关注粉丝数量，忽略了用户行为和三层节点网络拓扑的影响，覆盖率总体较低。TURank模型缺乏对三层节点间拓扑关系的考虑，传播能力较本文模型低。本文从多角度对用户影响力进行度量，覆盖率指标表现最优，说明了本文模型的有效性。

4  结  语

本文基于用户行为和结构洞原理构建用户影响力综合评价模型，以新浪微博为例，对用户影响力进行度量实验。针对目前用户影响力度量中对非冗余信息考虑不全的问题，本文模型将结构洞原理运用到用户影响力评价中，同时改进其评价方法——网络约束系数未考虑用户行为以及节点与邻近节点、次邻近节点的三层拓扑结构的问题，最终实现对用户影响力的度量。实验结果验证了本文模型度量用户影响力的有效性和准确性。在下一步的工作中，将在本文研究成果的基础上，对用户行为中的主题进行识别，情感进行分析，进一步优化对用户影响力的评价。

注：本文通讯作者为覃锡忠。

参考文献

[1] 吴信东，李毅，李磊.在线社交网络影响力分析[J].计算机学报，2014（4）：735?752.

WU X D， LI Y， LI L. Influence analysis of online social networks [J]. Chinese journal of computers， 2014（4）： 735?752.

[2] 王涛，覃锡忠，贾振红，等.基于相似度和信任度的关联规则微博好友推荐[J].计算机应用，2016，36（8）：2262?2267.

WANG T， QIN X Z， JIA Z H， et al. Association rules recommendation of MicroBlog friend based on similarity and trust [J]. Journal of computer applications， 2016， 36（8）： 2262?2267.

[3] KANNA A F， YACINE A， AJITH A. Models of influence in online social networks [J]. International journal of intelligent systems， 2013， 29（2）： 161?183.

[4] 王楠，孙钦东，周亚东，等.基于区域交互模型的SNS网络用户影响力评估[J].通信学报，2016，37（1）：160?169.

WANG N， SUN Q D， ZHOU Y D， et al. Study on user influence analysis via regional user interaction model in online social networks [J]. Journal on communications， 2016， 37（1）： 160?169.

[5] REZVANI M， LIANG W， XU W， et al. Identifying top? k， structural hole spanners in large?scale social networks [C]// 2015 ACM International on Conference on Information and Knowledge Management. Melbourne： ACM， 2015： 263?272.

[6] ALBERT R， BARABASI A L. Topology of evolving networks： local events and universality [J]. Physical review letters， 2000， 85（24）： 5234?5237.

[7] CHEN D B， GAO H， L? L， et al. Identifying influential nodes in large?scale directed networks： the role of clustering [J]. Plos ONE， 2013， 8（10）： 77455.

[8] LU L J， ZHANG M. Edge betweenness centrality [M]. New York： Springer， 2013.

[9] YAMAGUCHI Y， TAKAHASHI T， AMAGASA T， et al. TURank： twitter user ranking based on user?tweet graph analysis [C]// 2010 International Conference on Web Information Systems Engineering. Berlin： Springer， 2010： 240?253.

[10] WENG J， LIM E P， JIANG J， et al. TwitterRank： finding topic?sensitive influential twitterers [C]// Proceeding of the Third ACM International Conference on Web Search and Data Mining. New York： ACM， 2010： 261?270.

[11] TANG X， YANG C C. Ranking user influence in healthcare social media [J]. ACM transactions on intelligent systems & technology， 2012， 3（4）： 1?21.

[12] GUPTA J P， MENON K， MUKKAMALA R R， et al. Identi?fying weak ties from publicly available social media data in an event [C]// 2016 International Academic Mindtrek Confe?rence. Tampere： ACM， 2016： 11?19.

[13] KONG H， LI X， WANG L， et al. Generalized 2D principal component analysis [C]// 2005 IEEE International Joint Conference on Neural Networks. Montreal： IEEE， 2005： 108?113.

[14] BURT R S. Structural holes： the social structure of competition [M]. Cambridge： Harvard University Press， 2010.

[15] LOU T， TANG J. Mining structural hole spanners through information diffusion in social networks [C]// Proceedings of the 22nd International Conference on World Wide Web. Rio de Janeiro： ACM， 2013： 825?836.

[16] 韩忠明，吴杨，谭旭升，等.面向结构洞的复杂网络关键节点排序[J].物理学报，2015，64（5）：421?429.

HAN Z M， WU Y， TAN X S， et al. Ranking key nodes in complex networks by considering structural holes [J]. Acta physica Sinica， 2015， 64（5）： 421?429.

[17] YE S， WU S F. Measuring message propagation and social influence on Twitter.com [C]// Proceedings of the Second International Conference on Social Informatics. Laxenburg： Springer?Verlag， 2010： 216?231.

[18] HOU W， HUANG Y， ZHANG K. Research of micro?blog diffusion effect based on analysis of retweet behavior [C]// 2015 IEEE International Conference on Cognitive Informatics & Cognitive Computing. Beijing： IEEE， 2015： 255?261.