Алгоритм PageRank

Постановка задачи

Получив запрос пользователя, существующие службы веб-поиска извлекают все веб-страницы, содержащие термины запроса, что для большинства поисковых запросов приводит к получению огромного количества веб-страниц. Поэтому очень важно упорядочить или ранжировать полученные документы с целью размещения наиболее релевантных документов на первом месте. Часто при ранжировании используется два типа информации: (1) информация, специфичная для запроса, и (2) информация, не зависящая от запроса. Специфичная для запроса часть пытается измерить, насколько документ релевантен запросу. Поскольку она в значительной степени зависит от содержания страницы, то в основном находится под контролем автора страницы. Независимая от запроса информация пытается оценить качество страницы в целом. Для получения объективной оценки качества страницы важно, чтобы информация, не зависящая от запроса, включала в себя метрику, не контролируемую автором. Таким образом, задача состоит в том, чтобы найти такую меру качества страницы, которая (а) не поддавалась бы легким манипуляциям со стороны автора веб-страницы и (б) хорошо работала бы для всех веб-страниц. Это непростая задача, поскольку веб-страницы крайне неоднородны.

Основные результаты

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

Определение на основе линейной алгебры

Пусть n – общее количество веб-страниц. Вектор PageRank – это n-мерный вектор с одной размерностью для каждой веб-страницы. Пусть [math]\displaystyle{ d }[/math] – небольшая константа, например 1/8. Обозначим за [math]\displaystyle{ deg(p) }[/math] количество гиперссылок в основном тексте страницы [math]\displaystyle{ p }[/math], а за [math]\displaystyle{ PR(p) }[/math] – значение PageRank для страницы [math]\displaystyle{ p }[/math]. Предположим сначала, что каждая страница содержит хотя бы одну гиперссылку. В такой коллекции веб-страниц вектор PageRank вычисляется путем решения системы линейных уравнений, содержащей для каждой страницы [math]\displaystyle{ p }[/math] уравнение

[math]\displaystyle{ PR(p) = d/n + (1 - d) * \sum_{q \; has \; hyperlink \; to \; p} PR(q)/deg(q). }[/math]

("q has hyperlink to p" = "q содержит гиперссылку на p")

В матричной нотации вектор PageRank представляет собой собственный вектор с 1-нормой матрицы [math]\displaystyle{ A }[/math] с [math]\displaystyle{ d/n+ (1 - d)/deg(q) }[/math] для записи [math]\displaystyle{ A_{qp} }[/math], если [math]\displaystyle{ q }[/math] содержит гиперссылку на [math]\displaystyle{ p }[/math], и [math]\displaystyle{ d/n }[/math] в противном случае.

Если в этой линейной системе разрешить веб-страницы без гиперссылок, то они могут стать «стоками PageRank», то есть они будут «получать» PageRank от страниц, указывающих на них, но не будут «отдавать» свой PageRank, что потенциально может привести к «необычно высокому» значению PageRank для таких веб-страниц. Брин и Пейдж предложили два способа борьбы с веб-страницами без исходящих ссылок: либо рекурсивно удалять их до тех пор, пока в совокупности не останется ни одной такой веб-страницы, либо добавлять гиперссылку с каждой такой страницы на все остальные страницы.

Модель случайного серфера

Пусть веб-граф [math]\displaystyle{ G = (V, E) }[/math] – это ориентированный граф, в котором каждая вершина соответствует веб-странице, а каждая гиперссылка – ориентированному ребру от ссылающейся вершины к вершине, на которую производится ссылка. PageRank также можно интерпретировать как случайное блуждание по веб-графу следующего вида. Случайное блуждание начинается со случайной вершины в графе. Предположим, что на шаге [math]\displaystyle{ k }[/math] оно посещает страницу [math]\displaystyle{ q }[/math]. Затем оно подбрасывает несимметричную монету и с вероятностью [math]\displaystyle{ d }[/math], или если у [math]\displaystyle{ q }[/math] нет исходящих ссылок, выбирает случайную вершину из [math]\displaystyle{ V }[/math] и посещает ее на шаге [math]\displaystyle{ k + 1 }[/math]. В противном случае он выбирает случайное исходящее ребро текущей вершины и посещает его оконечную вершину на шаге [math]\displaystyle{ k + 1 }[/math]. (Обратите внимание, что это соответствует добавлению ориентированного ребра от каждой страницы, не имеющей гиперссылок, к каждой вершине в графе). При определенных условиях (которые не обязательно выполняются в Интернете) стационарное распределение этого случайного блуждания соответствует вектору PageRank. Подробнее об этом см. в [1, 4].

Брин и Пейдж также предложили вычислять вектор PageRank приблизительно, используя степенной метод, то есть задавая все начальные значения равными [math]\displaystyle{ 1/n }[/math], а затем многократно используя вектор PageRank предыдущей итерации для вычисления вектора PageRank текущей итерации с помощью приведенных выше линейных уравнений. После сотни итераций почти никакие значения не меняются, и вычисления прекращаются.

Применение

Мера PageRank используется компанией Google в качестве одного из факторов ранжирования результатов поиска. Вычисление PageRank может применяться и в других областях. Примерами могут служить управление репутацией в P2P-сетях и изучение зависимостей между словами при обработке естественного языка. В реляционных базах данных PageRank использовался для взвешивания кортежей базы данных, чтобы улучшить поиск по ключевым словам, когда пользователю неизвестна схема. Наконец, при агрегировании рангов PageRank можно использовать для поиска перестановки, минимально нарушающей набор заданных упорядочений. Подробнее об этом см. в [1].

Также изучались вариации алгоритма PageRank. Большое внимание уделяется персонализации вычислений PageRank таким образом, чтобы значения отражали интересы пользователя. Обзор по этой теме см. в работе [3]. Он также может быть модифицирован для использования в целях обнаружения поискового спама, то есть веб-страниц, которые пытаются манипулировать результатами веб-поиска [1].

Литература

1. Berkhin, P.: A survey on PageRank computing. Internet Math. 2(1),73-120(2005)

2. Brin, S., Page, L.: The anatomy of a large-scale hypertextual Web search engine. In: Proc. 7th Int. World Wide Web Conference, pp. 107-117. Elsevier Science, Amsterdam (1998)

3. Haveliwala, T., Kamvar, S., Jeh, G.: An Analytical Comparison of Approaches to Personalizing PageRank. In: Technical Report. Stanford University, Stanford (2003)

4. Langville, A.N., Meyer, C.D.: Deeper Inside PageRank. Internet Math. 1(3), 335-380(2004)

5. Page, L., Brin, S., Motwani, R., Winograd, T.: The PageRank Citation Ranking: Bringing Order to the Web. In: Technical Report. Stanford University, Stanford (1998)