PageRank и блочная структура web

Каждая страница в web может однозначно идентифицироваться парой чисел: идентификатором сайта, на котором она находится, и внутрисайтовым идентификатором страницы (уникальным только в пределах сайта). Эту пару можно считать уникальным идентификатором страницы в web.

Нарисуем график. По осям x и y расположим web-страницы, упорядоченные по их идентификатору: порядок определяется идентификатором сайта, а для страниц одного сайта – внутрисайтовым идентификатором. Если страница a ссылается на страницу b, на графике нарисуем точку с координатой (a, b). Вот так выглядит такой график:

Если ограничиться только страницами из домена .com, то график выглядит так:

Приблизимся ещё на один шаг – рассмотрим страницы, принадлежащие сайтам доменов stanford.edu и berkeley.edu:

Картинки взяты из Efficient Parallel Computation of PageRank (Christian Kohlschutter и др.) и Exploiting the Block Structure of theWeb for Computing PageRank (Sepandar D. Kamvar и др.).

Диагонали на графиках состоят из цепочки квадратных блоков. Некоторые из них больше, некоторые меньше, но в основном они имеют примерно одинаковый размер.

Каждый такой блок – это отдельный сайт. Страницы внутри сайта связаны ссылками между собой гораздо плотнее, чем со страницами других сайтов. По статистике 90% ссылок в web – внутрисайтовые.

Это открытие способствовало появлению алгоритмов вычисления PageRank, которые позволяют, как ускорить само вычисление, так и осуществлять его параллельно на нескольких машинах.

Самый известный из них так и называется – метод блочной структуры.

Метод блочной структуры (Block structure method)

Алгоритм состоит из четырёх шагов:

1. Строится граф сайтов. В этом графе сайт a связан с сайтом b, если на сайте a есть страница, ссылающаяся на страницу сайта b. Для этого графа выполняется классический PageRank. В результате для каждого сайта мы имеем некое число, которое можно назвать его рейтингом.

2. Затем каждый сайт обрабатывается в отдельности. Мы анализируем внутреннюю структуру: применяем классический PageRank к графу страниц сайта. Ссылки между сайтами игнорируются. Таким образом, для каждой страницы мы получаем так называемый локальный PageRank. Этот этап можно выполнять параллельно на нескольких машинах.

3. Локальный PageRank каждой страницы умножается на рейтинг сайта, на котором она находится и записывается в вектор Z.

4. Вектор Z используется как начальный вектор для вычисления классического PageRank для полного графа web-страниц. При использовании такого начального вектора, необходимое количество итераций сокращается вплоть до 50%.

Вычисление локального PageRank имеет следующие свойства:

1. Т.к. отдельные сайты значительно меньше всего web, локальный PageRank можно вычислять, храня необходимые данные в памяти, а не на жёстком диске, что существенно ускорит работу

2. Локальный PageRank можно вычислять параллельно на нескольких машинах

3. Алгоритм PageRank для графа страниц большинства сайтов сходится достаточно быстро – иногда бывает достаточно всего нескольких итераций

То есть выигрыш метода блочной структуры достигается за счёт того, что 50% итераций PageRank на полном графе заменяются более эффективными операциями.

Сайт, как правило, считается синонимом хост. Конечно, есть методы определения более точных границ сайта на основе алгоритмов кластеризации. Но, я полагаю, что приближение сайт = хост работает вполне адекватно.


Метод блочной структуры – это только один из алгоритмов, вдохновлённых блочной структурой web. Другие алгоритмы отличаются в основном 3-м и 4-м этапом – т.е. тем как из рейтинга сайтов и локальных PageRank получается окончательный результат.

Многие из этих алгоритмов добиваются существенного ускорения работы за счёт отказа от вычисления точного PageRank и вычисляют его аппроксимацию. Аппроксимации часто бывает вполне достаточно. Это позволяет отказаться от вычислительно самого сложного 4-го этапа – вычисления PageRank для полного графа web-страниц. Подробную информацию можно найти среди статей из подборки.

Siterank

PageRank страницы не зависит от того, на каком сайте она находится. Роль играют только связи между страницами.

В экспериментальной области исследований находятся алгоритмы, использующие рейтинг сайта (аналогичный полученному на первом этапе метода блочной структуры) не для аппроксимации PageRank, а для получения более качественного ранжирования.

Недостатком PageRank является то, что он поощряет старые страницы, на которые уже накопилось много ссылок, и недооценивает новые, на которые ссылки ещё не успели появиться в большом количестве.

Если учитывать рейтинг сайта, у новой страницы, появившейся на хорошем сайте, уже сразу может быть некий стартовый бонус, что не позволит ей потеряться в пучине.

Такой алгоритм, учитывающий структуру межсайтовых связей, может быть более устойчивым к поисковому спаму – манипулировать структурой страниц гораздо проще, чем структурой связей между сайтами (хостами).