基于用户影响力的微博数据提取算法

田霏霏 沈记全

(河南理工大学计算机科学与技术学院 河南 焦作 454000)

基于用户影响力的微博数据提取算法

田霏霏 沈记全

(河南理工大学计算机科学与技术学院 河南 焦作 454000)

微博作为舆情分析中基础数据的主要来源之一，如何对其进行有效提取是数据获取的关键问题。为此，提出一种基于用户影响力的数据提取算法，以满足舆情系统对数据的需求。该算法首先利用模拟登录技术获取用户关系并依此构建用户网络，再根据自主设计的用户影响力计算方法计算出影响力，进而建立符合微博特征的影响力最大化模型挖掘出最具传播能力的k个节点，最后爬取相应的微博数据。实验证明，该算法能够有效提高获取数据的质量，为舆情分析提供更好的数据支持。

舆情 微博 数据获取 用户影响力 范围最大化

0 引 言

微博作为大数据时代新生的网络应用形式，以建立用户关系为基础，提供了一个基于信息共享和传播的平台[1]。自其诞生之日起，就以其简单的组网方式和强大的信息传播能力吸引了大量用户[2]。大数据背景给予微博平台庞大的用户群体和海量的数据，其在社会舆情的形成中起着重要作用。随着微博持续不断地披露出重大公共事件，其逐渐成为舆情分析的主要数据来源。

为进行更有效的舆情分析，对基础数据的质量提出新的要求。近年来国内外学者在微博数据提取方面做了大量研究。高凯等[3]利用模拟登录技术结合抓包工具对数据包进行截取和分析，爬取网页链接和数据。陈舜华等[4]通过调用微博API接口来获取数据信息。由于API不完全对外开放，因此该方案获取到的数据不够全面。廉捷等[5]将微博API与Web页面解析技术相结合，对API调用频率进行合理控制实现了微博数据的高效获取。该方法获取的数据虽相对完整，但数据较原始、质量较低。卢体广等[6]使用一种模拟登录的算法来完成新浪微博的认证，通过计算优先级构造优先队列来进行数据获取。马俊等[7]提出了PBF方法，该方法通过对用户个人属性进行分析计算出用户影响力。Aizawa[8]针对Binary Heaps算法进行改进，提出一种优先队列计算方法来构造优先队列。Weng等[9]提出了基于PageRank原理的TwitterRank算法来计算某一用户在某一主题内的影响力。Phan等[10]基于Reduce Number of Comparison算法进行改进，在数据获取时也进行了优先队列的计算及构造。毛佳昕等[11]通过对用户行为特征的分析来评价用户影响力。虽然使用文献[6-11]中的方案均可获取到用户数据，但却没有将提取目标用户的范围最大化[12]，忽略了用户网络中的弱连接点。

针对以上获取数据质量方面的不足，本文提出一种基于用户影响力的微博数据提取算法来解决此问题。该算法首先构建用户网络，再通过深入分析用户交互行为计算用户影响力，进而建立影响力最大化模型挖掘出最具传播能力的k个节点并提取相应的微博数据，最终完成微博数据获取。通过该算法可以有目的地提取数据，为舆情分析提供良好的数据来源。

1 用户影响力计算

微博平台中，用户通过添加关注建立起单双向关系，从而构成整个用户网络。在此基础之上，用户间可进行各种交互使信息得到传播。定义用户影响力来衡量用户对信息的传播能力：

定义1 用户影响力[13]是微博网络中用户对他人的影响能力以及对信息的传播能力，是以用户交互为基础的一种信息传播能力，是用户在社交网络中重要性的体现。

由定义1可知影响力大的用户可以影响到更多的人，使信息的传播范围更广，更有利于舆情的产生。因此本文通过设计用户影响力计算方法对影响力进行计算，并以此为基础进行数据提取，能够更好地满足舆情分析的需要。

1.1PageRank算法

众所周知的PageRank[14]算法是用来计算网页重要性排名的经典算法，在用户影响力的计算中也被广泛应用。该算法利用网络拓扑中的链接关系来计算网页的重要程度。表达式如下：

(1)

