Алгоритм PageRank

Алгоритм PageRank представляет собой расширенную версию InDegree, с тем отличием, что ссылкам назначается различный вес, т.е. ссылки с высокачественных (высокоавторитетных) страниц ценятся больше. Таким образом, важно не только количество, но и качество входящих ссылок.

Для опеределения авторитетности веб-страниц PageRank симулирует поведение случайного пользователя, начиная вебсерфинг со случайной страницы и путешествуя по сети далее по ссылкам. Начальная страница обычно выбирается из равномерного распределения. Процесс случайного перехода происходит следующим образом: на начальной странице случайно выбирается исходящая ссылка, и пользователь переходит по ней с вероятностью1-d. Число d отражает вероятность того, что пользователь наберет в адресной строке броузера случайный адрес и перейдет по нему, т.е. не воспользуется исходящими ссылками. Параметр d называется “dumping factor”, и его значение может варьироваться, хотя обычно его принимают равным 0,85.

Для расчета значения PageRank для некой страницы используется следующая формула:

Алгоритм рассматривает множество страниц M(p_i), связанных друг с другом ссылками, с количеством элементов N. PR(p_j) является значением PageRank страницы p_j , принадлежащей этому множеству, а L(p_j) -числом исходящих ссылок с данной страницы. Каждая страница во множестве M(p_i),, ссылающаяся на p_i , сообщает ей долю собственного PageRank-а, размер которой зависит от общего числа исходящих ссылок на данной странице.

Входящие ссылки во множестве M(p_i) могут быть представлены в виде матрицы смежностей (adjacency matrix):

,

где l(p₁,p₂) равно 1 при наличии ссылки между страницами p₁ и p₂ , или нулю в противном случае. Значения PageRanks для всех страниц множества M(p_i) образуют вектор R, представляюший собой доминантный собственный вектор (eigenvector) матрицы смежностей:

Таким образом, формула для расчета PageRank может быть выражена и так:

Значения PageRank рассчитываются заранее (т.е. не во время поиска, а регулярно с определенным интервалом) и не зависят от поисковых запросов. Если необходимо отсортировать результаты на определенное слово или фразу, то значения PageRank используются совместно с факторами ранжирования, напрямую зависящими от запроса (к примеру, плотность и распределение ключевых слов на странице). Использование заранее рассчитанных значений PageRank-а значительно ускоряет сортировку результатов.

Источники

• Borodin, A, Roberts, G.O., Rosenthal, J.S. and Tsaparas, P. ‘Finding authorities and hubs from link structures on the World Wide Web’. In Proceedings of the 10 th International World Wide Web Conference, Hong Kong, May 2001. Available at http://citeseer.ist.psu.edu/borodin01finding.html
• Wikipedia: PageRank

Share elsewhere