基于PageRank的热点发现混合算法研究

应 毅，黄 慧，刘定一

(三江学院 计算机科学与工程学院，江苏 南京 210012)

0 引 言

近年来，随着互联网技术的发展，微博、微信等新兴微媒体受到大众广泛关注，被作为获取时事要闻、发表个人意见的主要途径。由于网络热点事件具有传播速度快、范围广的特征，使得微媒体平台在事件爆发后，能迅速积累大量的热点信息。从微媒体的海量信息中挖掘热点话题，有助于政府机关和相关部门及时掌握互联网事件的主导权，积极传播正能量，是当前微媒体热点引导工作面临的重要任务。

对于热点问题的发现，除了传统的针对文本信息的聚类、分类等数据挖掘技术外，近年来也广泛采用基于联系的链接分析技术。PageRank[1-2]是进行网页权重计算的链接分析算法，起源于文献引文分析方法[3]，主要思想是依次统计每个网页的入度和出度，入度为当前网页被其他网页引用的次数，且次数越多，说明该网页的质量越高；出度为当前网页引用其他网页的次数，算法通过迭代的方式反复计算每个网页的PageRank值[4]，直至达到平稳分布为止。搜索引擎即通过PageRank算法分析互联网上网页间的相互引用关系，进而衡量网页的重要程度。

基于这一思想，学者们针对热点话题的挖掘展开了广泛的研究。文献[5]将主题特征和时间因子引入PageRank算法进行热点分析，与传统方法相比，获得了更为可靠的分析结果。文献[6]提出网页时间权值的概念对热点问题进行分析，通过新方法弥补了传统算法中新网页总是处于“弱势”地位的不足，强调最新发布网页的重要性，对网页的排序搜索起到了优化的作用。文献[7]引入时间维和空间维的主题因子，为网络舆情处理提供主题样本。

此外，学者们还从词频热度、事件要素、情感趋势等多个角度结合PageRank算法来分析热点问题，都取得了一定的进展[8-12]。

1 热点发现研究现状及文中工作

微博作为大众获取信息的重要来源，在热点发现和舆情把控方面发挥了重要作用。使用传统的PageRank算法对微博数据进行热点挖掘时，会产生以下几个问题：

(1)微博不同于网页，没有频繁的入度与出度，因此无法直接使用PageRank算法获取每篇博文的重要程度。

(2)传统算法未考虑文本之间的相似度，一般而言，相应时间段内某个主题内容被提出的频次越高，说明该主题内容被关注的大众越多，越易成为热点话题。

(3)微博通常存储了博文的转发数、评论数和点赞数等数据，这些数据也应被充分利用以发现热点话题。

针对以上问题，文中通过网络爬虫工具对新浪微博的数据进行爬取，并从多角度对数据加以分析，获取更为可靠的热点话题。文中的贡献如下：

(1)引入微博用户的社会地位，通常用户的粉丝数越多，其社会地位越高，该用户发表的博文影响力也越大，越易被传播。文中将用户的社会地位融入PageRank算法，将用户之间拥有的粉丝信息形成链接结构，通过计算每位用户的PageRank值来衡量其社会地位，PageRank值越高，其社会地位也越高。

(2)将TF-IDF算法与余弦相似性算法结合进行博文之间的相似度计算，若时间段内某篇博文的相似文章数量较多，说明该时间段内此话题被多个用户关注，是热点话题。

(3)充分利用博文的转发数、评论数和点赞数等数据形成热度指数，热度指数越高，说明博文的影响力越大，越易形成热点。

文中在PageRank算法和相似度计算技术的基础上进行改进，提出热点发现混合算法(hotspot detection hybrid algorithm based on PageRank and similarity computation，HDH-PRSC算法)。

2 HDH-PRSC算法

HDH-PRSC算法思想是通过计算每篇博文的评分获取热点信息，其中博文评分由三部分组成：微博用户的社会地位、文本相似度分值和热度指数。热点分析时，将算法产生的三项值做加法运算，得到的总评分越高，则博文成为热点的可能性越大。

2.1 微博用户的社会地位

基于PageRank算法的基本思想计算微博用户的社会地位。

定义1(合法用户)：U={U1,U2,…,Un}为所有微博用户集合。如果满足Ui∈U且1≤i≤n，则称Ui为集合中的合法用户，简称用户。

定义2(合法粉丝)：V={Vi1,Vi2,…,Vim}为用户Ui的粉丝集合。如果满足Vij∈V且1≤j≤m，则用户Uj是用户Ui的合法粉丝，简称粉丝，记作Vij。

