基于链接分析的重要Blog信息源发现

【摘要】信息量的膨胀和信息源的无限增加为用户找到自己所关心的特定信息带来了不便。Blog领域信息与传统门户网站的区别在于，Blog作者关注的主题更加明确，并且通常代表一种相对单一的观点...

摘 要：本文提出了一种基于链接分析的对Blog信息源进行量化评估的方法，在此基础之上发现重要blog信息源，既体现了Blog信息的特点，又在一定程度上减小了作弊链接对链接分析结果的影响，能为用户阅读信息提供方便，并可望为Blog信息检索提供一种斯的思路。为了证明该评估方法的有效性，本文还提出了Blog信息源重要性的评价指标，对比了重要Blog信息源量化评估方法和评价指标的评分结果，通过相关性分析，表明此方法和评价指标存在高度的一致性。

关键词：计算机应用；中文信息处理；重要Blog信息源；链接分析；评价指标；相关性分析

中图分类号：TP391　文献标识码：A

1 引　言

随着Blog为代表的网络应用的流行，web2.0时代的到来，互联网用户可以更加随意的信息和进行交流，每个用户都成为一个潜在的信息源，而不是像以前只能单方面的从有限的信息源那里接受信息，因此互联网上的信息源和信息量变得极大丰富。

信息量的膨胀和信息源的无限增加为用户找到自己所关心的特定信息带来了不便。Blog领域信息与传统门户网站的区别在于，Blog作者关注的主题更加明确，并且通常代表一种相对单一的观点。发现Blog作者将方便用户阅读和查询信息，国外研究者已经开展了相关研究。一部分研究采用了传统的链接分析方法，它们之间的区别主要在于根据不同的理解和需要对有向图中的边进行不同定义，使用不同种类的链接关系，并赋以不同的权值。BelleL.Tseng等提出了一种基于查询和Blog条目对Blog排序的方法，在系统模型中，一个Blog由多个Blog条目构成，系统根据用户的查询通过关键词匹配找到相关的Blog条目，用类似PageRank的算法对Blog条目打分，将一个Blog所包含的Blog条目的分值加权平均，得到这个Blog的排序分值。iRank算法通过推断Blog间所有可能的信息传播途径，得到潜在信息流图，并在此基础上应用PageRank算法计算Blog的重要性。这种算法赋予具有较高感染力的Blog以高的分值，体现了Blog作为信息传播者的有效性。以上研究主要通过定义不同的链接关系形成不同的有向图，然后应用传统的链接分析方法进行重要性分析，还有研究采用了不同于传统方法的链接分析算法，EigenRumor算法是其中具有代表性的方法。EigenRumor算法对传统链接分析方法的算法模型进行了改进，综合发表Blog文章的作者的Authority值以及对Blog文章进行评论的其他作者的Hub值衡量该Blog文章的重要性。该算法允许对一个好的Blog作者发表的但没有其他Blog链接指向的文章评一个较高的分数，这是基于对Blog作者以前工作的认可。除了常用的链接分析方法外，Shinsuke Nakajima等根据Blog作者信息的被引用次数以及对社区文章数量和内容的影响，采用基于链接、流行度及主题变化的指标判断其重要性。

已有的关于Blog重要性分析的研究主要面临以下问题：存在一定局限难以适用于整个Blog领域；难以避免作弊链接的干扰；缺乏统一的评价指标使得不同方法间难以进行比较。基于Blog领域的特点，本文将一个Blog作者的所有信息的集合定义为一个信息源，提出了一种基于链接分析的对Blog信息源进行量化评估的方法。和以前的工作相比，本文的主要创新在于：(1)将页面间的链接关系转化为信息源间的链接关系，并拓展PageRank算法用于信息源的重要性评估；(2)本文提出的方法有效地减小了作弊链接对重要性评估结果的影响；(3)基于Blog特点提出了Blog信息源重要性的评价指标；(4)引进了相关分析等统计手段证明了方法的有效性。

本文第2节详细介绍了Blog链接关系抽取和信息源量化评估等方法，并提出了信息源重要性的评价指标；第3节通过实验验证了本文提出的方法的有效性；第4节总结全文并概述未来的研究工作。

2 Blog重要信息源的发现

2．1 Blog链接关系抽取

分析Blog的URL和网页结构等特点，设计抽取模式，逐条处理Blog信息，提取Blog作者即信息源信息，并从网页文本中逐个提取链接信息，在此基础上将网页间的链接关系转化为Blog信息源间的链接关系。Blog领域的链接可分为Blog信息源和非Blog网页间，相同Blog信息源的不同Blog网页间以及不同、Blog信息源之间的链接三类。本研究的范围限定在Blog领域，而相同Blog信息源的不同Blog网页间的链接对信息源重要性没有贡献，因此实验中只提取不同Blog信息源间的链接，在此基础上运用链接分析的方法对Blog信息源的重要性进行量化评估。详细的链接关系提取算法如算法1所示。

