- 1 -
一种基于分配因子的链接分析算法1
范鑫鑫
大连理工大学软件学院，大连 (116621)
摘 要：随着整个万维网的迅速发展，很难为用户提供相关而准确的查询信息。Web 结构挖
掘在数据挖掘领域起着很重要的角色，PageRank 和 HITS 是 Web 结构挖掘里面两种较为经典
的排序算法，这两种算法在分配权值的时候都是平均分配的，没有考虑各链接的重要性。后
来有些研究者通过入链、出链以及文本信息等对其进行了改进。本文提出了一种新的通过改
变马尔科夫概率分布矩阵(Markov Probability Distribution Matrix)排序算法，实验结果
表明该排序算法比标准的 PageRank 算法更加有效。
关键词：链接分析，Markov 模型，分配因子，概率矩阵
中图分类号：TP39
1. 引言
Web是一个由复杂超文本所组成的巨大的信息源，每天以超过700万页面的速度[1,2]增长,
如何从这样一个不断变化的信息源中提取有用的信息是一个难题。由于web信息的自组织和
半结构化，现有的搜索引擎技术远不能让客户满意[1]，经典的信息检索和数据库技术很难得
到有效的应用[2]。Web中含有丰富的超链接，超链接是联系整个信息源的纽带，因此链接分
析便成为提取有用信息的重要手段。
PageRank[3]和HITS[4]算法是web结构挖掘中两个较为经典的链接分析算法，它们和其它
大部分算法一样都是基于Markov模型的随机游动过程(Random Walk)，即跳向一个新网页或
者跟随链接到一个网页。这些算法能够很好的应用到web结构挖掘里面，但是这些算法在分
配权值的时候都平均的分配给所指向的网页，忽视了各链接权重不同问题。针对此问题，
Bharat和Henzinge[5]、Chakrabarti等 [6]提出了启发式方法来计算各链接权重值。Rafiei和
Mendelzon's [7]算法则偏重于那些含有一些特殊词的网页。Haveliwala [8]则采用了包含查询词
的网页子集方法。
随机游走受当前页面内容的影响，通常会跳转到与当前页面内容相关性很大页面，所以
链接权重应该是不一样的，鉴于此，本文提出了一种新的基于网页间相似度权值分配模式，
利用此分配模式我们提出了一种新的基于分配因子排序算法RADF(Ranking Algorithm Based
on Distributed Factor)。实验结果表明，该算法在获得相关性网页以及宏平均准确率方面比标
准的PageRank算法更加有效。
文章结构组织如下：第2部分介绍一下相关的链接分析算法，第3部分详细说明本文提出
的基于分配因子的链接分析算法RADF，第4部分通过实验将RADF算法与标准的PagesRank
算法进行比较与分析，第5部分总结全文。
2. 相关链接分析算法
Web的不断增大以及web用户特殊的性质使得整个网络结构更为复杂，检索出相关有用
的信息也变得更为困难。很多研究者也提出了不同的链接分析算法，例如：InDegree算法[9]，
该算法可以认为是所有基于流行度排序算法的前驱。Brin和Page通过扩展InDegree算法提出
1本课题得到国家自然科学基金的资助（项目编号：60503003）。
- 2 -
了PageRank[3]算法。Kleinberg考虑到两种权值传递模式于1998年提出了HITS[4]算法。
PageRank和HITS作为web结构挖掘里面较为经典的两种排序算法，很多研究者也对这两种算
法进行了改进。Mendelzon和Rafiei [10]利用随机跳转对HITS进行了改进，与SALSA算法相似。
Tomlin [11]提出了PageRank算法的一般化。文献[12-15] 对PageRank个性化向量处理方面也进行
了改进。
沿着不同的研究路线，有些研究者利用概率与统计技术来计算权值。Cohn和Chang[16]
提出了PHITS算法，该算法假设了一个概率模型，该模型中的链接由潜在的“因素”或“主
题”引起，他们利用期望最大值化算法(Expectation Maximization Algorithm)[17]来计算网页的
权威权值。他们的工作是基于Hofmann[18]提出的概率潜在语义分析(Probabilistic Latent
Semantic Analysis)框架。
3. 基于分布因子的排序算法(RADF)
传统的链接分析算法可能会带来不好的排序结果。首先，有些网页不是自描述性的，链
接的存在完全是为了导航目的；其次，排在后面的返回网页是没有价值的，即使是相关的网
页，因为大部分用户不会浏览第一页以后的返回结果[19-21]。
在分析超链接结构的时候，通常把web用户看做是一个“随机冲浪者(Random Surfer)”。
“冲浪者”会依不同的概率跳转到新的网页或者沿着链接到另外一个网页，所以链接权重是
不同的。本文认为“冲浪者”往往会依很大的概率浏览与当前网页相关的网页，因此各链接
权重可根据网页间的相似度得到。
相似度计算
为了计算网页间的相似度，我们引入了SimRank算法。该算法是由Stanford大学的Glen
Jeh和Jennifer Widom[22]提出的，可以计算任何领域里面任何两个对象之间的相似度，算法的
核心思想是：如果两个对象和其他相似的对象相似，那么这两个对象也是相似的。
我们把网页a和网页b的相似度定义为S(a, b)，并且S(a, b)的取值范围在0和1之间。如果
a=b，则定义S(a, b)=1，否则定义为：
( ) ( )
1 1
( , ) ( ( ), ( )) (1)
| ( ) || ( ) |
I a I b
i j
i j
cS a b S I a I b
I a I b = =
= ∑∑
参数c是介于0到1之间的常数，I(a)、I(b)分别是指向a、b的网页集合，即入链集合。从上面
的公式我们可以看出当I(a)=Φ或者I(b)=Φ时，S(a, b)=0。
文献[22]附录部分也证明了对于n2 SimRank算法S(*, *)总是存在并且是唯一的，所以我们
可以采用幂迭代方法求出任意两网页间的SimRank值。从公式1我们可以知道S(a,b)=S(b,a)，
两者是对称的，可以用该算法很好地计算任意两个网页之间的相似度。
公式1只是从入链角度考虑两者相似度。而对于整个超链接结构图，应该从入链和出链
两个方面来综合考虑。相比于入链公式可以很容易地得到出链公式：
( ) ( )
1 1
'( , ) ( ( ), ( )) (2)
| ( ) || ( ) |
O a O b
i j
i j
cS a b S O a O b
O a O b = =
= ∑∑
参数O(a)、O(b)分别表示由网页a，b所指向的网页集合。
入链和出链构成了整个超链接结构图，本文将两者SimRank值的平均作为最终的相似度
- 3 -
值，网页a、b的相似度计算公式为:
''( , ) ( ( , ) '( , )) / 2 (3)S a b S a b S a b= +
Markov 模型
研究者通常把 web 网页和超链接看成是一个有向图，如图 1 所示，图节点代表 web 网
页，有向边代表超链接。Markov 概率分布模型反映了“随机冲浪者”跳转概率，矩阵 P 是
图 1 的转移概率矩阵，P 中的元素 Pij表示从网页 i 跳转到网页 j 的概率。
从矩阵P中可以看出，任何节点都是以相等概率到达其所指向的节点，而没有考虑链接
权重不等问题。本文认为Web用户通常会以很大概率浏览和当前页面相关的网页，各出链网
页的分布概率是不同的。因此，我们提出了基于相似度的概率分布矩阵P’来代替上面的矩阵
P。从该矩阵我们可以看出，相似度越大，跳转到该网页的概率也越大。
S''(1, 2) 0 0 0 0
S''(1, 2)
S''(2, 1) 0
S''(2, 1) S''(2, 3)
P' =
+
S''(2, 3) 0 0
S''(2, 1) S''(2, 3)
S''(3, 1) S''(3, 4) 0 0
S''(3, 1) S''(3, 4) S''(3, 1) S''(3
+
+ + 0, 4)
0 0 0 0 0
0 0 S''(5, 3) S''(5, 4) 0
S''(5, 3) S''(5, 4) S''(5, 3) S''(5, 4)
⎛ ⎞⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟+ +⎜ ⎟⎝ ⎠
算法描述
通过改变Markov概率分布矩阵来调整权值分配模式，根据上述内容本文提出了新的基
于分配因子的链接分析算法RADF，其公式描述如下：
ij
i (j)
RADF(j)=(1-d)/n+d RADF(i) (4)
B
α
∈
∑
d为介于0到1之间的跳转因子，文献[23]提出当d=时实验结果比较好，所以本文在做实验
的时候仍然采用该值，n为网页节点总数，B(j)表示网页j的入链集合，这里面的αij我们称之
为分配因子，其表达式为：
( )
''( , ) /( ''( , )) (5)ij
k F i
S i j S i kα
∈
= ∑
F(i)表示网页i的出链集合，αij正好对应着矩阵P’里面的元素，同时也反应了随机冲浪者的心
图 1 由 5 个网页组成的有向图
0 1 0 0 0
1 /2 0 1 /2 0 0
P = 1 /2 0 0 1 /2 0
0 0 0 0 0
0 0 1 /2 1 /2 0
⎛ ⎞⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎝ ⎠
- 4 -
理，因为对于一个web用户来讲，往往会把那些与当前页面相关的网页作为下次跳转的对象。
矩阵计算
该部分将会介绍概率转移矩阵的计算方法以及 RADF 算法的一些特点，我们采用幂迭
代方法来求矩阵特征向量值，采用该方法有几个好的原因[23]。
用超链接建立 Markov 转移概率矩阵存在一个明显的问题，那就是某些行的元素可能全
部都是 0，如矩阵 P 或 P’中的第四行，这种情况发生在那些没有出链节点身上，我们称这些
节点为沉积节点。如果我们把 web 用户看作是一个随机冲浪者，那么这样的矩阵显然是不
合理的，因为这样的矩阵破坏了冲浪者的随机选择性。因此，必须用别的矩阵来代替 P’，
我们可以把所有沉积节点的权重平均分配给每个节点，即将这些为 0T行全部替换为 eT/n (n
是节点总数，e 是值为 1 的列向量), 这样修正后的概率转移矩阵 P’’为：
S''(1, 2) 0 0 0 0
S''(1, 2)
S''(2, 1) 0
S''(2, 1) S''(2, 3)
P'' =
+
S''(2, 3) 0 0
S''(2, 1) S''(2, 3)
S''(3, 1) S''(3, 4) 0 0
S''(3, 1) S''(3, 4) S''(3, 1) S''(
+
+ + 03, 4)
1/5 1/5 1/5 1/5 1/5
0 0 S''(5, 3) S''(5, 4) 0
S''(5, 3) S''(5, 4) S''(5, 3) S''(5, 4)
⎛ ⎞⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟+ +⎜ ⎟⎝ ⎠
然而，这样修正还是不能保证 Markov 稳定特征向量值的存在[23,24]，必须对矩阵 P’’做进
一步的调整来保证 P’’是不可约分的，因此修正后的随机的不可约分的矩阵 P’’’为：
''' '' (1 ) / (6)TP dP d ee n= + −
随机矩阵P’’和随机动摇矩阵E (E=1/n eeT)形成的凸组合保证了矩阵P’’’是随机的并且是不可
约分的，尽管转移概率在某些情况下可能是很小的但总是非0的。
每个状态最终都是可到达的从其他任一状态，称这样的Markov链是不可约分的。这也
就是说对于超链接图上所有的节点i、j存在一条从i到j的路径。根据Perron–Frobenius理论[25]，
不可约分这一属性能够保证Markov链拥有一个唯一的稳定的分布向量π(k+1)=π(k) P’’’ (π是
特征向量, k 是迭代次数)。
根据上述内容，下面我们将给出算法RADF框架：
输入：给出概率转移矩阵P’’’，传输向量v，控制参数ε。
输出：矩阵P’’’的特征向量π。
begin
initialize π(0) = v, k = 0
repeat
π(k+1) =π(k) P’’’
δ= ||π(k+1)- π(k)||
k = k + 1
untilδ<ε
- 5 -
end
return π(k)
4. 实验及结果分析
为了检验 RAD 算法的质量，我们通过实验与标准的 PageRank 算法进行比较。本文选
用了几组别的链接分析算法常用的测试数据集，表 1 列出了本次实验所用的数据集。
表 1 试验所采用的数据集及其节点数、超链接数
数据集 节点数 超链接数 数据集 节点数 超链接数
computational geometry 2292 8189 classical guitar 3150 12044
gun control 2955 11738 abortion 3340 22287
vintage cars 3460 12796 death penalty 4298 21956
本文采用了两种评测方法对 RADF 算法和标准的 PageRank 算法进行了比较。对于 web
用户来讲，可能关心更多的是返回结果中前一页或前三页有多少是相关的权威的网页，而不
是召回率的大小。这种在固定位置检查正确率的评测方法称为“precision at k”，本文取 k=10。
表 2 列出了实验结果，根据实验数据我们绘出了图 2。
表 2 前 10 个返回结果中相关网页的数目
数据集 PageRank RADF 数据集 PageRank RADF
computational geometry 5 8 classical guitar 7 7
gun control 4 6 abortion 9 10
vintage cars 2 6 death penalty 8 10
图2 前十个返回结果中网页的相关正确率及其平均值
(a) (b)
- 6 -
从图 2(a)可以很明显地看出算法 RADF 比标准 PageRank 更加有效，图 2(b)也显示 RADF
算法比 PageRank 平均提高了 20%。
本文采用 MAP(Mean Average Precision)作为第二种评测方法。AP(Average Precision)是对
召回点上的正确率进行平均，MAP 便是对所有查询的 AP 进行宏平均。其计算公式为：
| |
1 1
1 1( ) Pr ( ) (7)
| |
jmQ
jk
j k
MAP Q ecision R
Q m= =
= ∑ ∑
Q为查询主题，m为前多少个相关网页数，Precision(Rjk)为第k个相关网页在第j个查询主题上
的召回准确率。表3给出了详细了实验数据，根据这些数据我们绘出了图3。
表 3 两算法的 AP 实验数据
数据集 PageRank RADF 数据集 PageRank RADF
computational geometry classical guitar
gun control abortion
vintage cars death penalty
图3 两算法的AP以及MAP
从图3中可以明显看出，RADF算法在平均准确率方面比标准的PageRank算法更加有效，
MAP也比标准的PageRank算法提高了%。通过对比图2和图3可以看出：虽然查询词
“classical guitar”的相关准确率相等，但是AP是不等的，RADF算法的AP比PageRank要高。
(a) (b)
- 7 -
5. 总结
Web结构挖掘在信息检索领域起着很重要的角色，HITS和PageRank是两种比较经典而
且常用的链接分析算法。然而，它们在分配权值的过程中是按照等值分配的而没有考虑各个
链接的重要性程度。本文基于网页间的相似度提出了一种新的权值分配模式，按照此模式改
变了Markov概率分布矩阵，提出了一种新的基于分配因子的链接分析算法。实验结果表明
本文提出的RADF算法比标准的PageRank算法更加有效。本文用SimRank算法来计算网页间
的相似度，但是该算法的复杂度比较高，所以今后的研究方向将侧重于相似度方面。
参考文献
[1] MENG Tao, YAN Hong-fei, LI Xiao-ming. An Evaluation Model on Information Coverage of Search
Engines [J]. Chinese Journal of Electronics, 2003,31(8):1168-1172
[2] Wang XY, Zhou AY. Linkage analysis for the World Wide Web and its application: A survey [J]. Journal
of Software, 2003,14(10):1768~1780
[3] Brin, S. and Page, L. The anatomy of a large-scale hypertextual Web search engine. In Proceedings of the 7th
International World Wide Web Conference. Brisbane, Australia, 1998
[4] Kleinberg, J. Authoritative sources in a hyperlinked environment. In Proceedings of the Ninth Annual
ACM-SIAM Symposium on Discrete Algorithms,1998:668–677.
[5] K. Bharat and M. R. Henzinger. Improved algorithms for topic distillation in a hyperlinked environment.
Proceedings of the Twenty-First Annual International ACM SIGIR Conference on Research and Development in
Information Retrieval,1998
[6] Chakrabarti, S., Dom, B., Gibson, D., Kleinberg, et al. Automatic resource compilation by analysing hyperlink
structure and associated text. In Proceedings of the 7th International World Wide Web Conference, 1998
[7] Rafiei, D. and Mendelzon, A.. What is this page known for? Computing Web page reputations. In
Proceedings of the 9th International World Wide Web Conference. Amsterdam, Netherlands, 2000
[8] T. Haveliwala. Efficient computation of PageRank. Technical report, Stanford University, Stanford, CA, 1999
[9] Marchiori, M.. The quest for correct information on Web: Hyper search engines. In Proceedings of the 6th
International World Wide Web Conference, 1997
[10] . Mendelzon and D. Rafiei. What do the neighbours think? Computing Web page reputations. IEEE Data
Engineering. Bulletin, 2000,23(3):9–16
[11] Tomlin, J. A.. A new paradigm for ranking pages on the World Wide Web. In Proceedings of the 12th
International World Wide Wed Conference (WWW2003). Budapest, Hungary, 2003
[12] Page, L., Brin, S., Motwani, R., et al. The PageRank citation ranking: Bringing order to the web. Tech. rep.
Stanford Digital Library Technologies Project, 1998
[13] Haveliwala, T. H. Topic sensitive Page Rank. In Proceedings of the 11th International Word Wide Web
Conference (WWW 2002). Hawai, 2002
[14] Jen, G. and Widom, J.. Scaling personalized Web search. In Proceedings of the 12th International World
Wide Wed Conference(WWW2003). Budapest, Hungary, 2003
[15] Richardson, M. and Domingos, P.. The intelligent surfer: Probabilistic combination of link and content
information in PageRank. In Advances in Neural Information Processing Systems (NIPS) 14, 2002
[16] Cohn, D. and Chang, H.. Learning to probabilistically identify authoritative documents. In Proceedings of the
17th International Conference on Machine Learning. Stanford University, 2000:167–174.
[17] Dempster, A., Laird, N. and Rubin, D. (1977). Maximum-likelihood from incomplete data via the EM
algorithm. J. Roy. Statist. Soc. Ser. B 39 1-38.
[18] Hofmann, T.. Probabilistic latent semantic analysis. In Proceedings of Uncertainty in Artificial Intelligence,
UAI’99. Stockholm, Sweden, 1999
[19] Broder, A.. Web searching technology overview. In Advanced School and Workshop on Models and
Algorithms for the World Wide Web. Udine, Italy, 2002
[20] C. Silverstein, M. Henzinger, H. Marais, and. M. Moricz. Analysis of a very large altavista query log.
Technical Report 1998-014, Digital SRC, 1998.
[21] Jansen, B. J., Spink, A., Bateman, J., and Saracevic, T.. Real Life Information Retrieval: A Study of User
Queries on the Web. 1998, ACM SIGIR Forum 32, 5–17
[22] Glen Jeh, Jennifer Widom, SimRank: A Measure of Structural-Context Similarity, SIGKDD, 2002.
[23] Langville A N, Meyer C D. Deeper Inside PageRank. Internet Mathematics, 2004, 1(3): 355-0400
[24] Amy N. Langville and Carl D. Meyer, A survey of eigenvector methods of Web information retrieval, SIAM
Review 47 (2005) (1), 135–161.
[25] C. D. Meyer, Matrix Analysis and Applied Linear Algebra, SIAM, Philadelphia, 2000.
- 8 -
A link Analysis Algorithm Based on Distributed Factor
Fan Xinxin
School of Software, Dalian University of Technology, Dalian, Liaoning (116621)
Abstract
With the rapid growth of the web, it will become more and more difficult to provide relevant and
authoritative information to the users to cater to their needs. The web structure mining plays an
important role in data mining. There are two classic ranking algorithms HITS and PageRank commonly
used in web structure mining. These two algorithms treat all links equally ignoring the importance of
different links while assigning rank scores. Several algorithms have been developed to improve the
performance taking into account the importance of the in-links, out-links and the text content of the
pages et al. This paper provides a new ranking algorithm via changing the Markov probability matrix
based on distributed factor. Our experiment result shows that this algorithm performs better than the
standard PageRank.
Keywords：Link Analysis, Markov Model, Distributed Factor, Probability Matrix
作者简介：范鑫鑫，男，1984 年生，硕士研究生，主要研究方向为数据挖掘、web 信息检
索等。
