HiTs_PageRank

1.算法来源

1999年，Jon Kleinberg 提出了HITS算法。

HITS(Hyperlink-Induced Topic Search)。在HITS算法中，每个页面被赋予两个属性：hub属性和authority属性。同时，网页被分为两种：hub页面和authority页面。hub页面指那些包含了很多指向authority页面的链接的网页，而authority页面则指那些包含有实质性内容的网页。

2.算法原理

HITS算法基于以下两个假设

1	一个高质量的authority页面会被很多高质量的hub页面所指向。一个高质量的hub页面会指向很多高质量的authority页面。

而质量的评判基于以下评判

1	页面hub值等于所有它指向的页面的authority值之和。页面authority值等于所有指向它的页面的hub值之和。

与PageRank算法不同，HITS算法是在用户搜索后运行的，其与用户的查询密切相关，所以HITS算法处理的集合会比较小。

首先，我们需要确定这个集合。整个互联网中的网页之间的关系可以抽象为一个有向图G=(V,E)，当有一个搜索请求产生时（不妨设关键字为σ）,我们可以取所有包含关键字σ的网页组成的集合Q_σ为初始集合，并在这个集合上运行我们的HITS算法。然而，这个集合却有着明显的缺陷：这个集合可能非常之大，大到包含了数百万个网页，而这显然不是理想的集合大小。于是，我们进而想找到一个更小的集合S_σ，满足以下条件：

S_σ确实足够小。

S_σ包含很多与查询相关的页面。

S_σ包含很多高质量的authority页面。

一般将查询q提交给基于关键字查询的检索系统，从返回结果页面的集合总取前n个网页(如n=200)，作为根集合R_σ.然后我们可以基于如下过程来扩充这个集合。

Subgraph(σ, ψ, t, d)  
　　σ: a query string.  
　　ψ: a text-based search engine.  
　　t, d: natural numbers.  
  
　　Let Rσ denote the top t results of ψ on σ.  
　　Set Sσ := Rσ  
  
　　For each page p ∈ Rσ  
　　　　Let Γ+(p) denote the set of all pages p points to.  
　　　　Let Γ−(p) denote the set of all pages pointing to p.  
　　　　Add all pages in Γ+(p) to Sσ.  
　　　　If |Γ−(p)|≤d, then  
　　　　　　Add all pages in Γ−(p) to Sσ.  
　　　　Else  
　　　　　　Add an arbitrary set of d pages from Γ−(p) to Sσ.  
　　End  
　　Return Sσ

一开始我们令S_σ = R_σ。然后通过上面的方法，我们将所有被R_σ中网页所指向的网页加入到S_σ中，再把一定数量的指向R_σ集合中网页的那些网页（每个R_σ中网页最多能添加d个指向它的网页）加入到S_σ中。为了保证S_σ集合的合适的大小，d不能太大，一般设置为50左右。(d太大的话容易导致扩展后集合太大)通常情况下，扩展之后集合的大小为1000~5000个网页，满足上面的三个条件。

而计算hub值，authority值的过程如下：

我们可以设置一个阈值来停止迭代。

3.算法缺点

3.1计算效率低

这里说的“效率低”是针对其实时计算的特点而提出的。HITS算法是在用户提出搜索请求之后才开始运行的，然而计算出结果又需要多次迭代计算，所以就这点上来说HITS算法效率仍然较低。

3.2主题漂移

在算法原理部分我们介绍了HITS算法是如何生成初始集合Gσ。从根集合Rσ我们通过链接添加网页的方法进行扩展，但这也很可能添加进与搜索主题无关的网页。若是这部分网页中又恰恰有着一些高质量的authority页面，则很有可能返回给用户，降低用户的搜索体验。

3.3作弊网页

试想我们弄一个页面指向很多高质量的authority页面，那么这个页面就成为了一个高质量的hub页面。然后再弄个链接指向自己的网页，按照HITS算法，将大大提升自己的搓网页的authority值。

3.4稳定性差

对于一个网页集合，若是删除其中的某条链接，就有可能造成一些网页的hub值和authority值发生巨大变化。

二.PageRank

1.算法来源