为了便于比较分析，实验中所采用的Blog信息和信息源限定在同一托管网站，因此只考虑托管网站内部信息源之间的链接关系，舍弃剩余链接信息。对于属于网站内部的链接，提取链接指向的信息源，累积链接数得到信息源间的链接关系。算法1是针对本研究中的实验提出的，即Blog信息和信息源都限定在一个Blog托管网站内部，但它同样具有普遍意义，在处理Blog信息的范围发生变化时，只需改变对所提取链接进行处理的限定条件，即在算法第6行根据需要作相应的改动即可。

2．2 Blog信息源的量化评估

网页重要性评估的思想认为每个网页被量化的价值通过一种递归的方式来定义，由所有链接指向它的网页的价值程度所决定。类似的Blog信息源的重要性也可由所有链接指向它的Blog信息源的价值程度所决定。

PageRank算法和HITS算法是两种最具代表性的链接分析算法，具有代表性的相关系统包括基于PageRank算法的Google搜索引擎，以及IBM Almaden实验室开发的基于HITS算法的ARC(Automatic Resource Compilation)系统和CLEVER系统。在Blog领域，同主题权威信息源之间有着丰富的链接关系，而且鲜有类似导航网站的中心性信息源，同时考虑到HITS算法主题漂移的缺点，因此本系统对PageRank算法进行拓展用于对信息源的量化评估。在传统的PageRank算法中，只要某一页面中有链接指向其他页面，则无论链接数的多少，均认为该页面对其他页面的推荐程度相同；在拓展后的算法中，舍弃掉信息源内部网页之间的链接关系，准确记录每个信息源指向其他信息源的链接数目并进行归一化处理作为该信息源对其他信息源的推荐程度。这种拓展的根据在于量化评估的单位是信息源，若某一信息源中有链接指向其他信息源，可能有该信息源的一个或多个页面指向其他信息源的一个或多个页面，因此认为信息 源间的链接数与推荐程度正相关。

在算法模型中，设信息源R1，R2…，Rn有链接指向信息源A，设y(A)，V(R1)，V(R2)，…，V(Rn)分别表示信息源A，R1，R2，…，Rn的重要性值(Rankval)，C(R1)，C(R2)，…，C(Rn)分别表示信息源R1，R2，…，Rn中所有页面的链接出度，C(R1A)，C(R2A)，…，C(RnA)分别表示信息源R1，R2，…，Rn指向信息源A的链接数，d为用户不随链接访问其他信息源的概率，取值在0到1之间(本系统中取值为0.15)，则有：

将所有信息源初始的重要性值设为1，按照上式进行迭代计算，直到所有重要性值稳定(本系统中设所有重要性值的变化小于1e～10为稳定)后停止计算。设定最大的重要性值为10，并按照同样比例对所有信息源的重要性值放大或缩小，进行标准化处理。

2．3 对作弊链接影响的遏制

作弊链接是网站的拥有者或维护者人为加入的无意义的链接，其目的在于提高自身在搜索结果中的排名，以吸引更多互联网用户的关注和点击。所有针对互联网领域的链接分析算法都会受到作弊链接的干扰，在算法中，未被排除的作弊链接将和正常链接一样被作为网页间相互推荐的标志，从而对链接分析和排序结果造成不良影响。本文提出的基于信息源的重要性评估方法除了很好的体现了Blog信息的特点外，还在一定程度上减小了作弊链接对重要性评估结果的影响，主要体现在以下三个方面：

(1)在算法模型中，不考虑出链的影响，因此类似目录克隆(Directory Cloning)等利用出链的作弊方法不会对重要性值的计算构成影响。

(2)算法中舍弃了信息源内部网页之间的链接关系，从而避免了通过人为添加大量指向Blog信息源内部页面的链接以提高排名的可能。

(3)在Blog领域，通常有作弊者在评论信息中加入作弊链接，算法中准确记录每个信息源指向其他信息源的链接数目并进行归一化处理，重要信息源的链接出度通常达到数千甚至更多，因此一条乃至数十条人为加入的作弊链接对结果的影响很小。

2．4 评价指标

到目前为止，关于Blog信息源重要性评估本身还没有得到普遍认可的评价标准。理想的评价指标应该能够客观反映其他信息源的推荐程度以及读者的关注程度，且能够方便准确的获取便于大规模的评价。基于此，本文选取信息源的链接入度、评论数、Trackback数作为评价指标，评价指标的相关描述和定义如下：

