基于链接和萤火虫算法聚类博文发现热点话题

王雅琳，陆向艳，钟 诚

（广西大学 计算机与电子信息学院，广西 南宁530004）

0 引 言

基于纯文本的热点话题发现方法未考虑网页文本的特殊性，获得的结果准确度不高［1－3］，为此，研究者开始关注网页特征，在文本挖掘的基础上加入链接分析。文献 ［4］在内容计算网页相似度的基础之上，引入链接分析，提高了话题相关性度量的准确度；文献 ［5］通过页面链接来估计信息的传播性质，并对信息的热度进行度量；文献 ［6］运用复杂网络理论构建文本的加权复杂网络模型，从而形成更准确的文本特征值。文献 ［4－6］在基于文本挖掘的基础上与链接分析相结合，一定程度上提高了话题发现的准确度，但未能避免文本向量化及特征提取等耗时的文本处理，因此计算复杂度较高。为处理大规模Web数据挖掘以实时发现舆情热点，基于链接分析的热点发现方法被提出。HITS算法［7］以及PageRank算法［8］利用链接分析的方法来获得网页排名。这些方法仅以网页之间的链接为研究对象，通过分析链接关系找到热点话题。文献 ［9］将HITS算法和PageRank算法相结合，给出一种基于链接分析的网络舆情热点发现方法，该方法计算复杂度较低，但该方法的页面权重完全依赖与之有链接关系的页面的质量，而页面的质量仅靠链入链出数量来决定，这种页面权重计量方法易受作弊链接的影响，即为了提高的网页排名，作弊者自行加入许多指向权威页面的链接，且其未考虑页面的时效性，相对发布时间较早的网页易获得更高的网页权重，其对链接未加以选择，且对所有的链接均赋予相同的权重。因此，该方法仍然未能解决HITS算法和PageRank算法存在的抵抗作弊链接能力较弱的缺陷以及主题漂移问题。

本文的主要贡献是：利用复杂网络簇结构高度主题相关的特点，以页面为节点，将清洗后的链接作为边，并考虑了时间因素对页面权重的影响，页面权重由博文及博主的相关属性综合评定，从而建立博客话题模型；采用萤火虫算法对形成的无向有权图进行聚类获得聚类中心，将聚类中心按页面权重从大到小排序，最终形成热点的话题热度排行；设计实现一种有效避免作弊链接不良影响、克服主题漂移现象、可挖掘出精度更高且数量更多的博客热点话题算法。

1 博客话题模型

1.1 模型结构

文献 ［10］阐述了因特网属于复杂网络，网络簇结构具有同簇节点连接密集、异簇节点连接稀疏的自组织特点，并且证实了自组织方式形成的Web 簇具有高度主题相关性。相较于因特网上的其它信息，博客领域的话题更加分散且观点呈现个性化特征，表述也更规范，并且通常代表一种相对单一的观点。

为了从博主所发的博文中高效准确地挖掘出热点话题，本文在文献 ［11］给出的网络社区话题结构的基础上设计了一个博客话题模型，该模型由博文层、事件层和话题层组成，如图1所示。最底层是博文层，即原始网络，主要是由博主发出的博文以及相关链接组成。中间层为事件层，该层是将博文层中不同博主发出的关于某一事件的博文聚在一起，形成对该事件较为全面的描述。顶层是话题层，它将事件层中的同类事件聚合在一起，形成一个话题。该话题的核心即是影响力最大的博文，博文的博主即为该话题的精神领袖。在博文层，博文由博文热度、链接以及链接权重组成，第m 个博文的表示方式为Articlem＝ ｛Articlehotnessm，Linkm，Linkweightm｝；事件层的事件由博文组成，Eventp表示博文集中的第p 个事件，Eventp＝ ｛Article1，…，Articles｝；话题层中的话题由事件组成，Topicq表示博文集中的第q 个话题，Topicq＝ ｛Event1，…，Eventr｝。

1.2 博文热度

图1 博客话题模型的三层结构

在博客领域，博主被关注的人数越多，所发出的博文被评阅以及收藏转发的可能性就越大；博文的阅读量越大，表明该博文受到的关注度越高；评论数及收藏量越大，表明该博文获得的认可度越高博文被转发的可能性就越大；博文的转发量表明该博文获得的推荐度。因此，博主的感召力以 “关注人气”的人数来体现，博文热度则以博文的“阅读量”、 “收藏量”、 “评论数”以及 “转发量”来综合体现。