式中，Pi代表当前页面，L(Pj)表示从页面Pj链出页面的集合，M(Pi)是Pi的链入页面集合，d是阻尼系数。计算后PageRank值越大的网页越重要。由式(1)可看出，算法中页面的影响力值是均匀地传递到链出页面上的，忽略了各页面间影响力的不均衡性。

1.2 用户影响力计算方法

针对PageRank算法在影响力传递方面的不足，本文通过深入分析用户交互提出用户影响率的概念对其进行改进，以便更合理地分配用户影响力，最终计算出每个用户的影响力。用户影响率是被关注者对关注者的影响力，是一种衡量用户间交互能力的量，所以应从用户交互的角度去计算用户影响率。

用户交互是以用户网络为背景的，首先应针对用户间的单双向关系构建用户网络。定义G=(V,E)代表整个用户网络，V为所有用户节点的集合，E代表用户间有直接关系的边的集合。对于vm，vn∈V，∈E，代表用户vm关注vn，则vm称为vn的粉丝。网络中每个节点都会附加该用户的状态信息及行为信息，分别储存在PROFILES和ACTIONS文件中。其中，状态信息包括微博数量、关键词等信息，行为信息包括用户间的转发、评论等一系列的互动操作信息。可通过对交互行为的分析来计算用户影响率。通常，用户交互行为包括微博的转发、评论、提及(@)和私信等。在以下所有分析中，均有vi，vj∈V，vj关注vi。

1) 关注度

伴随着粉丝微博的发布，被关注用户的微博也一同被推送到该粉丝的微博首页。因此粉丝关注的用户越多，收到的推送信息就越多，从而会使某用户的微博在数据更新迅速的微博平台上被粉丝看到的几率降低。定义关注度来衡量这种特殊的关系，用AS表示如下：

(2)

式中，Tweet(vi)和Tweet(vj)分别代表的是vi和vj在某时间段内发布的微博总数，Attention(vj)代表的是用户vj关注的用户集合。

2) 转发量

用户vi发布的微博被推送到vj的首页时，若vj对vi发布的某条微博感兴趣，可对其进行转发操作，则该微博就被分享并推送给用户vj的粉丝，此情况下微博的传播范围被扩大。转发量作为衡量用户影响率的指标之一，用FS表示如下：

(3)

式中FS(vi,vj)代表用户vj对vi的转发量，Forward(vi,vj)是用户vj对vi转发次数总和，Forward(vj)表示用户vj对所有用户转发次数总和，Forwarded(vi)表示用户vi被所有用户转发次数总和。转发量越大，用户vi对vj的影响也就越大。

3) 评论量

当用户vi的微博对vj产生影响时，vj也会对其进行评论，评论越多证明该用户对其影响越大。用CS来表示评论量：

(4)

式中，CS(vi,vj)代表用户vj对vi的评论量，Comment(vi,vj)代表用户vj对vi进行评论的总次数，Comment(vj)表示用户vj对所有用户进行评论的总次数，Commented(vi)表示用户vi被所有用户评论的总次数。评论量越大则证明用户vj对vi越关注。

4) 提及量

@操作是微博平台上极具特色的操作，一般出现在微博内容中，表示发出者提及接收方来读取该微博信息，是用户交互行为的一种，该操作多出现在密友中。用MS表示提及量：

(5)

式中，MS(vi,vj)表示用户vj对vi的提及量，Mention(vi,vj)为用户vj提及vi的总次数，Mention(vj)表示用户vj提及其他所有用户的总次数，Mentioned(vi)表示用户vi被所有其他用户提及的总次数。提及量越大，信息交互越频繁，更能够促进信息的传播。

5) 私信值

私信是微博平台新上线的功能，用户间可以相互发送私信，体现了用户间的亲密和互动的程度。用DM表示私信值如下：

(6)

式中Direct(vi,vj)代表的是用户vi和vj的私信总次数，Direct(vj)表示用户vj私信所有用户的总次数，Directed(vi)表示用户vi被所有用户私信的总次数。

6) 关键词相似度

