基于监督随机游走的有影响力用户发现算法

唐明伟，高振伟,2，王彦婷，王 镇，邓加钰，陈晓亮

（1.西华大学计算机与软件工程学院，四川 成都 610039；2.中电科大数据研究院，贵州 贵阳 550022）

随着网络的发展，网络社交平台（如微博等）的出现改变了人们的生活。兴趣爱好类似的个体之间会相互关注。个体间的交互也较大地影响着网络的拓扑关系。基于用户的行为特征去判断其影响力是热点研究内容之一。基于微博的社交关系特性，挖掘信息的发送者，尤其是具有很大影响力的关键核心用户是非常重要的。但是，大量的“僵尸粉”充斥着微博，依据粉丝数等特征不能有效地判断该用户的真实影响力。剔除微博中的“僵尸粉”，挖掘该用户的真实影响力，具有重要的现实意义。网络结构和文本信息是识别有影响力用户的重要因素。

1 相关工作

基于随机游走思想的PageRank 算法已在社交网络得到广泛研究。该算法为节点分配代表其重要性的数值，测算每个节点值，并确定网络的结构。基于微博的个体特征及其行为特征，原野等[1]使用博文的规则和互动量计算公式，提出了基于MapReduce 和Spark 的并行计算框架。基于用户的粉丝数与其所发布的相关信息传播扩散速度的正相关性，Kwak 等[2]利用Twitter 社交网络和PageRank 变形提出了TunkRank 算法。Romero 等[3]分析了被影响的用户数和没有被影响的用户数，得出影响力是建立在粉丝被动性及关注者积极性上的结论。Mao 等[4]采用一种基于学习的方法来分析和测算用户的社会影响力，进而判断用户传播信息的能力。Agarwal 等[5]根据博文的评论、内容、互动程度及外部链接等特征对博客用户影响力进行全面评估与分析。Zhang 等[6]基于用户评论等交互行为，计算在不同时段用户的影响强弱。Huang 等[7]将PageRank 算法应用到用户活动特征中来评价微博用户的影响力。Tang 等[8]研究和分析了用户的会话内容等特征，采用加权的社会网络来评估用户的显式和隐式影响力。基于用户的活动因素、历史关注和微博的传播力因素，Chen 等[9]提出了一种用户影响力排名算法。通过用户之间存在的交互程度，Sheikhahmadi 等[10]提出了一种在社交网络中识别有影响力用户的方法。Wang 等[11]提出了一种基于情绪一致性的算法来查找Topk有影响力的用户。

文本内容是被用来评估用户影响力的因素之一。根据主题敏感程度和用户的互动等，Weng 等[12]分析用户和链接关系的局部相似性提出TwitterRank算法。Xiao 等[13]基于特征的共现词检测标签去检测新闻主题相关的用户社区，并分别从转发和提及2 方面对主题社区下的活跃用户影响力进行了评估。Li 等[14]提出一种基于在线学习社区的混合框架的意见领袖发现算法。从用户内容中提取主题以及利用主题之间的分布相似性，Pal 等[15]提出了使用主题建模的方法去判断用户影响值大小。结合不同主题下的影响力的传播模型（TAP），Hu 等[16]通过综合分析当前网络拓扑和所有节点的主题分布，构建了基于主题因子的传播模型（TFG）。融合主题模型和影响力，Bi 等[17]提出了一个比潜狄利克雷分配模型（LDA）更复杂的混合模型（FLDA模型）。根据用户对话题的情感极性，Eliacik 等[18]提出了一种在社交网络中计算影响力用户的算法。Backstrom 等[19]提出了基于监督的随机游走（supervised random walks，SRW）算法。

研究者常常更注重依赖网络结构去发现有影响力的用户，但是微博社交平台有影响力的用户通常只擅长某一领域，也只会影响具有相似度高的一批用户；因此，本文将链路预测的方法应用到有影响力用户检测中，提出了基于用户主题偏好的监督的随机游走算法（topic preferences supervised random walks，简称TP-SRW）。

