PageRank和HITS算法及应用

链接分析方法的思想起源于文献引文索引机制，即论文被引用的次数越多、引用它的论文质量越高，则这篇论文就被认为越权威。将这个思路移植到网络空间，就是某个网页被链接的次数越多、链接其的网页质量越高，该网页就被认为质量更高、人气更旺，更有可能是用户所需的。

Web是一个超文本集，且网页间的链接是有方向的。根据数据结构中对图的定义，通常将Web上错综复杂的网页作为有向图G来处理，即G=（V，E）。其中，V表示网页集合，E表示网页之间的链接集合。网页被抽象为图G中的顶点，网页之间的链接被抽象为图G中的有向边。链接分析以链接作为主要输入来研究Web的性质，尤其是其隐含的宏观性质。基于链接分析的文档排序方法主要基于两个重要假设：一个从网页A到网页B的超链接表示网页A的作者对网页B的一种推荐；如果网页A和网页B是通过超链接连接的，那么就认为它们有可能是关于同一个主题的。这两个假设在各种基于链接分析的算法中均以某种方式体现。最著名的文档排序算法是PageRank算法（由Page等人提出）和HITS算法（由Kleinberg等人提出），且PageRank算法在Google搜索引擎中的应用获得了巨大的商业成功。(www.xing528.com)

PageRank算法和HITS算法均为基于链接分析的排序算法，但两者的应用领域有所不同。PageRank算法通常应用于搜索引擎服务端，可直接用于标题查询，并获得较好的结果。HITS算法一般用于全文本搜索引擎的客户端，可用于自动编撰Web分类目录；通过找到指向某网页的集中网页（Hub网页）并以此为根集，HITS算法可以查找该网页的相关网页；此外，HITS算法还可用于元搜索引擎的网页排序。