Web图

问题：网页本身携带的词项和用户描述同一网页的词项之间往往存在着一定的差异。

解决办法：利用指向目标网页的链接的锚文本中的词项作为索引目标网页的词项。
基于词频或基于机器学习的评分方法来给词项赋予权重。

注：锚文本周围窗口中的文本也可当成锚文本来使用。

PageRnak

基于链接结构的评分和排序方法。

• PageRank值：Web图中每个节点都赋予一个0到1之间的分值，这个分值依赖于Web图的链接结构。

• 随机游走过程：网页浏览者从Web图中一个节点出发，在每一步中，浏览者都会从当前网页A的链出网页中随机选出一个网页作为下一步的访问目标。

• 随机跳转(teleport)：对于当前网页不存在出链的情况，引入随机跳转操作，基于这个操作，浏览者可以从当前节点调到Web图的任一其他节点。(相当于浏览者直接在浏览器中输入一个URL)

  随机跳转的实现：从满足均匀分布的所有网页中随机选择，假如Web图中所有节点数目为N，则以1/N的概率调到每一个节点。

  使用随机跳转的两种方式：(1)当节点没有出链接时，冲浪者调用随机跳转操作。(2)当节点包含出链接时，冲浪者以0<α<1的概率调用随机跳转操作，以1-α的概率继续进行随机游走。

注：采用这种混合过程(随机游走+随机跳转)，浏览者将会以一个固定的时间比例π(v)访问每一个节点。其中π(v)依赖于Web图结构和α。

马尔科夫链

马尔科夫链是一个离散时间随机过程通过一个N*N的转移概率矩阵P来刻画。

Pij表示从当前i状态到下一状态j的条件转移概率，这一转移概率仅依赖于当前状态i。当前状态i每一行的元素之和为1，每个N维的概率向量可以看成这一状态的概率分布。

• 将Web图上的随机冲浪过程看成马尔科夫链

1. 定义Web图的邻接矩阵A：如果存在网页i和网页j的一条链接，那么Aij=1，否则Aij=0。
2. 从矩阵A推导出马尔科夫链的概率转移矩阵P，如果A的某一行没有1，则用1/N代替每一个元素，对于其他行处理如下：
   （1）用每一行中的1的个数去除每个1。(2)上面处理后的结果矩阵乘以1-α。(3)对上面得到的矩阵中每个元素加上α/N。

这样，用概率向量x表示冲浪者任一时间所处位置的概率分布，当t=0时，冲浪者可能处于某一状态，对应x中元素为1，其他为0。当t=1时，冲浪者位置的概率分布可用xP表示。

定义 一个马尔科夫链，如果存在一个正整数 T0 使得对其中所有的状态对 i、j 都满足:若 i 是初始状态，那么对所有的 t>T0，在时刻 t 处于状态 j 的概率都大于 0。此时，称该马尔科夫 链是遍历马尔科夫链(ergodic Markov chain)

遍历性的两个条件(1)不可约性。即任意两个状态之间都存在非零概率转移序列。(2)非周期性。即不存在两个划分后的转态子集间的循环往复。

定理 对任一遍历马尔科夫链，都存在一个唯一的稳态概率向量 πr ，它是矩阵 P 的主左特征向量，并且如果 η(i, t)是在 t 步之内状态 i 的访问次数，那么有

其中，π(i) > 0 是状态 i 的稳态概率。

按照定理，带随机跳转操作的随即游走过程最后会得到其对应的马尔科夫状态的一个唯一的稳态概率分布。某一状态的稳态概率就对应该网页的PageRank。

PageRank的计算

• 特征向量法

根据(18.2) 的左特征值的定义，转移概率矩阵P的N维左特征向量π满足：

主特征向量π是带随机跳转操作的随即游走过程的稳态概率，也就是所有网页的PageRank。
在给定稳态概率分布π的情况下，πP=1π，1是P的特征向量。于是，只要计算出对应于矩阵P的特征值1的主左特征向量，那么就算出了PageRank的值。

• 幂迭代法
  幂迭代方法模拟了冲浪者的游走过程:从某个状态出发，游走一个 很大的步数t，并跟踪对每个状态的访问频率。在经过一个很大步数t之后，这些频率会稳定下来， 此时计算得到的访问频率的变化值会低于某个预先定义的阈值。这些访问频率2就是我们要计 算的PageRank值。

面向主题的PageRank

面向主题的PageRank是一种基于特定兴趣的PageRank，考虑的是非等概率跳到随机网页的情况。

• 对单个主题的PageRank
  若网页浏览者的兴趣是体育，假定与体育相关的网页集合S非空，非空网页集合Y，S包含于Y，其中Y中的随机游走过程存在稳态分布。将面向体育主题的PageRank的分布记为πs，称为面向体育主题的PageRank。
  -多个主题混合
  若用户对多个主题感兴趣，则任一用户的个性化PageRank都可以表示成多个面向主题的PageRank的线性组合。
  比如，拥有 60%体育类兴趣 和 40%政治类兴趣的用户的个性化 PageRank 就可以表示成:
  

Hub网页及Authority

权威型(authority)网页：如关于白血病的权威性网页可以是美国国家癌症研究所有关白血病的网页。
导航型(Hub)网页：对某一主题整理出的权威型网页列表。

一个好的hub网页会同时指向多个好的authority网页，而一个好的authority网页同时会被多个好的hub网页所指向。因此，对于一个包含好的hub网页和authority网页的Web子集及它们之间的链接，每个网页的hub值和authority值的迭代更新过程如下：

上式第一行中，每个网页的 hub 值设为它指向的所有网页的 authority 值之和。换句话说， 如果 v 指向的页面的 authority 值越高的话，那么它的 hub 值也越高。同样，上式第二行中两者 的角色互换，如果页面 v 被 hub 值更高的网页所指向，那么其 authority 值也越高。
在循环迭代过程中，会重新计算所有网页的 hub 值，接着根据更新后的 hub 值又来计算所有网页的 authority 值，接着又根据更新后的 authority 值重新计算所有网页的 hub 值。

将上式写成矩阵-向量形式：

其中A是Web子集的邻接矩阵，上式中的每个式子的右部都是另一个式子左部的一个向 量。于是，将它们互相代入，就会得到：

将上式中的 ← 替换为 = 号并引入未知特征值的话，而下面那个式子则会变成矩阵 ATA 的特征方程：

其中，λh、λa 分别是矩阵 AAT 及 ATA 的特征值。

总结计算过程：
(1) 收集 Web 网页构成网页子集，利用网页的链接形成图结构，计算 AAT 及 ATA; r
(2) 计算 AAT 及 ATA 的主特征向量，得到最后的 hub 值向量 hr 和 authority 值向量 a ;
(3) 输入排名靠前的 hub 网页和 authority 网页。

上述链接分析的方法被称为 HITS(Hyperlink-Induced Topic Search，超链导向的主题搜索）。

Web子集的选择

(1) 给定某个查询(比如 leukemia)，利用某个文本索引获得包含 leukemia 的所有网页。这 些网页被称为根集(root set)。
(2) 将根集及指向根集中的网页和根集所指向的网页加入到基本集(base set)中。