关键词集合是描述用户擅长领域或话题的集合。若两个用户的关键词有交集，表示二者有着相同的爱好，微博数据就更有可能在二者间传播。关键词数据格式为(keyword1,weight1;keyword2,weight2;…)，分别代表该用户的关键词及与之相对应的权重。则两个用户的关键词相似度KS表示如下：

(7)

式中，两用户关键词集合总大小为s,wik和wjk分别代表该公共关键词在两用户集合中相应的权重。

7) 用户影响力的计算

(8)

为解决不同评价指标间量纲不同的问题，需将数据进行标准化处理，使各指标处于同一数量级，适合进行综合对比评价。因此，对IR(vi,vj)进行线性变换，使其结果映射到[0,1]之间。

(9)

式中,INF(v)和INF(v′)分别代表用户v和v′的影响力，IR(v,v′)和IR(v″,v′)分别代表用户影响率。式中F(v)代表用户v的粉丝集合，Attention(v′)代表的是用户v′关注的用户集合，d是阻尼系数。对式(9)进行迭代可以求出网络中所有节点的影响力INF。

2 影响力最大化模型设计

根据本文提出的影响力计算方法可求得各节点的INF值，从而得到用户影响力的排序。INF值越大的用户，对信息的传播贡献就越大。假设某一INF值较小的用户A拥有INF值较大的粉丝B，此时A的微博数据可以被B在较大的范围内传播。若直接选取INF排名靠前的k个节点作为目标数据，很可能忽略网络中的弱连接点，导致k个节点集中在一个簇内，不能保证最终获取到的用户节点影响范围最大。因此需要建立符合微博网络特征的影响力最大化模型来寻找能够影响最多用户的节点。

2.1 影响力最大化定义

定义2 在已知的网络G中，给出特定的影响力INF(v)来求解集合S(k)，集合大小为k。S(k)需满足以该集合中节点为初始节点遵循影响力传播模型进行传播，最终能激活节点数目最多。即获取k个用户，使其具有最大的传播范围。

LTM模型[15]是一种经典的基于节点的传播模型。已知社会网络G=(V,E)，定义N(v)={u|(u,v)∈E}表示节点v在网络G中的邻居节点集合，buv是已激活节点u对它未激活邻居节点v的影响力，且∑u∈N(v)buv≤1。定义N(v)中已激活节点集合为A(v)，每个节点v均有一个特异性阈值θv，在∑u∈A(v)buv≥θv的条件下节点v被激活。

信息扩散步骤如下：

Step1 给定初始传播种子集合S0，buv为节点u对v的影响力，θv为节点v被激活的阈值。

Step2 在第t步扩散时，满足激活条件的基于集合St-1节点将形成新集合St。

Step3 程序循环进行，直到不再有新节点被激活。

2.2 最大化模型设计

LTM是基于节点的价值积累传播模型，其中buv是通过社交网络中u对v的影响权重来计算的。但在微博平台中，当用户被抽象为节点后，各节点间是通过双向交互来激活网络中的其他节点，最终促进信息传播。因此应根据微博自身的特征设计最大化模型来满足影响力最大化的需要。

通过本文对微博的深入分析，根据式(9)可计算出每个用户的影响力INF。各用户通过双向交互对其邻居节点的影响力bvv′可表示如下：

(10)

(11)

其中，V是用户集合，S是已激活节点集合。由式(11)计算后选取SeedFind值最大的节点为初始种子节点。

根据上述分析，设计具有微博特征的影响力最大化模型表示如下：

Step1 根据式(9)迭代计算所得的用户影响力INF值代入式(10)计算出传递概率bvv′。初始状态集合S为空。

Step3 由式(11)计算出指标SeedFind值。

Step4 将SeedFind值最大的节点作为种子节点，以bvv′为传递概率进行节点扩散。

Step5 每一步扩散都选取传播范围增量最大的节点，并将此节点添加到集合S中。

Step6 集合S.size=k，传播结束。

3 算法实现

本文综合微博自身特征及用户属性，提出一种基于用户影响力的微博数据提取算法来提取微博数据，核心步骤如下：

Step1 采用模拟登录技术获取微博用户初始数据，并对其进行结构化和预处理，获得用户关系。

