Прошлый раз мы вплотную подошли к попытке расчета PageRank, а, точнее, его упрощенной версии - Minirank. Вначале мы не знаем, какие веса MiniRank у этих страниц, поэтому мы их просто присвоим. Для простоты, мы выберем число один. В результате диаграмма становится… Все еще легко! Сейчас вспомните правила передачи веса. Вначале мы применяем коэффициент затухания. (Коэффициент затухания, в основном, говорит о том, что страница не может голосовать так, чтобы другая страница была столь же важна, как она сама. Это означает, что страницы, к которым труднее добраться в Web, менее важны.) Затем мы делим сохранившийся вес на число ссылок. Мы подсчитываем итоговый вес, который должен быть добавлен ко всем до единой страницам, перед тем как мы окончательно его прибавим8. Итак, глядя вначале на страницу A, видим, что значение веса MiniRank, доступное для передачи, после затухания равно 1 * 0,85 = 0,85. Со страницы ведут две ссылки, поэтому, по окончании итерации, мы добавим 0,425 к весу MiniRank страницы B и 0,425 к весу MiniRank страницы C. Мы не можем сделать это до тех пор, пока мы не рассчитали все ссылки страницы, потому что это повлияет на результаты. Перейдем к странице B. Она содержит только одну ссылку. Поэтому, она передаст 1 * 0,85 = 0,85 странице C, когда мы сделаем все вычисления для ссылок. Страница C также имеет одну ссылку. Поэтому она передаст вес 1 * 0,85 = 0,85 странице A. Страница D имеет одну ссылку, поэтому она передает 0,85 странице C. Сейчас мы можем добавить все суммы ко всем весам страниц. Новые значения весов MiniRank показывают, сколь важна страница C. Но мы еще не завершили. Поскольку все страницы начали с одного значения, по правде говоря, мы вычислили только популярность в ссылках (link popularity). Суть PageRank и MiniRank такова, что страницам, на которые чаще ссылаются, следует получить больше голосов; поэтому мы должны проделать то же самое еще раз! На этот раз страница C имеет большее влияние, потому что ее текущий вес MiniRank выше. Так, посмотрим на страницу A вначале. Ее текущий вес MiniRank равен 1,85. Величина MiniRank, доступная для передачи, после применения затухания составляет 1,85 * 0,85 = 1,5725. Есть две ссылки со страницы, поэтому по завершению итерации мы добавим 0,78625 к весу MiniRank страницы B и весу MiniRank страницы C. Перейдем к странице B. У нее есть только одна ссылка. Следовательно, она передаст 1,425 * 0,85 = 1,21125 странице C, когда мы завершим все вычисления со ссылками. Страница C также имеет одну ссылку, но при этом обладает огромным весом 3,125 MiniRank. Поэтому она передаст 3,125 * 0,85 = 2,65625 странице A. Страница D имеет одну ссылку, поэтому она передает 0,85 странице C. Мы получаем…. Мы уже можем видеть то, что следовало ожидать: страница C имеет наибольший вес MiniRank, страница A — следующий по величине. На практике нам нужно было бы повторить эти действия от 50 до 100 раз, чтобы гарантировать, что низкая точность предыдущих итераций сведена на нет. Просто! Обратная связь PageRank Но подождите минутку! Что-то происходит между страницами A и C, поэтому взглянем еще раз. Во время одной итерации вычислений страница C дает странице A повышение в весе MiniRank (PageRank). Во время следующей итерации она сама получает увеличение веса, пропорциональное новому улучшившемуся весу MiniRank страницы A (она получает назад часть своего веса MiniRank!). Это обратная связь PageRank. Можно подумать, что Google обязан игнорировать ссылки такого рода, особенно, если страница A и страница C расположены на одном сайте. Действительно, я слышал мнение нескольких человек, которые считают, что Google обязан. Истина в том, что Google не может сделать это. Представьте проделывание вычислений над миллионами страниц вместо четырех… представьте только как вам определять, когда встречается обратная связь, и как избавляться от нее. И даже если вы справитесь, как вы сведете на нет влияние, которое это окажет на оставшуюся часть системы? Обратная связь PageRank — неотъемлемая часть системы! Фактически, она нужна для правильного функционирования PageRank и является частью алгоритма. Продолжение следует 8 Одно из основных отличий демонстрационного MiniRank от настоящего PageRank в том, что вычисленный на новой итерации вес добавляется к весу страницы, полученному во время предыдущей итерации, в то время как в PageRank новый вес заменяют старый. Еще одно отличие — в MiniRank к новому весу не прибавляется (1-d). Из-за этого эффект «обратной связи», столь привлекательный в примерах с MiniRank, на практике (где используется PageRank) во многих случаях может иметь заметно меньшее значение. [Прим. А. С.] Назад к тексту
511 Прочтений • [Растолкованный PageRank, часть 3. Пример расчета] [20.04.2012] [Комментариев: 0]
Vova