为充分体现博文的热度，本文综合考虑了博主及博文两类属性。为消除因发布时间不同而造成博文热度存在的差异，本文提取博文 “发布时间”作为平衡热度的因子。博文页面Xm的热度计算公式为

式中：Δt（Xm）——博文Xm发布时间与当前时间之间的时间间隔，k——衰减系数，依据关注人气a（Xm）取值，k初值为0，a（Xm）每增加5000则k增加0.1［12］，c（Xm）为博文Xm的阅读量，z（Xm）为博文Xm的收藏量，f（Xm）为博文Xm的评论数，r（Xm）为博文Xm的转载量，m＝1，2，…，n，n为博文页面数，χ、ε、φ和η分别为相关系数，χ调节数量级，ε、φ和η满足ε＋φ＋η＝1。

1.3 链接选择

已有的基于链接分析的热点发现方法对链接未加以选择，且对所有的链接均赋予相同的权重，经多轮迭代后，将会使密集链接区域中主题不相关但链接数很多的页面具有过高的权重，即形成了主题漂移现象。为克服此现象，本文通过链接清洗来摒弃主题无关的链接，且通过博主以及博文的相关属性来直接评价博文热度，从而避免了因只依赖链接而赋予页面权重引起的网页排名不准确的问题。

博文页面链接主要有两种：一是博文到博主的链接，博主每阅读、评论、收藏一篇博文，均在该页面形成一条指向该博主的博客链接，这种链接表达了博主之间的关系；二是博文到博文的链接，包括博文的转发链接、相似博文的链接以及博主的其它博文链接。为了最大限度地减少作弊链接对计算页面热度的影响，本文方法对相关链接进行清洗后，仅抽取转发链接以及相似博文链接来进行链接分析。这两种链接关系能够将相似主题联系起来，经聚类后形成同一话题。

利用已抽取的链接关系建立博文的邻接矩阵E

其中，eij取0或1，eij＝1表示页面i与页面j 之间有直接链接，eij＝0表示页面i与页面j 之间没有直接链接。

2 运用萤火虫算法聚类博文

为了获得权威的博客页面，要进行相似主题聚类。萤火虫算法具有自动识别簇、不依赖初始值且不预设聚类中心的特点，优于其它群智能优化算法［12，13］。因此，本文运用萤火虫算法［14］对博文聚类。

在运用萤火虫算法对博文进行聚类时，前期适当扩大搜索空间，将能有效地避免陷入局部最优，后期适当缩小搜索空间，将能快速确定最优值。本文利用混沌理论［15］控制搜索范围的参数α 在既定范围内获得较大的随机性，以使算法的聚类精度达到最优。

萤火虫算法中的参数与博客话题模型中的参数存在一一映射关系。萤火虫种群规模n映射博文页面集规模n，萤火虫个体m 映射博文页面Xm，萤火虫的最大吸引度β0 映射页面链接的权重eij，i，j＝1，2，…，n。

萤火虫的最大荧光亮度I0映射博文页面Xm的热度Hotness（Xm）

萤火虫的相对荧光亮度I 映射个体m 的适应度向量F（Xm）

式中：rij——萤火虫Xi与Xj之间的空间距离，γ——光强吸收系数。为了均衡I0与rij对相对荧光亮度I的调节力度，本文将个体m 的适应度向量F（Xm）的计算公式改进为

式中：δ——调节系数。

若F（Xi）＜F（Xj），则萤火虫Xi被吸引向萤火虫Xj移动，其位置更新公式为

式中：t——种群的代数，其初值为1，Xti、Xtj为萤火虫个体Xi和Xj所处的空间位置，random（）为 ［0，1］上服从均匀分布的随机因子；扰动项为αti（random（）－1/2）。

萤火虫个体m （博文页面Xm）在第t轮迭代计算更新个体m 的位置 （更新页面链接权值）时，取值范围为 ［0，1］的混沌参数为

式中：Dtm——个体m 在第t 轮迭代时的混沌变量。采用Logistic映射获得混沌序列［15］

3 博客热点话题发现算法

3.1 博客热点话题发现方法

融合运用链接分析与萤火虫算法聚类博文的热点话题发现方法如图2所示。具体步骤是：①解析域名，与目标网络建立TCP连接。②利用URL 模板来匹配获取的URL地址，若相符，则存入本地文档，否则丢弃。③根据页面模板抽取的相关属性值计算博文热度值，利用抽取的相关链接形成邻接矩阵。运用萤火虫算法对博文进行聚类后，提取各个话题簇的权威页面形成热点，然后将博文标题按照博文热度值排序，形成热点的话题热度排行。

