Структура Веба в виде графа

Инфраструктура эксперимента

Все эксперименты проводились с использованием программы CS2 (Connectivity Server 2 — сервер связности 2), созданной в Центре системных исследований корпорации Compaq, а также данных, которые поступали от поисковой машины AltaVista. Программа CS2 обеспечивает быстрый доступ к информации о связях в Вебе. В соответствии со схемой действий программа CS2 воспринимает на входе данные о проходе по Вебу и строит индуцированное пройденными страницами представление всего Веб-графа в форме базы данных, которая состоит из всех пройденных URL вместе со всеми входящими и исходящими связями между ними. В дополнение, граф расширяется теми URL, на которые как минимум пять раз ссылаются пройденные страницы. (Экспериментальным путем мы определили, что подавляющее большинство URL, не пройденных, но встречавшихся менее пяти раз, оказывается недействительным.)

В двух важных направлениях программа CS2 содержит улучшения исходного сервера связности CS1, описанного в работе (Bharat K., Broder A., Henzinger M., Kumar P., Venkatasubramanian S. The connectivity server: fast access to linkage information on the Web // Proc. 7th WWW, 1998). Во-первых, она существенно повышает сжатие URL и структур данных о связях. В CS1 каждый сжатый URL занимал в среднем 16 байтов. В CS2 каждый URL хранится в 10 байтах. В CS1 каждой ссылке требовалось 8 байтов, чтобы хранить как входящую, так и исходящую связи; в CS2 используется в среднем только 3,4 байта. Во-вторых, CS2 обеспечивает дополнительную функциональность в форме центральной (host) базы данных. Например, в CS2 легко получить все входящие ссылки для данной вершины либо только входящие ссылки с удаленных узлов (remote hosts).

Подобно CS1, программа CS2 спроектирована для обеспечения высокопроизводительного доступа ко всем этим данным на мощном компьютере с ОЗУ, достаточным для хранения базы данных в памяти. На сервере Compaq AlphaServer 4100 с быстродействием 465 МГц и объемом оперативной памяти 12 Гбайт требуется 70—80 мс для преобразования URL во внутренний идентификатор ресурса и наоборот, а также только 0,15 мс/связь для обнаружения любой входящей или исходящей связи. На однопроцессорном компьютере поиск вширь, охватывающий 100 млн вершин, занимает около 4 мин; на 2-процессорном компьютере мы могли выполнять поиск вширь раз в две минуты.

В ходе экспериментов, описываемых в данной работе, база данных для программы CS2 была построена с использованием результатов прохода по Вебу, выполненного поисковой машиной AltaVista в мае 1999 г. База данных CS2 содержит 203 млн URL и 1466 млн ссылок (все они помещаются в памяти объемом 9,5 Гбайт). Некоторые из наших экспериментов повторялись при проходе по Вебу, выполнявшемся сравнительно недавно, в октябре 1999 г., и охватывавшем 271 млн URL и 2130 млн ссылок.

В общем случае, проход по Вебу с помощью поисковой машины AltaVista базируется на большом числе начальных точек, накопленных со временем из разных источников, включая произвольные добавления. Сам проход по Вебу выполняется примерно в стиле поиска вширь, но подчиняется при этом различным правилам, разработанным для того, чтобы избегать перегрузки Веб-серверов, ловушек для роботов (искусственных бесконечных путей), избегать и/или определять сетевой мусор (спам, в данном случае — лавинообразная маршрутизация страниц), бороться с тайм-аутами соединений и т. д. Каждое построение индекса поисковой машиной AltaVista базируется на данных о проходе по Вебу, которые были получены после их дальнейшей фильтрации и обработки, предназначенных для устранения дубликатов и их близких подобий, удаления страниц спама и т. д. В дальнейшем индекс постоянно обновляется, по мере того как различные процессы отбрасывают мертвые ссылки, добавляют новые страницы, обновляют их и т. д. Повторная фильтрация и последующие отбрасывания и добавления не отражаются в сервере связности. Но в целом, база данных программы CS2 может рассматриваться как надмножество всех страниц, хранящихся в индексе в каждый определенный момент времени. Заметим, что из-за наличия множества начальных точек результирующий граф может иметь много связных компонент.

Экспериментальные данные

С использованием CS2 были реализованы следующие основные алгоритмы:

• алгоритм BFS, выполняющий обход при поиске вширь;
• алгоритм BFS-WCC (weakly connected component) для обнаружения слабых компонент;
• алгоритм BFS-SCC (strongly connected component), выявляющий сильно связные компоненты.

Напомним, что и BFS-WCC, и BFS-SCC — простые обобщения алгоритма BFS. Применяя эти три базовые алгоритма, мы провели несколько интересных экспериментов на Веб-графе.

Окончание следует…