定义3(链接结构图)：每个用户形成图中的一个节点，如果用户Uj是用户Ui的粉丝，则形成Uj节点至Ui节点的一条有向边，指向Ui的边数称为Ui的入度。同理，Ui也可作为其他用户的粉丝，Ui节点指向其他用户的边数称为Ui的出度。由节点和有向边形成的图称为链接结构图。

基于PageRank算法的基本原理，微博用户的社会地位计算方法如式1所示。

(1)

其中，Ui为某个待评价的用户；j为用户i的粉丝数；U为用户总数；N(Vij)为用户Ui的第j个粉丝节点的出度；PRstatus(Ui)为用户Ui的社会地位值；PRstatus(Vij)为用户Ui的粉丝的社会地位值；d为用户之间彼此链接的阻尼系数，依据经验，通常取值为0.85。

按照式1对用户的社会地位值进行迭代运算，由于该算法是收敛的，直到用户的社会地位值趋于平稳，则计算结束。

通过算法获取每位用户的社会地位PageRank值并对PageRank值从高至低排序，同时计算所有用户的PageRank值的平均值，记为AVG(PR)。为提高算法运行效率，依据AVG(PR)，将用户的社会地位划分为三类：

e为用户定义的阈值，通常情况下，消极用户的发文成为热点的概率较低，因此计算热度时，不考虑消极用户的发文，以此提高算法效率。

算法1：计算微博用户社会地位的算法为GetUserStatus，其伪代码如下：

输入：链接结构图,e值；

输出：PRstatus(Ui)(Ui∈ActiveUser &&Ui∈NormalUser)。

FOREACHUi∈U

BEGIN

Array[i,0]=GetPRstatus(Ui)//获取每个用户的社会地位的PageRank值

Array[i,1]=UserID(Ui)//获取用户的UserID赋值给数组

Array[i,2]=NULL//用户初始的状态为空

END

SORT(Array) //对用户的社会地位从高到低排序

PRAvgStatus=AVG(PR) //计算所有用户的社会地位均值赋值变量PRAvgStatus

FOREACHiin Array

BEGIN

IF(Array[i,0]>=PRAvgStatus+e)

Array[i,2]=ActiveUser

ELSE IF(Array[i,0]>=PRAvgStatus-e&& Array[i,0] <= PRAvgStatus+e )

Array[i,2]=NormalUser

ELSE

Array[i,2]=InactiveUser

END

DELETE(InactiveUser)

2.2 博文相似度指数

当某篇博文具有较多的与其相似度较高的其他博文时，说明该博文可能是某时间段内的热点话题，被较多的用户关注。因此，统计博文的相似度指数，也是热点发现研究中的重要指标。文中通过结合TF-IDF[13]方法和余弦相似性算法[14]获得博文的相似度指数。

定义4(TF-IDF)：TF-IDF是用于评估一个字词对于一个文件集或一个语料库中的其中一份文件的重要程度。其中TF(term frequency)表示词条在文章中出现的频率；IDF(inverse document frequency)表示包含某个词的文档越少，则这个词的区分度就越大，即IDF越大。

TF=某个词在文章中出现的次数/文章总词数

(2)

IDF=log[词料库的文档总数/(包含该词的文档

数+1)]

(3)

TF-IDF=TF×IDF

(4)

通过统计TF-IDF的值，将每篇博文取值较高的前四个词作为该篇博文的关键字。

定义5(余弦相似度)：余弦相似度利用向量空间中两个向量夹角的余弦值作为衡量两个个体间差异的大小。文中将两篇博文的关键字分别作为空间向量，计算相似度，公式如下：

(5)

其中，Xi为X文档中第i个关键词出现的次数；Yi为Y文档中第i个关键词出现的次数。通过式5计算向量的余弦值，余弦值越接近1，表明夹角越接近0，则两篇文档越相似。

统计博文相似度指数的过程分为三个步骤：

步骤一：利用TF-IDF方法获取每篇博文的关键词，并对关键词出现的次数进行排序，获取Top-K个关键词；

步骤二：依次遍历博文，删除不包含关键词的博文；

步骤三：将剩余的博文对应的关键词按照余弦相似性的方法比较相似度，同时利用DBSCAN算法[15]对博文进行聚类，统计相似博文的篇数。博文的相似度指数为每篇博文的相似篇数与总篇数的比值。

其中DBSCAN是一种基于密度的聚类算法，基本思想是在样本区域内任意选择一个核心对象，以核心对象为中心计算与该核心对象的距离小于ε的其他所有对象，并将这些对象组合成一个类簇，将剩余对象作为输入进入下一轮算法的迭代，直到样本空间中的所有对象都划分为某个类簇，算法结束。文中的核心对象为算法输入中的任意一篇博文，ε为Sim(X,Y)的取值，即博文相似度。