Step2 构建用户网络，同时得到PROFILES和ACTIONS两个文件用来储存用户信息。利用式(2)-式(7)分别计算出AS(v,v′)、FS(v,v′)、CS(v,v′)、MS(v,v′)、DM(v,v′)、KS(v,v′)。

Step3 根据以上计算结果，利用式(8)计算出IR(v,v′)。

Step4 为用户INF赋初值1/n，并对式(9)进行迭代，依次求出网络中所有用户的影响力INF。

Step5 根据式(10)、式(11)计算出用户的SeedFind值和传播概率bvv′。建立基于微博特征的最大化模型，最终获取到大小为k的用户集合S。

Step6 根据集合S中的节点，应用爬虫技术提取相应的微博并存储，算法结束。

根据以上各步骤，将算法用伪代码表示如下：

Input: G=(V,E),PROFILES ,ACTIONS ,c,k,θv

Output: the Top-k node set S

1: for each edge ∈E do

2: calculate AS(v,v′),FS(v,v′),CS(v,v′),MS(v,v′),DM(v,v′),KS(v,v′) respectively

3: calculate IR(v,v′)

4: end for

5: set the initial influence value to 1/n,where n is the total number of nodes

6: while (ratio > Threshold)

7: for each v in V do

8: for each v′∈F(v)

9: get the value of IR(v,v′) and INF(v′)

10: for each v″∈ Attention(v′)

11: get IR(v″,v′),then accumulate them and assign to sum

12: end for

13: INFt+1(v)+=IR(v,v′)*INFt(v′)/sum

14: end for

15: INFt+1(v)=INFt+1(v)*c+(1-c)/n

16: end for

17: ratio=max(INFt+1(v)- INFt(v))/max(INFt+1(v))

18: end while

19: for each v in V do

20: get the value of INF(v),then accumulate SeedFind(v)

21: end for

22: Order SeedFind(v) by desc,then Initialize S=φ

23: v = List[0],S = S∪{v},i=1

24: while |S|<=k

25: v = List[i]

26: while v=argmax(I(v)i- I(v)i-1)

27: S = S∪{v}

28: i ++;

29: end while

30: end while

31: return S and extract the data

算法中I(v)代表以节点v为种子进行传播所激活的节点集合，其中I(v)i-I(v)i-1表示当前节点新加入后所激活节点的增量。因此该算法最终输出大小为k的集合S中的元素都是最具传播能力的节点。然后将这些用户的微博数据提取存入数据库，完成数据提取。

4 实验与分析

4.1 实验环境及初始数据准备

为验证本文提出的基于用户影响力的微博数据提取算法的有效性，设计实验进行验证。测试机器为Lenovo Y460服务器，Intel(R)Core(TM)i5 CPU，4 GB内存，运行环境为Windows 8.1平台下的Microsoft Visual Studio 2010，使用C#语言进行开发和实现。本文基于浏览器模拟登录技术完成微博平台的认证，再通过设计爬虫算法以得到实验的初始用户数据。模拟登录后可获取用来识别用户身份的cookie数据。将cookie作为访问微博的header参数提交request给服务器，可以收到服务器的response反馈。在提交POST请求之前，需要GET 获取“servertime” 和 “nonce”两个参数的值，通过HttpFox观察POST的数据，其中 “su”是加密后的username,“sp”是加密后的password，最终实现模拟登录。认证成功后便可爬取用户信息，再对得到的数据进行结构化和预处理(过滤僵尸用户等)即可完成初始数据的准备工作。数据集描述如表1所示。

表1 数据集情况

表1显示了实验获取到的8756个用户，以及用户间的单双向关系总量，将其抽象为节点和边建立用户网络G=(V,E)。用户的状态信息和行为信息分别以JSON数据格式储存在PROFILES文件和ACTIONS文件中。

4.2 实验评估及分析

算法通过设定比率ratio来控制收敛，该值为迭代过程中用户影响力的增量最大值与最大值的比值。当该比值小于已设定的门限值Threshold时终止循环。图1显示了实验过程中比率ratio随着迭代次数增加的变化情况。

图1 迭代次数与比率ratio变化关系图

