Формальное определение 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, также ссылается на многие другие страницы или нет. [Нв]
Эти два фактора отражают очень интуитивные идеи:
- Как правило, лучше получить рекомендательное письмо от признанного эксперта в этой области, чем от неизвестного человека.
- Независимо от того, кто дает рекомендацию, давая рекомендацию другим людям, они уменьшают ценность своей рекомендации для вас.
Как вы заметили, в этой формуле используется своего рода циклическая ссылка, потому что, чтобы узнать диапазон страниц X, вам нужно знать PageRank всех страниц, ссылающихся на X. Тогда как вы вычисляете эти значения? Значения PageRank?... Вот тут-то и возникает следующая проблема конвергенции, описанная в разделе документа.
По сути, если начать с некоторых «случайных» (или, что предпочтительнее, «достойных предположений») значений PageRank для всех страниц и вычислить PageRank по приведенной выше формуле, новые вычисленные значения станут «лучше», если вы повторите этот процесс несколько раз. раз. Значения сходятся, т. е. каждое из них становится все ближе и ближе к тому, что является фактическим/теоретическим значением. Поэтому, повторяя достаточное количество раз, мы достигаем момента, когда дополнительные итерации не добавят никакого практического точность значений, предоставленных последней итерацией.
Теперь... Теоретически это мило и стильно. Хитрость заключается в том, чтобы преобразовать этот алгоритм в нечто эквивалентное, но это можно сделать быстрее. Есть несколько статей, описывающих, как можно выполнить эту и подобные задачи. У меня нет таких ссылок навскидку, но я добавлю их позже. Остерегайтесь, что они будут включать здоровую дозу линейной алгебры.
РЕДАКТИРОВАНИЕ: как и было обещано, вот несколько ссылок об алгоритмах расчета рейтинга страницы. Эффективный расчет PageRank Haveliwala 1999 /// Использование блочной структуры Интернета для вычислений PR Камвар и др. 2003 / // Быстрый двухэтапный алгоритм вычисления PageRank Ли и др. 2002 г.
Хотя многие из авторов приведенных выше ссылок из Стэнфорда, не требуется много времени, чтобы понять, что поиск эффективного расчета, подобного PageRank, является горячей областью исследований. Я понимаю, что этот материал выходит за рамки OP, но важно намекнуть на тот факт, что базовый алгоритм не подходит для больших сетей.
Чтобы закончить очень доступным текстом (но со многими ссылками на подробную информацию), я хотел бы упомянуть Отличная статья в Википедии
Если вы серьезно относитесь к такого рода вещам, вы можете подумать о вводном/повторном занятии по математике, особенно по линейной алгебре, а также о занятиях по информатике, посвященных графам в целом. Кстати, отличное предложение от Майкла Дорфмана в этом посте для видео OCW с лекциями 1806 года.
Надеюсь, это немного поможет...
person
mjv
schedule
20.09.2009