(1)链接入度：其他Blog信息源指向目标Blog信息源的链接总数。

(2)评论数：Blog信息源的读者在该信息源的条目上发表评论的总数。

(3)Trackback数：Trackback是Blog信息源间相互通告的一种工具，如果某个Blog作者A的信息与另一个Blog作者B的信息相关，则A可发送一个Trackback到B，申明这种关联。Traekback数就是Blog信息源获得的Trackback的总数。

在Blog领域，一个链接入度较大，评论数和Trackback数较多的Blog信息源通常被较多的Blog信息源所推荐，被较多的Blog读者所关注，在Blog社区中具有较大的影响力。

对包括链接入度、评论数和Trackback数在内的评价指标进行标准化处理，即设定各项指标最大的值为10，并按照相应比例对各项指标进行处理得标准化值。将各项指标加权后得到信息源重要性综合参考值Referval，即：

Referval＝a×Indeg ree＋β×Comment

＋γ×Trackback (2)

其中α＋β＋γ＝1(α＞0，β＞0，γ＞0)，本研究中设信息源的链接入度、评论数、Trackback数对信息源重要性的影响相同，取。α＝β＝γ＝1/3。

3 实验结果及分析

本研究中采用的实验数据包括39 633个Blog网页，分别属于1075个信息源，全部1075个信息源共含有相互指向的链接400990个。本节将通过以上方法抽取链接关系并对信息源进行量化评估，计算出相应的重要性值，通过实验验证量化评估方法的有效性，并分析该方法对作弊链接影响的遏制。

3．1 相关性分析

本研究通过引入相关性分析验证信息源的重要性值与综合参考值之间的一致性。统计相关性是评估两个变量的观测数据之间是否存在相关关系的一种手段，两个变量X和Y之间的相关系数r(X，Y)定义为：

其中：COV(X，Y)是协方差；SX。是变量X的标准差；SY、是变量Y的标准差；n是样本容量；Xi(Yi)是变量X(Y)的第i个分量；X(Y)为变量X(Y)的样本均值。

3．2 量化评估方法验证

采用第2节中的方法计算Blog信息源的重要性值，并获取对应的各种评价指标，计算重要性值和各种评价指标间的相关系数，如图1所示。图1可以直观地显示出重要性值与评价指标之间是高度一致的。正相关的描述，相关系数大于0.5时表示强相关，在0.3到0.5之间表示中度相关。图1中除了Trankback数和链接入度间的相关系数为0.489之外，所有的相关系数都大于0.5，链接入度与本文提出的评估方法及其他评价指标的相关系数相对较小，它与其他评价方法的平均相似度为0.633。本文提出的评估方法与链接人度评分结果的相关系数为0.649，与其他评价指标的相关系数都在0.74以上，表明本文提出的量化评估方法和评价指标强烈正相关。

3．3 遏制作弊链接的分析

为了验证算法对作弊链接的遏制，模拟作弊链接的情况，假设重要性值最小的m个Blog信息源各有1条作弊链接使得重要性值最大的m个Blog信息源指向自己。分别依据模拟作弊行为前后的链接关系，计算各Blog信息源的重要性值，并对两组重要性值进行相关性分析，实验结果如表l所示。

表1中Adp_Correlation项显示了用改进后的PageRank算法在模拟作弊链接前后计算得到的重要性值间的相关系数。为了进行比较，采用传统的PageRank算法计算作弊链接前后的重要性值，并计算相关系数，结果如表1中Con_Correlation项所示。比较发现，Adp_Correlation的值明显大于Con_Correlation的值，当作弊链接达到250000条时，Adp Correlation的值依然大于0.9，表明改进后的方法受作弊链接的影响明显减小，即该方法能够有效的遏制作弊链接。

4 结论及未来工作

本文提出了基于链接分析的Blog信息源重要性量化评估的方法，在此基础上发现重要的Blog信息源，并根据Blog信息源的特点提出了Blog信息源重要性的评价指标。引进了相关分析等统计手段，通过实验证明了信息源重要性量化评估方法的有效性，并通过模拟作弊链接验证了本文提出的方法能够有效地减小作弊链接对重要性评估结果的影响。

在未来的工作中，拟将本文中提出的量化评估方法运用到整个Blog领域，构造一个基于该方法的Blog搜索引擎，结合Blog信息的自身特点，为用户的查询提供一系列信息源及对应的相关信息，同时也根据用户的反馈对该方法进行评价。