谷歌的两位创始人，当时还是美国斯坦福大学 (Stanford University) 研究生的佩奇 (Larry Page) 和布林 (Sergey Brin) 开始了对网页排序问题的研究。他们的借鉴了学术界评判学术论文重要性的通用方法，那就是看论文的引用次数。由此想到网页的重要性也可以根据这种方法来评价。于是PageRank的核心思想就诞生了，非常简单：

如果一个网页被很多其他网页链接到的话说明这个网页比较重要，也就是PageRank值会相对较高 如果一个PageRank值很高的网页链接到一个其他的网页，那么被链接到的网页的PageRank值会相应地因此而提高

2.算法原理

PageRank算法先给每个网页一个PR值，其物理意义为一个网页被访问概率，所以一般为1�N1;

假设一个由4个网页组成的群体：A，B，C和D。如果所有页面都只链接至A，那么A的PR（PageRank）值将是B，C及D的Pagerank总和。

继续上面的假设，A除了链接到D以外，A还链接了C和B，那么当用户访问 A 的时候，就有跳转到 B、C 或者 D 的可能性，跳转概率均为 1/3。在计算D的PR值时，A的PR值只能投出1331 的票，B的PR值只能投出1221的票，而C只链接到D，所以能投出全票，所以D的PR值总和应为：

如果一个网页没有出链，即其对其他网页没有PR值的贡献，我们不喜欢这种自私的网页（其实是为了满足 Markov 链的收敛性），于是设定其对所有的网页（包括它自己）都有出链。

如果互联网中一个网页只有对自己的出链，或者几个网页的出链形成一个循环圈。那么在不断地迭代过程中，这一个或几个网页的PR值将只增不减。为了解决这个问题。我们想象一个随机浏览网页的人，当他到达C网页后，显然不会傻傻地一直被C网页的小把戏困住。我们假定他有一个确定的概率会输入网址直接跳转到一个随机的网页，并且跳转到每个网页的概率是一样的。如图

此图中C的PR值可表示为：在一般情况下，网页的PR值计算如下:

根据上面的公式，我们可以计算每个网页的PR值，在不断迭代趋于平稳的时候，即为最终结果。

3.算法缺点

没有区分站内导航链接。很多网站的首页都有很多对站内其他页面的链接，称为站内导航链接。这些链接与不同网站之间的链接相比，肯定是后者更能体现PageRank值的传递关系。

没有过滤广告链接和功能链接（例如常见的“分享到微博”）。这些链接通常没有什么实际价值，前者链接到广告页面，后者常常链接到某个社交网站首页。

对新网页不友好。一个新网页的一般入链相对较少，即使它的内容的质量很高，要成为一个高PR值的页面仍需要很长时间的推广。

HITS算法与PageRank算法比较

1.HITS算法是与用户输入的查询请求密切相关的，而PageRank与查询请求无关。所以，HITS算法可以单独作为相似性计算评价标准，而PageRank必须结合内容相似性计算才可以用来对网页相关性进行评价；

2.HITS算法因为与用户查询密切相关，所以必须在接收到用户查询后实时进行计算，计算效率较低；而PageRank则可以在爬虫抓取完成后离线计算，在线直接使用计算结果，计算效率较高；

3.HITS算法的计算对象数量较少，只需计算扩展集合内网页之间的链接关系；而PageRank是全局性算法，对所有互联网页面节点进行处理；

4.从两者的计算效率和处理对象集合大小来比较，PageRank更适合部署在服务器端，而HITS算法更适合部署在客户端；

5.HITS算法存在主题泛化问题，所以更适合处理具体化的用户查询；而PageRank在处理宽泛的用户查询时更有优势；

6.HITS算法在计算时，对于每个页面需要计算两个分值，而PageRank只需计算一个分值即可；在搜索引擎领域，更重视HITS算法计算出的Authority权值，但是在很多应用HITS算法的其它领域，Hub分值也有很重要的作用；

7.从链接反作弊的角度来说，PageRank从机制上优于HITS算法，而HITS算法更易遭受链接作弊的影响。

8.HITS算法结构不稳定，当对“扩充网页集合”内链接关系作出很小改变，则对最终排名有很大影响；而PageRank相对HITS而言表现稳定，其根本原因在于PageRank计算时的“远程跳转”。