图2 融合运用链接分析与萤火虫算法聚类博文的热点话题发现方法

3.2 算法描述

本文将博文页面映射成萤火虫个体，将寻找簇结构（相似博文聚成的话题）即聚类过程映射成萤火虫个体间的相互吸引和位置移动过程，并利用归一化开销控制萤火虫种群的迭代轮数。获得簇结构后，选取各簇亮度最大的萤火虫 （权威页面）作为聚类中心，萤火虫个体代表的博文页面即为博客热点话题。融合运用链接分析和萤火虫算法聚类博文的热点话题发现算法 （简记为Blog－IPO 算法）描述如下：

算法1：Blog－IPO 算法

输入：博文页面集

输出：热点排行

Begin

（1）对参数χ、ε、φ、η、γ、β0、α、δ、μ初始化；

（2）抽取博文页面Xm的相关属性，按式 （1）计算博文Xm的热度Hotness（Xm），m＝1，2，…，n；

（3）抽取Xm的转发链接及相似博文链接；

（4）形成邻接矩阵E；

（5）t＝1；

（6）for i＝1to ndo

（7）for j＝1to ndo

1）若eij＝1则按式 （4）计算萤火虫个体Xi、Xj的适应度向量F（Xi）、F（Xj）；

2）若F（Xi）＜F（Xj）则按式 （5）更新Xi的Xt＋1i；

3）按式 （7）和式 （8）计算αt＋1i；

（8）按后述的式 （11）计算归一化开销 （CDet）Norm，将第t轮迭代计算所得的归一化开销 （记为）与第（t－1）轮迭代计算所得的归一化开销进行比较，若＜则令t＝t＋1，转歩骤 （6），否则转歩骤 （9）；

（9）依据Xt＋1i形成聚类中心Xcenter，center＝1，2，…，h，h为聚类中心数目；

（10）将Xcenter的标题按照Hotness（Xcenter）从大到小排序；

（11）输出热点话题排行Topic1，Topic2，…，Topich；

End

Blog－IPO算法利用复杂网络的簇结构高度主题相关的特性建立博客话题模型，同时运用博文以及博主的相关属性来衡量页面权重，并提取博文的发布时间作为平衡热度的因子以消除因发布时间不同造成的热度差异，选取与博文内容相同或相关的链接形成邻接矩阵，并运用萤火虫算法对博文进行聚类形成聚类中心 （热点话题），克服了基于链接分析的舆情发现方法存在的主题漂移现象，并消除了作弊链接对页面排名的影响，提高了热点话题发现的准确度。

4 实 验

4.1 数据集

实验数据来源于新浪博客，利用开源工具HTML Parser解析目标博客网站的页面，然后利用模板匹配抽取相关信息。新浪博客抽取信息及属性见表1。

4.2 实验环境

本文的实验硬件环境为主频2.90GHz、4GB 内存、500G 硬盘的Intel奔腾双核G2020 计算机，操作系统为Windows XP，编程开发工具为VC＋＋6.0。

4.3 实验参数

本文实验采用的参数χ＝0.001、δ＝0.1、ε＝0.3、φ＝0.2、η＝0.5由文献 ［16］获得，μ＝4由文献 ［15］获得，控制聚类效果的参数α、γ由实验获得。文献 ［17］的研究表明当α∈ ［0，1］、γ∈ ［0，10］时算法性能较好，本文令α以间隔0.1、γ以间隔1的幅度变化构造55 对组合参数，用归一化开销作为聚类质量的评测标准对本文数据集进行测试。实验结果表明当α＝0.2、γ＝1时，归一化开销达到最低，即聚类质量最佳。

表1 抽取的信息及属性

4.4 实验结果

对博客而言，博文能够越多地被聚类到正确的话题簇中，并且能够识别出越多的话题，则说明该热点话题发现方法的性能越好。因此，本文从聚类博文精度以及发现话题的个数两个方面进行实验测试，并与文献 ［9］的方法（记为HITS－PageRank）对比结果。

4.4.1 博文聚类精度对比

实验抽取新浪博客专题模块中如下10个专题作为测试数据：韩国岁月号沉船事件、兰州自来水苯含量超标、文章出轨、中国大妈卢浮宫跳广场舞、内地小孩在港随地小便、房价下调、中纪委严惩贪污腐败、黑龙江火车脱轨案、城管被打、马来西亚人质。

