PageRank

Материал из NLPub
Перейти к: навигация, поиск

PageRank — алгоритм анализа ссылок, названный в честь Ларри Пейджа и используемый в поисковой машине Google[1]. Алгоритм присваивает числовое значение каждому элементу множества документов, связанных гиперссылками. Присвоенное числовое значение означает «важность» одного документа по отношению к другим элементам множества.

Применение

Алгоритм PageRank применяется в информационном поиске в задаче ранжирования документов.

Алгоритм

Здесь представлено описание приближённого вычисления значения PageRank для вершин заданного ориентированного невзвешенного графа.

Вход: d — фактор затухания, \epsilon — точность вычисления, граф G = (V, E), где V — вершины, E — рёбра.

Инициализация:

   for v \in V
       
       \textit{ranks}[v] \leftarrow \frac{1}{|V|}
       
       if \textit{Out}(v) = \empty
       
           \textit{sinks} \leftarrow \textit{sinks} \cup \{v\}
   
   \textit{converged} \leftarrow \textit{false}

Определение: \textit{In}(v) — множество вершин, имеющих ребро, входящее в v, \textit{Out}(v) — множество вершин, имеющих ребро, исходящее от v.

Алгоритм:

   while (\neg\textit{converged})
       
       \textit{sinkrank} \leftarrow 0
       
       for s \in \textit{sinks}
       
           \textit{sinkrank} \leftarrow \textit{sinkrank} + \textit{ranks}[s]
       
       \textit{temp} \leftarrow \textit{ranks}
       
       for v \in V
           
           rank \leftarrow \frac{1 - d}{|V|} + \frac{d \cdot \textit{sinkrank}}{|V|}
           
           for w \in \textit{In}(v)
           
               weight \leftarrow \frac{1}{|\textit{Out}(w)|}
               
               rank \leftarrow rank + d \cdot \textit{ranks}[w] \cdot weight
           
           \textit{converged} \leftarrow \textit{converged} \land (\frac{\textit{temp}[v] - \textit{ranks}[v]}{\textit{ranks}[v]} < \epsilon)
       
       \textit{ranks} \leftarrow \textit{temp}
       
       if \textit{converged}
       
           break

Выход: \textit{ranks} — множество вершин и присвоенных им весов.

Сложность и время работы

Время работы алгоритма PageRank оценивается как O(|V| + |E|).

См. также

Примечания

  1. S. Brin, L. Page. The Anatomy of a Large-Scale Hypertextual Web Search Engine, 1998.