算法2：统计博文相似度指数的算法为GetSimScore，其伪代码如下：

输入：活跃用户与一般用户的博文文章，k值，相似度阈值m；

输出：每篇博文的相似度指数。

FOREACHTi∈Title

BEGIN

Array[i,0]=GetKeyWords()//通过TF-IDF方法获取文章关键字

Array[i,1]=TitleID(Ti)//获取文章ID号

END

FOREACHjin KEYWORDS

ArrKeyWords[j]=COUNT(Array) //统计每个关键字出现的次数

string[] ArrImpKeyWords=SORT(ArrKeyWords,k)//获取前k个重要关键字

FOREACHTi∈Title

BEGIN

IF !Ti.Contains(ArrImpKeyWords) //判断博文Ti是否包含重要关键字

DELETE(Ti) //如果不包含重要关键字,则删除博文

END

FOREACHTi∈Title

FOREACHTj∈Title

BEGIN

IF Sim(Ti,Tj)>=m

DBSCAN() //如果两篇博文相似度达到阈值，则调用DBSCAN算法进行聚类

END

FOREACHTi∈Title

SimScore(Ti) //获取每篇博文的相似度指数

2.3 热度指数

定义6(热度指数)：热度指数由转发数、评论数和点赞数的总和得到，热度指数越高，说明此博文成为热点的概率越大。

热度指数的计算公式如下：

HotScore(Ti)=(转发数+评论数+点赞数)/(总转发数+总评论数+总点赞数)

(6)

2.4 HDH-PRSC算法的实现

博文的最终热度综合评分由微博用户的社会地位、博文相似度指数和热度指数三项分值获得，如下：

Score(Ti)=αUserScore(Ui)+βSimScore(Ti)+

γHotScore(Ti)

(7)

其中，α、β和γ分别为微博用户的社会地位、博文相似度指数和热度指数的评分系数，且α+β+γ=1。

算法3：HDH-PRSC算法。

输入：α值,β值,γ值；

输出：博文综合评分。

FOREACHTi∈Title

BEGIN

Ui=GetUserByTitle(Ti)//通过Ti获取博文的用户Ui

UserScore=GetPRstatus(Ui)

SimScore=SimScore(Ti)

HotScore=HotScore(Ti)

RETURNα*UserScore+β*SimScore+γ*HotScore

END

3 实验结果及分析

采用网络爬虫对新浪微博数据进行采集，数据集包括2018年8月25日-2018年8月30日期间4 000个微博用户共864 000条博文。删除明星等名人的博文信息，随机抽取部分数据作为实验基础，数据字段包含用户UserID、性别、用户粉丝信息、微博数、微博ID、微博内容、微博发布时间、阅读数、转发数、评论数和点赞数。

实验操作时，用来给用户分类的阈值e设置为AVG(PR)×0.2；计算博文相似度指数时，相似度阈值设置为0.6；式7中的α、β和γ均设置为1/3。由于实验数据规模较大，最终计算得到的用户地位评分、相似度指数和热度指数值均介于0.000 1～0.000 4之间。实验搜索到的热度文章以及各项算法的评分结果如表1所示。

表1 热度博文及评分

通过实验发现，单一算法(如：基于PageRank的用户社会地位计算、结合TF-IDF和余弦相似性的博文相似度计算)得到的结果和HDH-PRSC算法得到的热点博文排序不尽相同，E2事件在PageRank算法中排序第1，但在HDH-PRSC算法中排序第2；E3事件在相似度计算中排序第2，但在HDH-PRSC算法中排序第3。如图1所示，单一算法所得结果相对比较片面，如PageRank算法将E2事件排名第1是因为该博文的发布者是央视财经，算法认为只要是央视财经发布的博文一定都是热点，而实际情况并非如此；同理，E3事件在相似度计算中排名第2是因为其类似文章的出现次数较多，这有可能是因为一个小团体内多次转发了某篇广告，仅凭此项因素判断热点缺乏充足依据。HDH-PRSC算法综合了发文用户的社会地位、博文相似度指数、热度指数三个因素，更加全面地从多个角度综合评价博文的热度，思想更为合理，其计算结果也要优于单一算法。

图1 热点发现算法比较

4 结束语

基于用户社会地位、博文相似度指数以及热度指数对微博数据进行分析，提出一种基于PageRank和相似度计算的热点发现混合算法。该算法弥补了传统算法中未考虑用户社会地位和文本相似度的不足。实验结果表明，HDH-PRSC算法能够更为合理地发现热点话题。下一步将在更大规模的数据集上进行实验分析，并研究如何通过算法获取文中α、β和γ评分系数的合理取值，以得到更为理想的实验效果。