依据TDT 评测标准，采用漏检率Pmiss、错检率Pfault以及归一化开销 （CDet）Norm来评价网络舆情热点发现方法的博文聚类精度

其中：Cmiss是Pmiss的代价常量，Cfault是Pfault的代价常量，Ptarget表示一个文本属于某个话题的先验概率，Ptarget＝1－Ptarget。根据TDT 评测标准，通常取Cmiss＝1、Cfault＝0.1和Ptarget＝0.02。

Blog－IPO 方法与HITS－PageRank方法对不同专题的漏检率、错检率结果如图3、图4所示。

由图3、图4可以看出，对于各个话题专题，Blog－IPO方法的漏检率均低于HITS－PageRank方法，Blog－IPO 方法的漏检率比 HITS－PageRank 方法的漏检率平均降低24.53%。这是因为本文提出的Blog－IPO 方法使用的链接均是话题的有效链接，大大提高了话题中相似博文的聚合力，聚类后的话题相关博文数量增多，从而降低了漏检率。除了Blog－IPO 方法对专题1 与专题4 的错检率略高于HITS－PageRank方法的错检率以外，Blog－IPO 方法对其余专题的错检率均明显低于HITS－PageRank 方法的错检率。这是因为Blog－IPO 方法对页面权重评判以及链接清洗，避免了话题漂移现象，有效地提高了话题聚类的准确率，从而使得Blog－IPO 方法整体上降低了错检率。

图3 Blog－IPO 方法和HITS－PageRank方法对不同话题专题的漏检率

图4 Blog－IPO 方法和HITS－PageRank方法对不同话题专题的错检率

Blog－IPO 方法与HITS－PageRank方法对不同话题专题的归一化开销如图5所示。

图5 Blog－IPO 方法和HITS－PageRank方法对不同话题专题的归一化开销

图5的结果表明，对于不同话题专题的归一化开销，Blog－IPO方法均低于HITS－PageRank方法，平均降低了27.81%。这是因为相较于错检率，漏检率在归一化开销中占据的比重较大，而本文的Blog－IPO 方法的漏检率明显低于HITS－PageRank方法的漏检率。

综合以上实验结果分析可知，本文给出的融合运用链接分析和萤火虫算法聚类博文的热点话题发现方法能够有效地挖掘出精度更高的博客热点话题。

4.4.2 热点话题挖掘结果

实验抽取了从2014年4月1日8时至4月30日18时新浪博客发表的4236个博文页面及62341条链接作为测试数据。HITS－PageRank方法与Blog－IPO 方法发现的热点话题结果分别见表2、表3。

表2 HITS－PageRank方法发现的热点话题结果

表3 Blog－IPO 方法发现的热点话题结果

对比表2、表3可知，Blog－IPO方法发现了15个热点话题，HITS－PageRank方法发现了10个热点话题，两种方法发现的话题均为2014年4月的热点信息，但是Blog－IPO 方法发现的话题数量更多。HITS－PageRank方法发现的话题数量少于本文提出的Blog－IPO 方法发现的话题数量，是因为HITS－PageRank方法存在话题漂移现象，将主题词相似但实质表述不同事件（例如表3中的以“火车”为关键词的话题9与11、以“住房”为关键词的话题6与13）的博文归为一类。此外，HITS－PageRank方法受到非相关链接的影响，未能识别出相对规模较小的表3中的热点话题12、14以及15。

5 结束语

本文给出的利用复杂网络簇结构高度主题相关的特性、基于三层博客话题模型、融合运用链接分析和萤火虫算法聚类博文的热点话题发现方法，克服已有的基于链接分析的舆情热点发现方法抵抗作弊链接能力较弱、存在主题漂移现象的问题，能够发现精度更高、数量更多的博客热点话题。本文的博客热点话题发现方法依据复杂网络簇结构进行建模，对于社区结构明显的论坛热点话题发现研究有参考价值。为适应大数据时代Web信息挖掘的需求，下一步工作将研究适合大规模博文页面热点话题发现的方法。

［1］ZHENG Kui，SHU Xueming，YUAN Hongyong.Hot spot information auto－detection method of network public opinion［J］.Computer Engineering，2010，36 （3）：4－6 （in Chinese）.［郑魁，疏学明，袁宏永.网络舆情热点信息自动发现方法 ［J］.计算机工程，2010，36 （3）：4－6.］