图1中显示了进行0～100次迭代ratio值的变化情况，ratio的值随着迭代次数的增加而不断减小。进行70次迭代后，ratio已经减小到10-5数量级，已经非常接近0，可以认为该循环结束，因此门限值Threshold可设为10-5，即计算过程中循环进行70次结束。迭代结束后可以计算出用户影响力值，其分布情况如图2所示。

图2 INF值分布图

图2中显示出实验数据集内INF值的分布情况，INF较大的用户集中在小范围内，更多用户集中在INF值较小的范围内。为防止弱连接点的丢失，需进行影响力最大化计算来扩大影响力的范围。提取结果数据集中INF值Top 10用户与影响力最大化后的Top 10节点进行对比说明，如表2和表3所示。

表2 用户影响力INF值Top 10

表3 影响力最大化后微博用户Top 10

通过对比两表中的数据，可见INF值大的用户与影响力范围最大化后的节点集合S不完全相同，INF排名靠前的用户不一定出现在集合S的Top-k中。原因是某些INF小的用户可能拥有INF较大的粉丝，这些粉丝对当前用户的微博进行转发后，相当于影响力较大的用户发布了该微博，从虚拟的角度增大了当前用户的影响力，所以在结果集S中出现INF值小的新用户，从某种程度上初步体现了本文算法获取数据范围广的优点，保证网络中弱连接点不被忽略。

为进一步验证本文算法的有效性，与PageRank算法以及TwitterRank算法进行对比。将PageRank算法结果按降序排列并取出Top-k节点构成集合P1，同理TwitterRank算法对应集合P2，与本文算法最终输出集合S分别对比。定义相似性分别为H1、H2：

(12)

H1、H2的计算结果如图3所示。

图3 相似性曲线

由图3可看出，H1、H2随着抓取目标集合大小k的增大均呈现先下降后平稳上升的趋势。这是由于随着获取节点的不断增多，弱连接点也随之增多，当一些弱连接点被挖出时，相似性就会相对降低；当获取节点个数持续增多时，弱连接点的个数由于不断被挖掘出来而减少，此时相似性就呈现出稳定增长的状态。该对比进一步验证了本文算法的正确性和获取数据完整的优点。

为验证本文算法获取数据质量高，选取本文算法(以下简称Our method)、PageRank算法、TwitterRank算法以及爬虫算法(Web Spider)的实验结果集进行对比。四个集合中分别选取前十个节点作为种子节点，以bvv′为传播概率构成传播模型来模拟微博数据在微博平台上的传播情况。在选取同样数量种子节点的情况下，所激活的节点个数情况如图4所示。

图4 激活用户节点个数比较

图4中各曲线可看出，在种子集合大小一样的情况下，四种算法激活的节点数都呈上升趋势，其中爬虫算法激活的节点最少，本文算法激活的节点最多，PageRank和TwitterRank算法则居中。这意味着本文算法获取到的用户对数据具有最强的传播能力，可使数据传播的范围更广，对舆情的形成具有更重要的意义，因此依据本文算法提取到的微博数据质量更高。为将四种算法进行效率对比，实验利用获取相同个数节点所消耗的时间来评估各算法的效率。实验结果如图5所示。

图5 各算法执行性能比较

由图5可以看出，在获取相同数量节点的情况下，爬虫算法耗时最长，本文算法与PageRank算法耗时基本接近，TwitterRank居中。本文算法在耗时上相对于爬虫算法和TwitterRank算法具有明显的优势。由于本文需要进行最大化计算，在保证耗时与PageRank基本相同的情况下获取到的数据质量更高，相对提高了数据的获取效率。

将本文算法提取的微博数据集与PageRank算法以及TwitterRank算法获取的用户数据进行对比。将三者的数据集分词后应用LDA模型，进行热门话题检测，比较召回率、准确率和F值，如表4所示。

表4 话题测评结果对比

表4中可看出，本文算法提取的数据在话题检测中较其他两种算法占优势，性能较PageRank算法提高约3.79%，较TwitterRank算法提高约1.89%。因此本文算法获取的数据质量更高，更能满足舆情分析的需要。

