Вычисление Pagerank |
||||
|---|---|---|---|---|
Представьте себе идеального веб-серфера перемещающегося по всемирной паутине. Пусть сёрфер посещает страницу p, случайное блуждание при этом находится в состоянии p. На каждом шаге, веб-сёрфер либо перепрыгивает на другую страницу в сети, выбранную псевдослучайным образом, либо он следует по ссылке на текущей странице, при этом не возвращаясь и не посещая одну и ту же страницу дважды. Вероятность случайного прыжка обозначим как d тогда вероятность перехода по ссылке будет 1-d. Таким образом, вероятность нахождения пользователя на странице p можно вычислить по следующей формуле:  где R(p) - Page Rank страницы, С(p) - число
ссылок на странице, k - число ссылающихся на p страниц,
d- коэффициент затухания (damping factor). Обычно
0.1<d<0.15. Если масштабировать Page Rank таким образом, что
 где N - число всех страниц, для которых производится расчёт PageRank, то R(p) можно рассматривать как распределение вероятности по всем страницам. Для вычисления Page Rank составляется матрица M размером NxN, где каждому элементу mij матрицы присваивается значение R0(p)=1/C(p) в том случае, если с i-й страницы имеется ссылка на j-ую, все оставшиеся элементы матрицы заполняются нулями. Таким образом, вычисление Page Rank сводится к отысканию собственного вектора матрицы M что достигается умножением матрицы M на вектор Rj на каждом шагу итерации. Введение коэффициента затухания гарантирует, что процесс сходится. |
||||
