PageRank

Происхождение и история термина

В экземпляре отчёта The PageRank Citation Ranking: Bringing Order to the Web стоит дата 29 января 1998 года. Основной текст описывает оценку страниц через граф, передачу значимости по ссылкам, случайные переходы и проблему страниц без исходящих ссылок. ^[2] Это документированная ранняя версия исследования, а не доказанная дата изобретения.

В том же 1998 году Sergey Brin и Lawrence Page опубликовали The Anatomy of a Large-Scale Hypertextual Web Search Engine. В ней PageRank рассматривается как часть устройства Google, использующая неодинаковый вклад ссылок. ^[3] Таким образом, история термина связана и с математической моделью, и с её применением в поиске.

Работа Langville и Meyer 2004 года развивает математическое изложение: рассматривает переходную матрицу, тупики и условия получения устойчивого распределения. ^[1] Современная справка Google сообщает, что PageRank существенно изменился и остаётся частью основных систем. ^[4] Исторические формулы поэтому не раскрывают все параметры нынешнего поиска.

Суть и механизм

Граф — набор узлов и связей между ними. В нашей задаче узел обозначает страницу, а направленная связь — ссылку с одной страницы на другую. В базовой модели случайный пользователь выбирает исходящие ссылки с одинаковой вероятностью. Страница-источник распределяет свою текущую долю между адресатами; поэтому простого подсчёта входящих ссылок недостаточно. ^{[1] [2]}

К этому движению добавляют телепортацию: выбор страницы из всего заданного списка. В рассматриваемом варианте все страницы имеют равный шанс такого выбора. Это правило не описывает действия каждого настоящего посетителя: оно задаёт вычислительную модель. Для страницы без исходящих ссылок, или тупика, также предусматривается распределение перехода по всему списку. ^[1]

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

Здесь N — число страниц, p — доля страницы, t — номер шага, L — число исходящих ссылок страницы-источника. Сумма учитывает только источники, ссылающиеся на рассматриваемую страницу. Параметр τ означает вероятность телепортации; в основном расчёте он строго больше нуля и меньше единицы. Коэффициент перехода по ссылке равен единице минус τ. Эта запись получена из модели ^[1]; обозначение параметра изменено, чтобы явно назвать вероятность телепортации.

Деление на N распределяет общую добавку между всеми страницами. Если вместо неё прибавлять τ каждой странице, сумма уже не сохранится. При наличии тупиков к правой части добавляют их общую текущую долю, умноженную на коэффициент ссылочного перехода и разделённую на N. Так учитывается масса, которую иначе некуда передать. ^[1]

Виды и классификации

Для практического чтения редакция различает три объекта. Это поясняющая схема статьи, а не официальная классификация поисковика.

Последняя строка — правило проверки: одинаковая подпись или похожее число ещё не доказывает совпадения алгоритмов. Даже два корректных локальных расчёта сравнивают только после сверки состава страниц и ссылок. При изменении графа меняются исходные условия модели. ^[1]

Как применяется на практике

Google описывает несколько систем, которые помогают определить порядок результатов по запросу. ^[4] Поэтому локальный ссылочный расчёт полезно отделять от проверки, отвечает ли страница на вопрос читателя. Высокая доля в учебном графе сама по себе не обещает место в выдаче.

HTTP-статус — код ответа сервера, помогающий проверить доступность адреса. В учебной ситуации издатель нашёл ссылку на удалённую новость в справочнике партнёра. Исправление адреса восстанавливает маршрут для читателя. Из самого исправления нельзя вычислить прирост внутреннего PageRank Google: у издателя нет описания всей используемой системы. ^[4]

Предлагаемый журнал приёмки содержит страницу-источник, целевой адрес, назначение перехода, дату и результат проверки. Редактор может отдельно отметить, куда должна вести ссылка после переноса материала. Это собственная организация работы, а не установленный поисковиком способ измерить PageRank.

Как измерить или проверить

Рассмотрим учебный граф: A ссылается на B, B — на A, C — на A. Исходная доля каждой страницы равна одной трети; вероятность телепортации равна 0,3. Тупиков нет. Каждая страница получает базовую добавку 0,1, а оставшиеся 0,7 распределяются по ссылкам.

Для A складываются две исходные трети, умноженные на 0,7, и добавка 0,1. B получает вклад только от A. C получает лишь телепортационную добавку. Точные дроби в таблице дают сумму один; округлённые числа используются только для показа.

Это первая итерация, то есть один повтор вычисления. Она не равна окончательному устойчивому распределению. Для следующих шагов используют весь предыдущий набор значений одновременно: нельзя сначала обновить A, а затем подставить уже новое A при расчёте B. Такой порядок изменил бы описанную процедуру. ^[1]

Воспроизводимая проверка фиксирует список узлов, направление каждой связи, начальные доли, параметр, обработку тупиков и условие остановки. Можно, например, остановить учебный расчёт, когда сумма абсолютных изменений долей за шаг стала меньше заранее выбранного порога. Это критерий точности вычисления, а не оценка качества страницы. ^[1]

Сохранение общей суммы — необходимая, но недостаточная проверка: неверно развёрнутые ссылки тоже могут дать сумму один. Поэтому отдельно сверяют каждый вклад. Нулевой размер графа не допускается, поскольку деление на число страниц невозможно. Эти проверки следуют из выбранной формулы и не требуют обращения к поисковой системе.

Ошибки, ограничения и спорные вопросы

Не следует называть долю посещений модельного пользователя реальной посещаемостью сайта. Она получена из заданных переходов, а не из журнала визитов. Также нельзя смешивать шкалы: распределение с суммой один и значения с другой общей суммой сначала приводят к одной нормировке. ^{[1] [2]}

Изменение параметра не обязательно меняет распределение. Редакционный контрпример — цикл из трёх страниц с одной ссылкой у каждой: при равных начальных долях они остаются равными и при телепортации 0,3, и при 0,6. Это проверка формулы на симметричном графе, а не наблюдение о Google.

Google относит создание ссылок преимущественно ради манипулирования ранжированием к ссылочному спаму. Платная реклама рассматривается отдельно: правила допускают соответствующие ссылки с sponsored или nofollow. ^[5] Руководство предпочитает sponsored для платных размещений. ^[6] Из этих указаний нельзя вывести обещание определённой «передачи веса».

Частые вопросы

Связанные термины

• obratnaya-ssylka
• ranzhirovanie
• ssylochnaya-massa
• nofollow
• e-e-a-t
• iks