5 结 语

本文针对舆情分析的要求提出一种基于用户影响力的数据提取算法。通过详细分析用户间的双向交互最终实现微博数据的有效获取。通过设计实验验证了本文算法可以减少用户网络中弱连接点的丢失，保证抓取目标数据的完整性和准确性。通过与其他算法的性能对比，验证了本文算法可以有效提取高质量的微博数据，为进一步进行舆情分析提供了良好的条件。但在算法执行时间上应考虑到并行化，这将是后续研究的方向。

[1] 丁兆云,贾焰,周斌.微博数据挖掘研究综述[J].计算机研究与发展,2014,51(4):691-706.

[2] Kwak H,Lee C,Park H,et al.What is Twitter,a Social Network or a News Media?[C]//Proceedings of the 19th International Conference on World Wide Web.New York:ACM,2010:591-600.

[3] 高凯,王九硕,马红霞,等.微博信息采集及群体行为分析[J].小型微型计算机系统,2013,34(10):2413-2416.

[4] 陈舜华,王晓彤,郝志峰,等.基于微博API的分布式抓取技术[J].电信科学,2013,29(8):146-150,155.

[5] 廉捷,周欣,曹伟,等.新浪微博数据挖掘方案[J].清华大学学报(自然科学版),2011,51(10):1300-1305.

[6] 卢体广,刘新,刘任任.微博数据通用抓取算法[J].计算机工程,2014,40(5):12-16,20.

[7] 马俊,周刚,许斌,等.基于个人属性特征的微博用户影响力分析[J].计算机应用研究,2013,30(8):2483-2487.

[8] Aizawa A.An information-theoretic perspective of tf-idf measures[J].Information Processing & Management,2003,39(1):45-65.

[9] Weng J,Lim E P,Jiang J,et al.TwitterRank:Finding Topic-sensitive Influential Twitterers[C]//Proceedings of the Third ACM International Conference on Web Search and Data Mining.ACM,2010:261-270.

[10] Phan X H,Nguyen L M,Horiguchi S.Learning to Classify Short and Sparse Text & Web with Hidden Topics from Large-scale Data Collections[C]//Proceedings of the 17th International Conference on World Wide Web.ACM,2008:91-100.

[11] 毛佳昕,刘奕群,张敏,等.基于用户行为的微博用户社会影响力分析[J].计算机学报,2014,37(4):791-800.

[12] Liu Y.Influence Maximization in MicroBlog Based on a New User Influence Ranking Method[J].Journal of Information and Computational Science,2015,12(9):3729-3737.

[13] 张昊,刘功申,苏波.一种微博用户影响力的计算方法[J].计算机应用与软件,2015,32(3):41-44.

[14] 平宇,向阳,张波,等.基于MapReduce的并行PageRank算法实现[J].计算机工程,2014,40(2):31-34,38.

[15] 陈浩,王轶彤.基于阈值的社交网络影响力最大化算法[J].计算机研究与发展,2012,49(10):2181-2188.

MICROBLOG DATA EXTRACTION ALGORITHM BASED ON USER INFLUENCE

Tian Feifei Shen Jiquan

(CollegeofComputerScienceandTechnology,HenanPolytechnicUniversity,Jiaozuo454000,Henan,China)

As one of the main sources of basic data in public opinion analysis,the microblog is a key problem in data acquisition.For this issue,a data extraction algorithm based on user influence is proposed in order to meet the needs of public opinion system for data.First,the algorithm uses the simulation login technology to obtain the user relationship and builds the user network,and then calculates the user influence with the independent design user influence calculation method in order to establish the influence of microblog features to maximize the ability of the model and dig out the mostknodes.Finally,it uses the conventional crawler technology to climb the corresponding microblog data.Experiments show that this algorithm is able to improve the quality of the data effectively and provide better data support for public opinion analysis.

Public opinion Microblog DATA acquision User influence Range maximize

2015-09-09。国家自然科学基金面上项目(61175066)。田霏霏，硕士生，主研领域：舆情分析，数据挖掘。沈记全，教授。

TP39

A

10.3969/j.issn.1000-386x.2017.01.010