链接分析

1. 关键词倒排索引
   • 早期搜索引擎根据网页内容建立关键词的倒排索引
   • 这种方法很容易被网站所有者使用关键词作弊(term spam)
2. 因此谷歌提出PageRank
   • 模拟用户上网行为，使用网页间跳转关系计算PageRank
   • 判断网页内容时，不仅考虑网页本身内容，更要考虑指向该网页的链接或其周围内容
   • 造假者很难控制别人的网页，所以提高造假难度
3. PageRank计算
   • 整个web是一个有向图G，可以得到所有页面之间的__转移矩阵(w)__
   • 所有网页的pagerank组成一个向量v，初始值为[1/n, 1/n,…]
   • 不断迭代 ` v=w*v `
   • 如果G是一个强连通图，即所有的节点的入度出度都不为0，上述迭代会正确收敛
   • web结构复杂，很多网页出度为0，称为终止点
     1. 转移到这些页面的重要性会不断流失，导致最总部分或所有结果为0
     2. 方法1，先从G中递归的删除这些终止点，计算pagerank，之后再逆序计算删除的节点
     3. 方法2(更好)，修正计算过程，认为，每个节点有部分概率进行随机跳转
        • v = beta*m*v + (1-beta)*e
        • beta常量参数，一般在0.8-0.9之间；e是分量都是1/n的n维向量
   • 快速计算
     • 转移矩阵M非常稀疏( 10^-8 )，之保存非0值
     • 并行计算，对转移矩阵进行切分
4. 面向主题的PageRank
   • 主要是优化随机跳转的e(方法2中)，提高目标主题网页的跳转概率
   • 具体方法
     1. 对所有网页进行主题分类，建立每个主题的网页集合(构建e)
     2. 为每个主题建立特定的转移矩阵(构建m)
     3. 对于特定的搜索请求，使用某种方法确定目标主题集合(难点)
     4. 利用方法2公式迭代计算
   • 解决第1步问题的方法
     1. 使用Open Directory的分类信息
   • 解决第3步问题的方法
     1. 允许用户手动选择
     2. 通过用户历史搜索记录推断
     3. 利用用户信息判断，如用户收藏夹，facebook上的信息等
5. 链接作弊
   • PageRank想对于关键字倒排索引算法健壮许多，但仍会收到攻击
   • 如垃圾农场，即建立各种假链接相互指向
   • 虽然可以识别一些垃圾农场结构进行过滤，但扩展性弱
   • 提出TrustRank算法
     1. TrustRank是面向主题的PageRank，这里的主题是值得信赖的可靠的网页集合
     2. 如何建立可靠网页集合
        • 人工检查
        • 选择成员受限的域名，如edu, mil, gov等，作弊网页难以放到这些域名下
     3. 垃圾质量
        • 分别计算页面p的普通PageRank值r和基于可靠网页集合的TrustRank值t
        • 网页p的垃圾质量为(r-t)/r
        • 垃圾质量为负或十分接近0，意味这网页p很可能不是垃圾网页，反之…
6. HITS算法
   • 分别考虑了网页的导航度和权威度
   • 导航度衡量该页面的导航价值，类似于page rank方法
   • 权威度衡量了网页的内容的主题价值，类似于到倒排索引方法