Web-Crawling und Link-Struktur

Web-Crawling ist der automatisierte Prozess des Entdeckens und Herunterladens von Webseiten durch das Verfolgen von Hyperlinks, und die resultierende Link-Struktur bildet einen Graphen, den Suchsysteme sowohl durchlaufen als auch analysieren.

Definition

Web-Crawling ist die algorithmische Durchquerung des Webs, die von Seed-URLs ausgeht und wiederholt Seiten abruft sowie deren ausgehende Links extrahiert, um weitere Seiten zu entdecken, während sich die Link-Struktur auf den gerichteten Graphen bezieht, der durch Seiten und die Hyperlinks zwischen ihnen gebildet wird.

Scope

Dieses Thema behandelt, wie Crawler systematisch Webseiten abrufen und wie die Hyperlink-Struktur des Webs aufgebaut ist. Es befasst sich mit der Crawler-Architektur, der URL-Frontier und den Höflichkeitsbeschränkungen, der Erkennung von Duplikaten und Beinahe-Duplikaten, der Aktualität und der Neu-Crawling-Planung sowie der Einhaltung des Robots Exclusion Protocol. Es behandelt auch empirische Eigenschaften des Webgraphen, wie seine breite Bowtie-Struktur und die Heavy-Tail-Verteilung des Grades, die sowohl das Crawling als auch die Link-Analyse beeinflussen. Die Verwendung von Links für das Ranking, die unter PageRank und HITS behandelt wird, ist ausgeschlossen.

Core questions

• Wie entdeckt, priorisiert und plant ein Crawler die Seiten, die er abruft?
• Wie werden Höflichkeit, Roboterausschluss und Serverlast während des Crawlings respektiert?
• Wie werden doppelte und nahezu doppelte Seiten erkannt und behandelt?
• Wie wird die Aktualität des Crawls aufrechterhalten, wenn sich Seiten ändern?
• Welche großräumige Struktur weist der Webgraph auf?

Key concepts

• Web-Crawler / Spider
• URL-Frontier und Seed-Set
• Crawl-Höflichkeit und robots.txt
• Erkennung von Duplikaten und Beinahe-Duplikaten
• Aktualität und Neu-Crawling-Planung
• der Webgraph
• Bowtie-Struktur
• In-Degree- und Out-Degree-Verteilungen

Key theories

Crawler-Architektur und die URL-Frontier

Ein Crawler verwaltet eine Frontier von abzurufenden URLs, wendet Priorisierungs- und Höflichkeitsrichtlinien an, parst abgerufene Seiten, um neue Links zu extrahieren, und verfolgt besuchte Seiten, wobei er Abdeckung, Aktualität und Ressourcenbeschränkungen ausbalanciert.

Makroskopische Webgraphenstruktur

Empirische Studien zeigen, dass der Linkgraph des Webs eine charakteristische Bowtie-Form mit einem großen stark verbundenen Kern sowie In- und Out-Komponenten aufweist, zusätzlich zu Tendrilen und nicht verbundenen Teilen, und eine Heavy-Tail-In-Degree-Verteilung, die die Erreichbarkeit einschränkt und die Crawling-Strategie beeinflusst.

Clinical relevance

Crawling ist die Datenerfassungsphase jeder Websuchmaschine und von groß angelegten Webanalysen, Archivierungen und Datensatzkonstruktionen. Das Verständnis der Link-Struktur leitet ein effizientes Crawling, hilft bei der Abschätzung der Abdeckung und untermauert die linkbasierten Autoritätsmaße, die im Ranking verwendet werden.

History

Web-Crawler erschienen Mitte der 1990er Jahre mit dem frühen Web, um Suchindizes zu speisen. Cho und Kollegen untersuchten 1998 effizientes Crawling und die URL-Reihenfolge, und die Studie „Graph Structure in the Web“ aus dem Jahr 2000 enthüllte die Bowtie-Makrostruktur des Webs. Mit dem Wachstum des Webs entwickelte sich das Crawling zu einer Disziplin großer verteilter Systeme, die Aktualität, Abdeckung und Höflichkeit betonte.

Key figures

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

Seminal works

• broder2000
• cho1998
• manning2008

Frequently asked questions

Was ist die URL-Frontier in einem Crawler?

Die URL-Frontier ist die Warteschlange der entdeckten, aber noch nicht abgerufenen URLs. Ein Crawler wählt wiederholt URLs aus der Frontier gemäß Prioritäts- und Höflichkeitsrichtlinien aus, ruft die Seiten ab, extrahiert neue Links und fügt zuvor ungesehene URLs wieder der Frontier hinzu.

Was bedeutet die 'Bowtie'-Struktur des Webs?

Groß angelegte Studien haben ergeben, dass der Webgraph einen großen stark verbundenen Kern, eine 'In'-Komponente von Seiten, die den Kern erreichen können, eine 'Out'-Komponente, die von ihm aus erreichbar ist, sowie Tendrilen und nicht verbundene Teile aufweist, die einer Bowtie ähneln. Diese Form beeinflusst, welche Seiten ein Crawler von bestimmten Seeds aus erreichen kann.