33. Page Rank

Основная идея: считать рейтинг страницы через количество ведущих на нее гиперссылок и рейтинги страниц, с которых ведут эти гиперссылки

Орграф – это граф, у которого на каждом ребре задана ориентация (пара (V,A), где V – конечное мн-во, а А содержится в V²)

Математическая модель

Ориентированный граф G=(V,A) , V – множество HTML-страниц ,(u,v)ÎA если и только если из u ведет гиперссылка к v ,PageRank – метка вершины орграфа G

deg⁺(v) – полустепень исхода вершины v , deg^-(v) – полустепень захода вершины v

w(uv) = r_u/deg⁺(u) , r_u – PageRank вершины u

Как считать PageRank в общем случае?

M_ij = система( ,если ij A, 0 в противном случаи)

M – стохастическая матрица , r_i – PageRank i-го сайта , r = Mr , r – собственный вектор стохастической веб-матрицы

Вероятностная модель PageRank

r_k(i) – вероятность оказаться в i-й вершине после k шагов

Кратчайшие пути в случае, когда веса не обязательно равны 1