Оригинальный алгоритм PageRank

Этот алгоритм был создан на базе диссертации PageRank (http://infolab.stanford.edu/~backrub/google.htm), авторство которой принадлежит Sergey Brin и Larry Page (тогда они еще были студентами университета Stanford University).

В этой работе заявляется, что каждая ссылка на web-страницу является голосом за эту страницу. Однако голоса имеют разный вес. Чтобы вы лучше поняли, как это все работает, мы объясним алгоритм PageRank на высоком уровне. Для начала всем страницам дается прирожденный (но очень маленький) рейтинг PageRank (рис. 7.1).

Рис. 7.1. Начальный рейтинг PageRank для каждой страницы

Затем страницы могут увеличивать рейтинг PageRank, получая ссылки с других страниц (рис. 7.2).

Рис. 7.2. Страницы получают при помощи ссылок дополнительный рейтинг PageRank

Какое количество рейтинга PageRank страница может передать другим страницам при помощи ссылок? Меньше, чем рейтинг PageRank данной страницы. На рис. 7.3 это представлено функцией f(x), означающей, что способный передаваться рейтинг PageRank является функцией от x (суммарного рейтинга PageRank).

Рис. 7.3. Другим страницам может передаваться часть рейтинга PageRank (Passable PageRank – Передаваемый рейтинг PageRank)

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

Рис. 7.4. Передача рейтинга PageRank через ссылку (Link – Ссылка)

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

Рис. 7.5. Простая иллюстрация передачи PageRank

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

Рис. 7.6. Перекрестные ссылки между страницами

Перекрестные ссылки значительно усложняют вычисление PageRank. На рис. 7.6 страница В делает ссылку обратно на страницу А и передает некоторое количество fly) рейтинга PageRank обратно странице А. На рис. 7.7 вы должны понять, как это влияет на рейтинг PageRank всех страниц.

Рис. 7.7. Итеративные вычисления PageRank

Главный вывод здесь таков: когда страница В делает ссылку на страницу А для того, чтобы сделать ссылку взаимной, рейтинг (х) страницы А начинает зависеть от f(y), передаваемого рейтинга страницы В (который зависит от f(x)!). Кроме того, на рейтинг, передаваемый страницей А странице С, влияет также и ссылка со страницы В на страницу А. Это создает очень сложную ситуацию, когда вычисление рейтинга PageRank любой страницы в Интернете должно выполняться при помощи рекурсивного анализа.

Определим новые параметры:

• q – это рейтинг, который накапливается на странице В от ссылки со страницы А (после того, как будут выполнены все итеративные вычисления);

• z – это рейтинг, который накапливается на странице А от ссылки со страницы В (опять-таки, после выполнения всех итераций).

Сценарий на рис. 7.8 создает дополнительные сложности, потому что вводит ссылку со страницы В на страницу D. В этом примере страницы А, В и С – это внутренние ссылки в пределах одного домена, а страница D – это другой сайт (в данном примере показана Wikipedia). В исходной формуле PageRank внутренние и внешние ссылки передавали рейтинг совершенно одинаково. Выяснилось несовершенство такого распределения, т. к. издатели обнаружили, что ссылки на другие сайты создают "утечку" рейтинга с их собственных сайтов (рис. 7.8).

Рис. 7.8. Утечка рейтинга PageRank

Поскольку страница В ссылается на Wikipedia, то некоторая часть рейтинга, передаваемого PageRank, посылается туда вместо других страниц, на которые ссылается страница В (в нашем примере это страница А). На рис. 7.8 мы представляем это параметром w, который является рейтингом, не попадающем на страницу А из-за ссылки на страницу D.

Утечка рейтинга PageRank представляла собой весьма существенный недостаток алгоритма. Если бы те, кто создает страницы для ранжирования в Google, изучили основные принципы PageRank, они быстро поняли бы, что ссылки наружу со своего сайта приносят больше вреда, чем пользы. Если бы такой философии стало придерживаться большое количество web-сайтов, то это подорвало бы концепцию "ссылки – это голоса" и нанесло бы вред компании Google. Не стоит и говорить, что Google исправила этот недостаток своего алгоритма, а потому об утечке рейтинга PageRank беспокоиться уже не приходится. Качественные сайты могут делать ссылки на другие релевантные качественные страницы по всему Интернету.

Но даже после этих изменений внутренние ссылки по-прежнему передают некоторое количество PageRank (рис. 7.9).

Рис. 7.9. Внутренние ссылки по-прежнему передают некоторое количество PageRank

Компания Google изменяла и улучшала алгоритм PageRank много раз. Однако тем, кто занимается оптимизацией результатов Google, знать исходный алгоритм, безусловно, полезно.

Дата добавления: 2015-10-13