［2］WANG Tietao，WANG Guoying，CHEN Yue，et al.Study of network public opinion situation based on semantic pattern and word sentiment orientation ［J］.Computer Engineering and Design，2012，33 （1）：74－77 （in Chinese）. ［王铁套，王国营，陈越，等.基于语义模式与词汇情感倾向的舆情态势研究 ［J］.计算机工程与设计，2012，33 （1）：74－77.］

［3］LONG Zhiyi，CHENG Wei.Kind of hot topic detection algorithm based on clustering keywords ［J］.Computer Engineering and Design，2011，32 （6）：2214－2216 （in Chinese）.［龙志禕，程葳.基于词聚类的热点话题检测算法 ［J］.计算机工程与设计，2011，32 （6）：2214－2216.］

［4］ZHU Hengmin，SU Xinning，ZHANG Xiangbin.A topic tracking method of Internet public opinion based on link network diagram［J］.Journal of the China Society for Scientific and Technical Information，2012，30 （12）：1235－1241（in Chinese）.［朱恒民，苏新宁，张相斌.基于链接网络图的互联网舆情话题跟踪方法［J］.情报学报，2012，30 （12）：1235－1241.］

［5］LI Dongfang，YU Nenghai，YIN Huagang.Mining hot topics on Internet under Web 2.0 ［J］.Journal of Electronics ＆Information Technology，2010，32 （5）：1141－1145（in Chinese）.［李东方，俞能海，尹华罡.一种Web 2.0 环境下互联网热点挖掘算法［J］.电子与信息学报，2010，32 （5）：1141－1145.］

［6］XIE Fenghong，ZHANG Dawei，HUANG Dan，et al.Keywords extraction based on weighted complex network ［J］.Journal of Systems Science and Mathematical Sciences，2010（11）：1592－1596 （in Chinese）. ［谢凤宏，张大为，黄丹，等.基于加权复杂网络的文本关键词提取 ［J］.系统科学与数学，2010 （11）：1592－1596.］

［7］Nonaka H，Kubo D，Kimura T H，et al.Correlation analysis between financial data and patent score based on HITS algorithm ［C］//IEEE International Technology Management Conference，2014：1－4.

［8］Ji－Lin Z，Yong－jian R，Wei Z，et al.Webs ranking model based on pagerank algorithm ［C］//2nd International Conference on Information Science and Engineering.IEEE，2010：4811－4814.

［9］HUANG Min，HU Xuegang.Internet public opinion hot spot mining base on complex network theory ［J］.Computer Simulation，2011，28 （9）：114－117 （in Chinese）. ［黄敏，胡学钢.基于复杂网络方法的舆情热点挖掘 ［J］.计算机仿真，2011，28 （9）：114－117.］

［10］YANG Bo，LIU Dayou，LIU J，et al.complex network clustering algorithms ［J］.Journal of Software，2009，20（1）：54－66 （in Chinese）.［杨博，刘大有，Liu J，等.复杂网络聚类方法 ［J］.软件学报，2009，20 （1）：54－66.］

［11］HE Jianmin，ZHANG Yi.Research on identifying method for the hot topics based on class entropy distance measurement［J］.Information Science，2012，30 （8）：1147－1150 （in Chinese）.［何建民，张义.基于类熵距离测量的热点话题识别方法研究 ［J］.情报科学，2012，30 （8）：1147－1150.］

［12］Senthilnath J，Omkar S N，Mani V.Clustering using firefly algorithm：performance study ［J］.Swarm and Evolutionary Computation，2011，1 （3）：164－171.

［13］Banati H，Bajaj M.Performance analysis of firefly algorithm for data clustering ［J］.International Journal of Swarm Intelligence，2013 （1）：19－35.

［14］Yang X S.Nature－inspired metaheuristic algorithms ［M］.Bristal，UK：Luniver Press，2008：83－96.

［15］Amiri B，Hossain L，Crawford J W，et al.Community detection in complex networks：Multi－objective Enhanced Firefly Algorithm［J］.Knowledge－Based Systems，2013，46 （1）：1－11.

［16］ZHOU Erzhong.Blog hot topic detection and its analysis on public opinion ［D］.Beijing：Beijing University of Technology，2013 （in Chinese）.［周而重.博客舆情热点发现与分析［D］.北京：北京工业大学，2013.］

［17］Yang X S.Multiobjective firefly algorithm for continuous optimization［J］.Engineering with Computers，2013，29（2）：175－184.