网络爬取与链接结构

网络爬取是发现和下载网页的自动化过程，通过跟踪超链接进行。由此产生的链接结构形成了一个图，搜索系统既遍历也分析这个图。

Definition

网络爬取是从种子URL开始，重复获取页面并提取其出站链接以发现更多页面的算法遍历过程，而链接结构是指由页面及其之间的超链接形成的定向图。

Scope

本主题涵盖爬虫如何系统地获取网页以及万维网的超链接图如何构建。它涉及爬虫架构、URL前沿和礼貌性约束、重复和近重复检测、新鲜度与重新爬取调度，以及遵守robots排除协议。它还涵盖了网络图的经验特性，例如其宽泛的“蝴蝶结”结构和重尾度分布，这些特性为爬取和链接分析提供了信息。本主题不包括链接在排名中的使用，这部分内容在PageRank和HITS中讨论。

Core questions

• 爬虫如何发现、优先排序和调度其获取的页面？
• 在爬取过程中如何遵守礼貌性、robots排除协议和服务器负载？
• 如何检测和处理重复和近重复页面？
• 随着页面变化，如何保持爬取的新鲜度？
• 网络图呈现出何种大规模结构？

Key concepts

• 网络爬虫 / 蜘蛛
• URL前沿和种子集
• 爬取礼貌性和robots.txt
• 重复和近重复检测
• 新鲜度与重新爬取调度
• 网络图
• 蝴蝶结结构
• 入度与出度分布

Key theories

爬虫架构和URL前沿

爬虫维护一个待获取URL的前沿队列，应用优先级和礼貌性策略，解析已获取页面以提取新链接，并跟踪已访问页面，从而平衡覆盖范围、新鲜度和资源限制。

宏观网络图结构

实证研究表明，网络的链接图具有特征性的“蝴蝶结”形状，包含一个大的强连通核心以及入站和出站组件，以及重尾入度分布，这限制了可达性并为爬取策略提供了信息。

Clinical relevance

爬取是每个网络搜索引擎以及大规模网络分析、归档和数据集构建的数据获取阶段。理解链接结构有助于指导高效爬取，帮助估计覆盖范围，并支撑用于排名的基于链接的权威度量。

History

网络爬虫随着20世纪90年代中期的早期万维网出现，用于填充搜索索引。Cho及其同事在1998年研究了高效爬取和URL排序，2000年的“网络图结构”研究揭示了网络的“蝴蝶结”宏观结构。随着网络的发展，爬取逐渐成熟为一门大规模分布式系统学科，强调新鲜度、覆盖范围和礼貌性。

Key figures

• Andrei Broder
• Prabhakar Raghavan
• Junghoo Cho
• Hector García-Molina

Seminal works

• broder2000
• cho1998
• manning2008

Frequently asked questions

爬虫中的URL前沿是什么？

URL前沿是已发现但尚未获取的URL队列。爬虫根据优先级和礼貌性策略反复从前沿中选择URL，获取页面，提取新链接，并将以前未见的URL添加回前沿。

网络的“蝴蝶结”结构意味着什么？

大规模研究发现，网络图有一个大的强连通核心，一个可以到达核心的“入”组件，一个可以从核心到达的“出”组件，以及触角和不连通的部分，形似一个蝴蝶结。这种形状影响了爬虫可以从给定种子到达哪些页面。