Алгоритм PageRank: различия между версиями

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