PageRank

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

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

Применение

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

Алгоритм

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

Вход: — фактор затухания, — точность вычисления, граф , где — вершины, — рёбра.

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

   for 
       
       
       
       if 
       
           
   
   

Определение: — множество вершин, имеющих ребро, входящее в , — множество вершин, имеющих ребро, исходящее от .

Алгоритм:

   while ()
       
       
       
       for 
       
           
       
       
       
       for 
           
           
           
           for 
           
               
               
               
           
           
       
       
       
       if 
       
           break

Выход: — множество вершин и присвоенных им весов.

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

Время работы алгоритма PageRank оценивается как .

См. также

Примечания