Формальное определение PageRank, определенное на странице 4 цитируемого документа, выражается в математическом уравнении с помощью забавного символа «Е» (на самом деле это заглавная греческая буква сигмы. Сигма - буква «S»). что здесь означает Суммирование ).
В двух словах, эта формула говорит, что для расчета PageRank страницы X ...
For all the backlinks to this page (=all the pages that link to X)
you need to calculate a value that is
The PageRank of the page that links to X [R'(v)]
divided by
the number of links found on this page. [Nv]
to which you add
some "source of rank", [E(u)] normalized by c
(we'll get to the purpose of that later.)
And you need to make the sum of all these values [The Sigma thing]
and finally, multiply it by a constant [c]
(this constant is just to keep the range of PageRank manageable)
Ключевая идея этой формулы заключается в том, что все веб-страницы, которые ссылаются на данную страницу X, увеличивают ценность до ее «ценности». По ссылке на какую-то страницу они «голосуют» за эту страницу. Однако этот «голос» имеет больший или меньший вес в зависимости от двух факторов:
- Популярность страницы, которая ссылается на X [R '(v)]
- Тот факт, что страница, которая ссылается на X, также ссылается на многие другие страницы или нет. [Nv]
Эти два фактора отражают очень интуитивные идеи:
- Обычно лучше получить рекомендательное письмо от признанного эксперта в этой области, чем от неизвестного.
- Независимо от того, кто дает рекомендацию, также давая рекомендации другим людям, они уменьшают ценность своей рекомендации для вас.
Как вы заметили, эта формула использует в некоторой степени круговую ссылку , потому что для того, чтобы узнать диапазон страниц X, вам нужно знать PageRank всех страниц, ссылающихся на X. Тогда как вы Вычислите эти значения PageRank? ... Вот тут-то и объясняется следующий вопрос конвергенции в разделе документа.
По сути, начиная с некоторых «случайных» (или предпочтительно «приличных догадок») значений PageRank для всех страниц и вычисляя PageRank по формуле выше, новые вычисленные значения становятся «лучше», когда вы выполняете эту итерацию обработать несколько раз. Значения сходятся , т. е. каждое из них становится все ближе и ближе к фактическому / теоретическому значению. Поэтому, повторяя достаточное количество раз, мы достигаем момента, когда дополнительные итерации не добавят любая практическая точность значений, предоставленных последней итерацией.
Теперь ... Это хорошо и теоретически. Хитрость заключается в том, чтобы преобразовать этот алгоритм в нечто эквивалентное, но это можно сделать быстрее. Есть несколько работ, которые описывают, как это, и подобные задачи, могут быть выполнены. У меня нет таких ссылок, но я добавлю их позже. Остерегайтесь, что они будут включать здоровую дозу линейной алгебры.
РЕДАКТИРОВАТЬ: , как и было обещано, вот несколько ссылок, касающихся алгоритмов для расчета рейтинга страницы.
Эффективное вычисление PageRank Haveliwala 1999 ///
Использование блочной структуры сети для компьютерных PR Kamvar etal 2003 ///
Быстрый двухэтапный алгоритм для вычисления PageRank Lee et al. 2002
Хотя многие авторы приведенных выше ссылок из Стэнфорда, не займет много времени, чтобы осознать, что стремление к эффективному PageRank-подобному вычислению является горячей областью исследований. Я понимаю, что этот материал выходит за рамки OP, но важно намекнуть на тот факт, что базовый алгоритм не подходит для больших сетей.
Чтобы закончить с очень доступным текстом (но со множеством ссылок на подробную информацию), я хотел бы упомянуть Отличная статья Википедии
Если вы серьезно относитесь к такого рода вещам, вы можете рассмотреть вводный / курс повышения квалификации по математике, в частности, по линейной алгебре, а также урок информатики, который имеет дело с графами в целом. Кстати, отличное предложение от Майкла Дорфмана, в этом посте, для видео OCW лекций 1806 года.
Надеюсь, это немного поможет ...