PageRank — алгоритм анализа ссылок, названный в честь Ларри Пейджа и используемый в поисковой машине Google[1]. Алгоритм присваивает числовое значение каждому элементу множества документов, связанных гиперссылками. Присвоенное числовое значение означает «важность» одного документа по отношению к другим элементам множества.
Применение
Алгоритм PageRank применяется в информационном поиске в задаче ранжирования документов.
Алгоритм
Здесь представлено описание приближённого вычисления значения PageRank для вершин заданного ориентированного невзвешенного графа.
Вход: — фактор затухания, — точность вычисления, граф , где — вершины, — рёбра.
Инициализация:
for
if
Определение: — множество вершин, имеющих ребро, входящее в , — множество вершин, имеющих ребро, исходящее от .
Алгоритм:
while ()
for
for
for
if
break
Выход: — множество вершин и присвоенных им весов.
Сложность и время работы
Время работы алгоритма PageRank оценивается как .
См. также
Примечания