2 基于用户主题偏好的监督随机游走算法（TP-SRW 算法）

2.1 监督随机游走

基于用户主题偏好的监督随机游走的模型框架如图1 所示。由于无监督随机游走的不确定性，因此本文在随机游走的基础上加上监督的方式去指导游走节点进行游走。它巧妙地融合了网络结构、节点和边的特征，使游走的节点更加倾向于目的节点。

重启随机游走是随机游走的一种改进,当将要进行下一步转移时有2 种选择：根据状态转移矩阵以一定的概率随机地选择下一个节点；以一定的概率回到初始节点重新开始游走。

图1 基于用户主题偏好的监督随机游走模型

社交网络可以用有向图G=(V,E)表示,V表示节点的集合，E表示节点与节点之间相连的边。2 个节点之间存在边，代表用户与用户之间有社交互动，具体来说：边ei j表示用户ui与用户uj发生了互动关系，对于每一条边，建立一个特征向量 φuv去描述2 节点相连的边以及节点本身的关系。特征向量 φuv有以下特征：粉丝数、微博数量、关注数、兴趣主题、微博被转发数。对于每一个节点可以根据该用户的历史微博得出该用户的主题概率分布，用suv表示2 个节点之间的主题相似性评分。在有监督随机游走的过程中，需要学习出一个边权重的参数，首先用PageRank 生成一组有影响力的节点I={i1,i2,···,in}和一组没有影响力的节点IN={n1,n2,···,nn}，其目的就是让随机游走出来的结果包含I但是不包含IN。因此，在随机游走算法中利用边权重计算函数fw(φuv)和主题相似度评分suv来计算边的重要度auv=fw(φuv)suv。边的重要度就是随机游走过程中节点间的转移概率。

2.2 基于LDA 主题模型的用户主题偏好

微博文本字数有限，通常小于140 个字符，除去一些噪声信息，可利用的信息有限。本文首先把每位用户在特定时间内所有微博、评论以及反馈等信息收集到一个文件中，并一一对应；然后使用LTP 分词工具对该文件进行预处理，只保留名词等关键信息；接着利用LDA 主题模型对每篇文档的主题进行抽取，并将结果保存在用户-主题偏好矩阵中。假设主题集合数为m，用户数为n，每个用户都有矩阵中对应的各个主题的偏好概率。根据各个主题偏好的概率，建立D=U×IT矩阵，其中U代表微博用户集合，IT代表主题偏好集合。在D矩阵中，元素anm表示用户vn所发表的微博文本中关于主题tm的概率，它描述用户对主题社区的偏好程度。用户-主题偏好矩阵为

2.3 微博用户主题相似度计算

在微博社区中，同质性代表具有相同或者相似兴趣爱好的用户。当一个用户发表了1 篇微博，与该用户具有同质性的用户会对该微博产生兴趣，行为上主要体现在对该微博进行转发、评论、回复、点赞等操作。因此，可以根据用户的微博文本的主题相似度来衡量用户的同质性，再依据排序算法，对某一特定主题下具有同质性的用户进行排序，进而找出特定主题下有影响力的用户。

本文将每个微博用户所有发表、转发和评论的内容归集到1 篇文档中，然后用2.2 节的LDA主题模型进行分类，并将分类结果保存在用户-主题偏好矩阵D中。准确来说，给定所有用户的主题分布，通过计算相应主题的概率分布来计算用户所发微博、回复、评论所形成的文档之间的相似度。

1）主题相异度Dis(i,j)，表示2 主题分布的差异程度。

式中，TS(i,j)是Jensen-Shannon 散度,它是相对熵（Kullback-Leibler Divergence，KL 距离）一种变种，主要用来衡量2 个变量的相似度，其表达式[20]为

其中，M是2个概率分布的平均值，Ai和Aj是不同用户i,j对应的文档的主题概率分布，是Ai和Aj2 个向量之间的 Kullback-Leibler 散度，也是衡量2 个概率分布的差异程度。

