PageRank算法和HITS算法

楼楼刚才想了一个特别骚情的标题，叫PageRank算法和HITS算法的“前世今生”，特别像之前写头条号的套路，然后就想起来去年6月份自己有在经营一个技术型的头条号，后来因为做不到一天一篇的更新频率被我弃坑了，现在手机号换了，登陆不了，去主页看了看之前写的文章，竟然被一直这么努力的自己感动到了。：）

PageRank算法和HITS算法都属于比较著名的链接链接分析方法，作为经典方法，由此也衍生出一些列相关方法，从下图就可以看出这两种方法的前世今生。

随机游走模型：

随机游走模型就和它字面意思所表述的那样，用户的浏览在网页之间进行跳转，假设网页包含k个出链， 用户从当前页面跳转到这k个页面的概率是相等的。用户不断重复上述过程，在相互有链接指向的页面之间跳转，如果对于某个页面所包含的所有链接，用户都没有兴趣继续浏览， 则可能会在浏览器中输入另一个网址，直到到达该网页，这种行为被称为“远程跳转” 。而随机游走模型就是一个对直接跳转和远程跳转两种用户浏览行为进行抽象的概念模型。

实例

子集传播模型

子集传播模型会把互联网网页按照一定规则划分， 分成两个甚至是多个子集合。其中， 某个子集合具有特殊性质， 很多算法会从这些具有特殊性质的子集合出发，给予子集合内网页初始值，之后根据这个特殊子集合内网页和其他网页的链接关系，按照一定方式将权值传递到其他网页。

PageRank算法

PageRank算法是Google创始人在1997年构建的早期搜索系统的原型时所提出的链接分析算法。对于某个互联网网页A来讲，PageRank算法是基于以下两个假设的。

数量假设：在Web图模型中，如果一个页面节点接收到的其他网页指向的入链数量越多，那么这个页面越重要。

质量假设： 指向页面A的入链质量不同，质量高的页面会通过链接向其他页面传递更多的权重。所以越是质量高的页面指向页面A， 则页面A越重要。

初始阶段：

按照网页链接关系构建起web图， 每个页面被设置成相同的PageRank值。

经过若干轮计算：

每个页面将当前的PageRank值平均分配到被页面包含的出链上， 每个链接获得相应的权值。

而每个页面将所有指向本页面的入链所传入权值求和， 即可得到新的PageRank得分，即完成一轮PageRank计算。

从图6-9中可以看出PageRank算法的迭代过程。

有一点值得注意，当相互链接的网页形成一个环形结构，也就是说网页的PageRank值不能传播出去，只能通过其他指向这个环形结构的网页吸收PageRank值，随着一轮一轮的迭代，会导致环形结构的网页的PageRank值会越来越高，高的不合情理。这种情况可以称之为链接陷阱。

而远程链接就可以解决链接陷阱所带来的问题。

HITS算法

HIST算法是子集传播算法的代表算法。在HIST算法中，分为Hub页面和Authority页面，Authority页面是指与某个领域或者某个话题相关的高质量页面，Hub页面则是包含很多指向高质量Authority页面链接的网页，比如，hao123首页就是一个典型的高质量Hub页。

Hub页和Authority页之间是相互增强的关系，HITS算法基于的是下面的两个基本假设：

基本假设1：一个好的Authority页面会被很多Hub页面指向。

基本假设2 ： 一个好的Hub页面会指向很多好的Authority页面。

HITS算法与PageRank算法最大的区别是，PageRank算法是与查询无关的全局算法，而HITS算法与用户输入的查询词是密切相关的，HITS算法接收到用户查询之后，将查询词提交给搜索引擎，返回的搜索结果中， 提取排名靠前的网页，得到一组与用户查询高度相关的初始网页集合，这个集合被称为根集。 HIST算法对根集中的网页进行扩充，扩充的原则：凡是与根集内的网页有直接链接指向关系的网页都被扩充进来。

扩充进来的页面我们并不知道哪些是Authority页或者是好的Hub页，利用HIST算法，初始值可以设置为相同的，设置为1，利用相互增强关系迭代更新每个页面的值，直到稳定 。

上图则是Hub与Authority的相互增强关系图。