Веб-краулинг и структура ссылок

Веб-краулинг — это автоматизированный процесс обнаружения и загрузки веб-страниц путем перехода по гиперссылкам, а полученная структура ссылок образует граф, который поисковые системы как обходят, так и анализируют.

Definition

Веб-краулинг — это алгоритмический обход Интернета, который начинается с начальных URL-адресов и многократно извлекает страницы и их исходящие ссылки для обнаружения новых страниц, в то время как структура ссылок относится к ориентированному графу, образованному страницами и гиперссылками между ними.

Scope

Эта тема охватывает то, как краулеры систематически извлекают веб-страницы и как структурирован граф гиперссылок в Интернете. Она рассматривает архитектуру краулера, очередь URL-адресов и ограничения вежливости, обнаружение дубликатов и почти дубликатов, актуальность и планирование повторного сканирования, а также соблюдение исключений для роботов. Она также охватывает эмпирические свойства веб-графа, такие как его широкая структура «бабочки» и распределение степеней с тяжелыми хвостами, которые влияют как на краулинг, так и на анализ ссылок. Исключается использование ссылок для ранжирования, рассматриваемое в PageRank и HITS.

Core questions

• Как краулер обнаруживает, приоритизирует и планирует страницы, которые он извлекает?
• Как соблюдаются вежливость, исключения для роботов и нагрузка на сервер во время краулинга?
• Как обнаруживаются и обрабатываются дубликаты и почти дубликаты страниц?
• Как поддерживается актуальность краулинга по мере изменения страниц?
• Какую крупномасштабную структуру демонстрирует веб-граф?

Key concepts

• веб-краулер / паук
• очередь URL-адресов и начальный набор
• вежливость краулинга и robots.txt
• обнаружение дубликатов и почти дубликатов
• актуальность и планирование повторного сканирования
• веб-граф
• структура «бабочки»
• распределения входящих и исходящих степеней

Key theories

Архитектура краулера и очередь URL-адресов

Краулер поддерживает очередь URL-адресов для извлечения, применяет политики приоритизации и вежливости, анализирует извлеченные страницы для извлечения новых ссылок и отслеживает посещенные страницы, балансируя охват, актуальность и ограничения ресурсов.

Макроскопическая структура веб-графа

Эмпирические исследования показывают, что граф ссылок Интернета имеет характерную форму «бабочки» с большим сильно связанным ядром, а также входящими и исходящими компонентами, и распределением входящих степеней с тяжелыми хвостами, что ограничивает достижимость и влияет на стратегию краулинга.

Clinical relevance

Краулинг — это этап сбора данных для каждой поисковой системы, а также для крупномасштабной веб-аналитики, архивирования и создания наборов данных. Понимание структуры ссылок направляет эффективный краулинг, помогает оценить охват и лежит в основе мер авторитетности на основе ссылок, используемых при ранжировании.

History

Веб-краулеры появились с ранним Интернетом в середине 1990-х годов для наполнения поисковых индексов. Чо и коллеги изучали эффективный краулинг и упорядочивание URL-адресов в 1998 году, а исследование «структуры графа в Интернете» 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-адреса обратно в очередь.

Что означает структура «бабочки» в Интернете?

Крупномасштабные исследования показали, что веб-граф имеет большое сильно связанное ядро, «входящий» компонент страниц, которые могут достигать ядра, «исходящий» компонент, достижимый из него, а также ответвления и несвязанные части, напоминающие бабочку. Эта форма влияет на то, какие страницы краулер может достичь из заданных начальных точек.