CMU 11642 Search Engine - 文件的权威性

PageRank, TSPR, T-Fresh, HITS

作者 QIFAN 日期 2017-04-29
CMU 11642 Search Engine - 文件的权威性

本文主要讨论信息来源(文件)的可靠性依据。

PageRank

PageRank 耳熟能详,这是用于估计网页重要性的一个依据。Larry Page 提出并实现。
PageRank 是独立于 query 的。高 PageRank 的网页不会适用所有的 query。

实现原理

整个网络就是一张巨大的图,每个网页有通向另一些网页的链接,其他网页也有通向这个网页的链接。介绍下列三种算法。

random walk

PageRank 可以看成是一种”任意行走“(random walk)算法。

  • 从任意网页 w 开始,设该网页有 n 个外链。
  • 下一步有两种走法:
    • 选择任意一个外链继续走
    • 选择网络中的任意一个网页继续走
  • 重复上述过程

经过 N 次重复后,某些网页被访问的频率明显比其他网页要高,可以认为这些网页是“更重要”的。公式如下:
$PR(p_k)=\frac {(1-d)}{|C|} + d\sum_{p_j\in InLinks(p_k) }\frac{PR(p_j)}{|OutLinks(p_j)|}$

  • $d$: 走外链的权重
  • $1-d$: 走任意网页的权重
  • $p_k$: 某个网页
  • $PR$: PageRank 分数
  • $|C|$: 整个网络中的网页数量

voting

每个网页 p 给所有链出的网页投票,重复 N 轮直到结束。

结束时,受欢迎的网页得到的总票数比其他网页会多很多。

simple iterative

每个节点设初始值 $currPR = 1/|C|$,$nextPR=0$ ,进入循环:

while(not done)
for 节点 i
用 currPR 更新它所有 outlink 节点的 nextPR ,公式是上方的 $PR(p\_k)$
for 节点 i
currPR = nextPR
nextPR = 0

举例
$B\rightleftharpoons A \rightleftharpoons C , d = 0.5$

  • 初始化
    • $currPR_A=0.33, currPR_B=0.33, currPR_C=0.33$
  • 第 1 轮:
    • 循环 1
      • A 的指向 B 和 C ,用 $currPR_A$ 分别更新 $nextPR_B, nextPR_C$:
        • $nextPR_B= (1-d)/|C| + d\times currPR_A / |outlink(A)| = 0.5/3 + 0.5 * 0.33 / 2 = 0.25$
        • $nextPR_C = 0.25$ 同理
      • B 指向 A ,用 $currPR_B$ 更新 $nextPR_A$:
        • $nextPR_A=(1-d)/|C| + d\times (currPR_B / |outlink(B)| + currPR_C /|outlink(C)|)=0.5/3+0.5*(0.33+0.33)=0.5$
      • C 指向 A ,$nextPR_A$ 在 B 里已经算过
    • 循环 2,更新每个节点的 $currPR$
      • $currPR_A=0.5, currPR_B=0.25, currPR_C=0.25$
  • 重复上述步骤

如何提高 PageRank

  • 有很多指向该网页的链接 inlink
  • 有很多高 PageRank 的 inlink
  • outlink 少

Topic-Sensitive PageRank (TSPR)

给每个网页分配一个 topic ,计算相应的 $PR_{topic} (d)$

对于包含多个 topic 的网页,先根据 query 给不同的 topic 进行一个权重分布,再加总该页面所有 topic 的 PageRank ,得出该页面的 TSPR。公式如下:
$TSPR(d)=\sum_{i\in I_q} w_i \times TSPR_i(d)$

PageRank 的计算会偏向于页面,因为老页面通常会有更多 inlink ,而这些页面有些甚至已经被废弃或者内容跟不上时代,人们有时候更希望新页面。

T-Fresh

T-Fresh 将与页面“新鲜”程度有关的变量纳入考虑:

  • 页面新鲜度:页面多久更新
  • 链接新鲜度:有多少来自新页面的 inlink

先介绍两类网页:

  • Authority :自身内容好的网页
  • Hub :指向很多 Authority 的网页

这两个分数也是叠加重复计算的:
$H(pk)=\sum\{p_j\inInlinks(p_k)} A(p_j)$
$A(pk)=\sum\{p_j\inInlinks(p_k)} H(p_j)$

这类计算并不涵盖整个 web,而是:

  • 初始集合 root set:查询 query 的 top n 网页
  • 将所有 root set 网页 inlink 的网页加入集合
  • 将 root set 集合内的所有 outlink 的网页加入集合
  • 计算 hub 与 authority

这么做的原因如下:

  • root set 是针对 query 的
  • 集合较小,所以计算速度快
  • 以 query 为计算起点的的速度要求必须快

HITS 在大规模搜索引擎场景应用的不多,因为:

  • 更容易被 spam ,只要 root set 里包含了几个 spam page ,最后的 rank 很可能就不对了
  • 运行成本比 PageRank 高

适用于找兴趣小组或者社区内查找。