2）用户主题相似度计算。主题相似度可以通过用户对应的主题分布的Jensen-Shannon 散度进行计算，用 topici j表示。其中，topici j是介于0-1 的值，主题相关度越大，说明2 个用户感兴趣主题越相似。可通过对数据进行规范化处理，有效地提升算法鲁棒性。

2.4 基于主题偏好的监督随机游走算法

在微博社交网络中，假如用户A 发表了1 篇微博，A 的粉丝B 受到A 的影响以一定的概率转发了用户A 的微博，则此概率就是节点A到节点B之间的转移概率。传统的方式是采用PageRank 算法来计算节点之间的转移概率，然而在微博中，用户兴趣深刻地影响着用户的转发等行为；因此，在计算转移概率时要考虑2 个节点兴趣的相似度和边的属性特征。在进行随机游走前，利用优化的方法去计算边的重要度，对于每一条边，建立一个特征向量φuv去描述2 节点相连的边以及节点本身的关系，本文采用来表示。这里的auv就是随机游走过程中节点间的转移概率，用特征向量w来表示边权重计算函数fw(φuv)的参数。与文献[20]提出方法类似，本文通过计算边的权重来确定更有影响力的节点，最终确定最佳参数w（即边权重函数f的参数）。

监督随机游走算法中用到的参数最优化问题定义为

式中：I为具有影响力的节点集合；IN为没有影响力的节点集合；λ为正则化参数，用作平衡模型的复杂度与其结果约束条件强弱之间的关系。它的值越大，说明约束条件越强，反之则越弱，对错分情况的容忍度越大。在实验中，λ过小容易发生过拟合的风险。在本文中，当λ=1时，实验效果达到最好。为了解决最优化问题，采用改进L-BFGS 算法[21]去寻找最优的w，使得F(w)最小。损失函数h通过不同的pi-pn进行惩罚，如果pi-pn＞0也就是h(·)=0，即没有违反约束，反之，pi-pn＜0即h(·)＞0。在这里采用了Wilcoxon-Mann-Whitney（WMW）损失函数[22]，为

在学习边权重参数前，首先建立边权重函数fw(φuv)与边权重参数w以及主题偏好随机游走得分p联系。具体来说，给定边的权重函数和主题相似性评分求出边的重要度auv,根据这个边的重要度来指导随机游走。

定义从节点u到节点v的转移矩阵Q和转移概率PQ为：

由式（9）（10）可知，主题相似度越高，边的权重越大，转移概率越高越容易找到更有影响力的节点。

在随机游走过程中，会遇到链路中断等情况，因此引入了重启动随机游走机制，也就是节点在随机游走过程中会以一定的概率回到初始节点重新开始随机游走，设重启概率为γ，假设s为初始节点，那么

且

在网络中按照转移矩阵Q*中的概率进行重启动的随机游走，最终会达到一个稳定的状态，此时，每一个节点都能得到一个概率值，即从初始节点出发按照重启随机游走概率矩阵Q*的概率在网络上游走访问到该节点的概率，此时主题偏好随机游走概率满足式（13）。

式（13）使节点的PageRank 评分pu∈p以及边权重计算函数的fw(φuv)学习参数w通过随机游走转移矩阵Q联系到一起。F(w)相对于w的梯度，为

其中δin=pi-pn，已知loss()损失函数，可以求出关于w的损失函数，这里需要计算的是，根据式（13）可以得到

输出：最佳参数w。

step 1:选初始点w0，收敛误差ε ＞0，存储最近m次的迭代数据。

step 2:k=0,r=∇F(w0)。

step 3:如果‖∇F(wk+1)‖≤ε，则返回最优解w，否则转入step 4。

step 4:计算本次迭代的可行方向pk=-rk。

step 5:计算步长ak＞0，对下面的式子进行一维搜索。

step 7:如果大于，保留最近 次的向量对，删除。

step 8:计算并保持。

step 9:用two-loop recursion 算法计算rk。

step 10:k=k+1，并转入step 3。

