研究生课程：现代信息检索-第18讲 链接分析

《现代信息检索》课程笔记：第18讲 链接分析

第18讲 链接分析

链接无处不在

• 真实性和权威性的有效来源
  • 垃圾邮件-哪些电子邮件帐户是垃圾邮件发送者？
  • host质量-哪些 host 质量不好？
  • 电话呼叫记录
• 好节点、坏节点和未知节点
  • 好节点不会指向坏节点
    • 如果一个节点指向了坏节点，那么这个节点是坏节点
    • 如果一个好节点指向这个节点，那么这个节点是好节点
  • 所有其他貌似合理的组合

为什么我们对链接分析感兴趣？

链接分析对目前为止的完全基于文本的IR任务进行了补充

• （文档）评分和排序
• 基于链接的聚类-来自链接的主题结构
• 链接作为分类特征-彼此链接的文档可能是同一主题
• 爬虫-根据已看到的链接，我们下一步要爬取哪里？

Web可以看成一个有向图

• 假设1: 超链接代表了某种质量认可信号
• 假设2: 锚文本描述了文档d2 的内容

对锚文本构建索引

• 因此，锚文本往往比网页本身更能揭示网页的内容
• 在计算过程中，锚文本应该被赋予比文档中文本更高的权重

PageRank背后的假设

• 假设1：Web 上的链接是网页质量的标志-链出网页的作者认为链向的网页具有很高的质量
• 假设2：锚文本能够描述链向网页的内容

Google炸弹：指由于人为恶意构造锚文本而导致的结果很差的搜索。用户群体有意创建链接误导搜索引擎

锚文本索引：将从指向文档D的链接的锚文本（也可能包含锚文本附近的文本）包含在D的索引中

有时会产生低于期望的效果，例如：垃圾邮件过滤应用全然失败

可以根据锚页面网站的权威性对锚文本进行加权

链接服务器：低成本地获取所有链接信息

• 支持网络图上的快速查询
• 将映射存储在内存中
• 应用：链接分析、网络图分析、爬虫控制

Boldi and Vigna：基本目标-维护内存中的节点邻接表

邻接表压缩中利用到的属性：

• 相似度（邻接表之间）
• 位置（一个页面中的许多链接都连接到“附近”的页面）
• 在已排序的邻接表中使用间隔编码
• gap value的分布

间隔编码

给出整数x,y,z 的已排序列表，用 x y-x z-y 来对 x,y,z 进行表示

使用编码来压缩整数

BV算法的主要优势

• 仅依赖于位置的规范顺序
  • 字典顺序对web十分适用
• 邻接查询可以被非常高效地回答
  • 要获取外部邻居，需要回溯到链的原型
  • 在实践中，这条链通常很短（因为相似性主要基于host 内部）
  • 编码过程中也可以明确限制链的长度
• 易于实现one pass 算法
  • 顺序读取，不需要无限缓冲。读取复杂度与网页数量是线性关系

引用分析

引用分析：科技文献中的引用分析

另一个应用：引用频率可以用度量一篇文档的影响度

更好的度量方法：对不同网页来的引用频率进行加权

PageRank

• 一个网页如果它的入链越多，那么它也越重要（PageRank 越高）
• 一个网页如果被越重要的网页所指向，那么它也越重要（PageRank 越高 )

原始PageRank的一个不足：图中存在一个循环通路，每次迭代，该循环通路中的每个节点的 PageRank不断增加，但是它们并不指出去，即不将PageRank分配给其他节点！

改进的PageRank公式：随机冲浪或随机游走(Random Walk)模型

HITS: Hub节点&Authority节点

每个网页计算两个值：

Hub：作为目录型或导航型网页的权重

Authority：作为权威型网页的权重

一个网页被越重要的导航型网页指向越多，那么它的Authority越大；

一个网页指向的高重要度权威型网页越多，那么它的Hub越大。

HITS算法也是收敛的，也可以通过迭代的方式计算。

HITS算法的实际计算过程

• 首先进行Web 搜索；
• 搜索的结果称为根集（从搜索结果中选择一部分排名靠前的网页作为根集，也叫做种子集合）
• 将所有链向种子集合和种子集合链出的网页加入到种子集合；
• 新的更大的集合称为基本集
• 最后，在基本集上计算每个网页的hub值和authority值（该基本集可以看成一个小的Web图）。

PageRank vs. HITS

网页的PageRank 与查询主题无关，可以事先算好，因此适合于大型搜索引擎的应用。

HITS算法的计算与查询主题相关，检索之后再进行计算，因此，不适合于大型搜索引擎。