Webクローリングとリンク構造

Webクローリングは、ハイパーリンクをたどってウェブページを発見しダウンロードする自動化されたプロセスであり、結果として得られるリンク構造は、検索システムが巡回し分析するグラフを形成します。

Definition

Webクローリングは、シードURLから始まり、繰り返しページを取得し、その発信リンクを抽出してより多くのページを発見する、ウェブのアルゴリズム的巡回であり、リンク構造とは、ページとそれらの間のハイパーリンクによって形成される有向グラフを指します。

Scope

このトピックでは、クローラーがどのように体系的にウェブページを取得するか、およびウェブのハイパーリンクグラフがどのように構造化されているかを扱います。クローラーのアーキテクチャ、URLフロンティアとポライトネス制約、重複およびほぼ重複の検出、鮮度と再クロールのスケジューリング、robots除外の尊重について説明します。また、ウェブグラフの経験的特性、例えばその広範な蝶ネクタイ構造や裾の重い次数分布についても扱い、これらはクローリングとリンク分析の両方に情報を提供します。PageRankとHITSで扱われるリンクのランキング利用は除外します。

Core questions

• クローラーはどのようにして取得するページを発見し、優先順位を付け、スケジュールするのでしょうか？
• クローリング中にポライトネス、robots除外、サーバー負荷はどのように尊重されるのでしょうか？
• 重複およびほぼ重複のページはどのように検出され、処理されるのでしょうか？
• ページが変更されるにつれて、クロール鮮度はどのように維持されるのでしょうか？
• ウェブグラフはどのような大規模構造を示すのでしょうか？

Key concepts

• ウェブクローラー / スパイダー
• URLフロンティアとシードセット
• クロールポライトネスとrobots.txt
• 重複およびほぼ重複の検出
• 鮮度と再クロールスケジューリング
• ウェブグラフ
• 蝶ネクタイ構造
• 入次数と出次数分布

Key theories

クローラーアーキテクチャとURLフロンティア

クローラーは、取得すべきURLのフロンティアを維持し、優先順位付けとポライトネスポリシーを適用し、取得したページを解析して新しいリンクを抽出し、訪問済みページを追跡し、カバレッジ、鮮度、リソース制限のバランスを取ります。

マクロスコピックなウェブグラフ構造

経験的調査によると、ウェブのリンクグラフは、大きな強連結なコアと、コアに到達できる「イン」コンポーネント、コアから到達できる「アウト」コンポーネント、さらに触手状の部分と切断された部分からなる特徴的な蝶ネクタイ型を示し、裾の重い入次数を持ち、これは到達可能性を制約し、クローリング戦略に情報を提供します。

Clinical relevance

クローリングは、あらゆるウェブ検索エンジン、大規模なウェブ分析、アーカイブ、データセット構築におけるデータ取得段階です。リンク構造を理解することは、効率的なクローリングを導き、カバレッジを推定するのに役立ち、ランキングで使用されるリンクベースの権威測定の基礎となります。

History

ウェブクローラーは、1990年代半ばの初期のウェブとともに登場し、検索インデックスに情報を提供しました。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をフロンティアに戻します。

ウェブの「蝶ネクタイ」構造とは何を意味しますか？

大規模な研究により、ウェブグラフには大きな強連結なコア、コアに到達できるページの「イン」コンポーネント、コアから到達できる「アウト」コンポーネント、さらに触手状の部分と切断された部分があり、蝶ネクタイに似ていることがわかりました。この形状は、特定のシードからクローラーが到達できるページに影響を与えます。