根据上述算法求出最佳参数向量w，计算对应节点的转移概率来进行有影响力的用户发现。TPSRW 算法如图2 所示。

图2 用户主题偏好的监督随机游走算法伪代码

3 TP-SRW 算法实验

现进行僵尸粉识别ASDM 模型（advertising spammers detecting model）实验和有影响力用户发现TP-SRW 算法（topic preferences supervised random walks）实验，其实验流程如图3 所示。

图3 实验流程图

实验数据主要包括微博用户的ID、用户发表微博帖子内容、用户的关注数量和粉丝数量，以及关注转发评论等关系信息。微博数据的获取途径有2 种：数据集1 利用微博爬虫对新浪微博平台进行微博数据的爬取，共爬取了6 万4 168 条微博数据；数据集2 来自于2016 年第五届全国社会媒体处理大会（SMP2016）中比赛用的微博数据集，有4 万8 162 条微博数据。本文将数据集1 作为训练集，数据集2 作为测试集。

本文采用LTP 系统对微博短文本切词、分词等微博数据进行处理[23]。

为分析用户的主题偏好，本文把同一用户在一定时间内所有博文、评论以及回复集中到1 篇文档中，然后对文档进行切词、分词处理，接着利用Mahout 机器学习平台，采用LDA 主题模型对文档的主题进行分析。部分关键词表示如表1 所示。

针对LDA 模型，文献[20]认为主题数选取在20 左右得出的结论效果较好。本文计算用户主题偏好时，仅需要对用户偏好进行模糊评估，因此，选取主题数小于所有可能的话题数，降低了拟牛顿法训练过程中参数w的收敛时间。表2示出部分用户对于指定的5 个主题的偏好概率分布情况。相关主题概率越大，代表着其越偏向于某个主题。

表1 主题对应关键词

表2 用户相关微博的比例

3.1 “僵尸粉”识别实验与结果分析

3.1.1 “僵尸粉”标注

由于“僵尸粉”的不断变异升级，在分类“僵尸粉”时没有可以利用的现成标注过的训练集，因此本文采用手工标注的方式去标注数据集中的僵尸粉。在度量用户的影响力时仅仅是活跃的“僵尸粉”才会对用户影响力产生影响。该类“僵尸粉”表面上看和正常用户是区分不开的，但该类用户会转发或者发布大量的营销类博文；因此，本文通过二人双盲的方式标注用户的微博文本。首先通过标注的文本和垃圾微博占的比例来确认该用户是否为“僵尸粉”，然后分析该类用户在用户属性和行为上和正常用户的差异性。

对于微博文本，本文采用LDA 主题模型进行分析，统计出正常随机用户和“僵尸粉”用户在微博文本主题上分布的差异性，其结果如表3 所示。可以看出，营销类“僵尸粉”用户和随机用户在微博文本主题分布上很有大的差异。随机用户中概率较高的主题为亲子、旅行、生活、经济、政治等，而营销类“僵尸粉”概率较高的主题多为有奖抽奖推广、商品推广、链接推荐、婚纱摄影推广等。可见，将微博文本特征用于识别广告类“僵尸粉”是可行的。

表3 随机用户和广告“僵尸粉”用户的主题分布

3.1.2 实验评价指标

为了评估僵尸粉识别ASDM 模型的性能，分别使用准确率P（precision）、召回率R（recall）和F值（F-value）。P和R相互影响和相互制约，F值则表示综合考虑准确率和召回率二者关系。其定义为

式中：WCorrected表示被正确识别是“僵尸粉”的个数；WAllspam表示样本中是“僵尸粉”的总个数；WAll表示数据集中提取到的用户总个数。

3.1.3 实验结果及分析∑

实验将α从0 开始缓慢的增加，在每个α下计算准确率、召回率、F值，得出的结果如图4 所示。由图可知，在本文模型中，即使是营销类的“僵尸粉”自己所发布微博的重复率也比较低，在整体上其影响不如转发的微博，这是因为该类用户往往是营销机构为了扩大传播能力而注册的小号，该类帐户往往是以转发其他有需求的营销帐号的微博为主。统计结果表明，当α=0.14时，F值为最大，等于0.933。

