Во второй части этой серии я упомянул, как рассчитываются значения PageRank и как работает алгоритм Random-Walk. После этого я упомянул об основных проблемах, которые приводят к неправильному расчету значений PageRank, когда мы пытаемся применить алгоритм PageRank к реальной структуре Интернета. В третьей и последней части этой серии я собираюсь дать информацию об этих проблемах и методах решения.

Во-первых, давайте вспомним, что это за проблемы:

Тупики:

Тупики — это просто узлы, у которых нет исходящих связей. Поэтому, если вы думаете, что многие посетители, просматривающие веб-страницы, каким-то образом попадают на эту страницу без каких-либо ссылок, когда они переходят на страницы случайным образом, они не могут никуда перейти после этого. Они полностью там застряли, поэтому вероятность случайного посетителя оказаться на другой странице будет равна 0 после того, как он попадет на страницу, которая является тупиковой.

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

Если это объяснение не имеет для вас никакого смысла, давайте приведем пример:

Допустим, наш сетевой граф такой. Как видите, страница E не имеет исходящих ссылок, она имеет только входящие ссылки на себя. Е - тупик. Итак, если мы вычислим матрицу перехода для этого конкретного графика, она будет выглядеть так:

Если мы пойдем по пути случайного серфера, это будет так:

Как вы можете видеть на этих страницах, возможность оказаться где угодно в конечном итоге сходится к 0 после некоторых шагов. Что ж, это проблема, так как значения PageRank страниц на графике станут равными 0.

Работа с тупиками:

Существует два основных способа решения тупиковой проблемы:

  1. Удаление тупиков: этот процесс удаляет страницы, которые являются тупиками, и все ссылки, ведущие на эту конкретную страницу. Этот процесс может привести к возникновению других тупиков. Чтобы предотвратить это, мы продолжаем рекурсивно удалять тупики и входящие связи, чтобы в конечном графе больше не было тупиков.
  2. Метод налогообложения, о котором я расскажу после того, как напомню о ловушках для пауков, решает обе наши основные проблемы.

Ловушки для пауков:

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

Это простейшая форма ловушки для пауков только с одной страницей, E. E имеет две входящие ссылки и только одну исходящую ссылку на себя. Как видно из графика, после того, как вы перейдете на E, вы не сможете снова посетить какую-либо другую страницу. В какой-то момент вероятность оказаться на других страницах будет равна 0, и все значения вероятности уйдут через ловушку для пауков. В то время как страницы в ловушке для пауков получат все значения PageRank, ни одна другая страница не получит их. Матрица перехода M для графика выше:

После n шагов значения вектора v сойдутся к этому:

Обратите внимание, что вероятность оказаться на странице, отличной от E, равна 0 после n шагов. Поэтому значения PageRank этих страниц становятся равными 0.

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

Налогообложение

Помните, что наш расчет для случайного пользователя составляет v’=M*v для каждого шага. Давайте определим общий подход к решению этих двух основных проблем:

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

где ß — константа, используемая для распределения вероятностей при телепортации, а e — вектор единиц соответствующего размера. а n – количество страниц на диаграмме. ßMv часть формулы представляет возможность перехода по исходящей ссылке для следующего шага, а остальная часть — вероятность телепортации на случайную страницу.

Если мы применим нашу новую формулу к предыдущему графику, где ß=0,8, формула итерации для следующего шага будет:

И мы повторяем n шагов, чтобы значения сошлись:

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

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

Буду очень признателен за ваши комментарии и вопросы об этой серии. Спасибо за чтение!

Ресурсы:

Юре Лесковец, Ананд Раджараман, Джефф Ульман. «Анализ массивных наборов данных»