图4 不同的参数α 取值下算法的评价效果

为了评估算法性能，将ASDM 模型与张艳梅等[24]提出的SVM 算法和张锡英等[25]提出的Naive Bayes 算法进行对比，其结果如图5 所示。ASDM模型分类准确率超过了94%，其性能优于其他算法。在识别“僵尸粉”实验中，ASDM 模型的综合性能更好。

图5 ASMD、SVM 及Naive Bayes 对比实验

3.2 TP-SRW 算法实验与结果分析

为了验证算法有效性，本文首先对已有的数据集进行处理，将数据集中每一位用户的微博文本归集到1 篇文档，用LDA 主题模型对上述文档进行主题分析，统计出数据集中用户的主题偏好。本文选取比例前四的主题：科技(16.63%)、娱乐(15.36%)、旅游(13.29%)、军事(12.5%)去评价TP-SRW 算法的性能。

3.2.1 参数设置和评价指标

TP-SRW 算法有2 个评估有影响力用户挖掘效果的指标：肯德尔等级相关系数（Kendall Tau Correlation）[26]和覆盖度[27]。肯德尔等级相关系数是用来度量2 个随机变量是否具有相关性。在真实的社交网络中，一方面影响力不会仅仅介于直接交互的邻居用户间，另一方面影响力随着路径的增大将会逐渐减弱；因此，本文将单步覆盖度和全路径覆盖度做平均，其平均值作为对有影响力用户挖掘效果的初始评估指标。

TP-SRW 算法引入了重启的随机游走。其重启概率的大小会影响节点随机游走的状态。重启概率值越大，节点随机游走过程中回到初始节点的概率也就越大，结果会更偏向于距离近的节点。通过对比不同的重启概率值对实验结果的影响，发现当重启概率等于0.65 时，该算法的效果最好。

3.2.2 算法实验结果与分析

为了验证TP-SRW 算法在不同的主题下识别有影响力用户的有效性，将其与Twitter rank 算法[12]、Inf luence rank 算法[28]以及Leader rank 算法[29]进行实验与对比。

由于微博从发布到消亡有一个过程，本文利用覆盖度指标去评判识别出的有影响力用户在一定时间内影响的人数。对发帖后的2、8、24、48 h 的情况进行实验，图6 和图7 给出前20 和前50 个有影响力的用户的覆盖度。其结果表明： TP-SRW 算法性能优于Twitter rank 算法、Inf luence rank 算法以及Leader rank 算法。Leader rank 算法没有考虑粉丝质量，粉丝中的大量发送垃圾广告的营销类“僵尸粉”的存在会对用户影响力的评估造成一定的负面影响。Twitter rank 方法在计算用户的影响力时把重点放到用户发微博频次上，没有考虑用户和用户之间的互动，这同样影响到用户的影响力。TP-SRW 算法综合考虑了粉丝质量及用户和用户之间的互动关系。

图6 排名前20 的有影响力用户的影响力覆盖度

图7 排名前50 的有影响力用户的影响力覆盖度

4 结论

本文研究了监督的随机游走，并将链路预测的方法用到影响力用户发现上。根据用户的微博爱好，构建用户的兴趣偏好概率矩阵，计算用户与用户之间的相似度，然后给出了边权重参数的训练，针对给定一组有影响力的节点和一组没有影响力的节点，采用最优化的方法并结合边和节点的特征去指导随机游走，发现更有影响力的节点。

在“僵尸粉”识别的实验中，首先进行数据的标注，然后进行训练，最后在测试集上进行测试，并和其他算法做了对比。在有影响力用户发现实验中，着重对比了不同主题社区下前20 和前50 的有影响力用户发布微博的覆盖率。其结果表明，TPSRW 算法的性能更好。在下一步工作中，将考虑话题热度和粉丝的真实性等因素，以期进一步提高TP-SRW 算法的性能。