Pagerank и его математика: требуется пояснение

Ответ 1

Формальное определение PageRank, как определено на стр. 4 цитируемого документа, выражается в математическом уравнении со смешным символом "E" (на самом деле это синтаксическая буква "Sigma" ). Сигма - это буква "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/// Использование блочной структуры Web для вычислений PR Kamvar etal 2003/// Быстрый двухэтапный алгоритм для вычисления PageRank Lee et al. 2002

Хотя многие из авторов ссылок, приведенных выше, из Стэнфорда, не займет много времени, чтобы понять, что поиск эффективных вычислений с помощью PageRank - это горячее поле исследований. Я понимаю, что этот материал выходит за рамки OP, но важно намекнуть на то, что основной алгоритм не практичен для больших сетей.

Чтобы закончить с очень доступным текстом (еще со многими ссылками на углубленную информацию), я хотел бы упомянуть отличную статью в Википедии

Если вы серьезно относитесь к подобным вещам, вы можете рассмотреть вводный/обновленный класс по математике, в частности, линейную алгебру, а также класс компьютерных наук, который имеет дело с графиками в целом. BTW, большое предложение от Майкла Дорфмана, в этом посте, для видео в OCW из 1806 лекций.

Надеюсь, это немного поможет...

Ответ 2

Если вы серьезно относитесь к разработке алгоритма для поисковой системы, я серьезно рекомендую вам пройти курс линейной алгебры. В отсутствие индивидуального курса курс MIT OCW от Gilbert Strang довольно хорош (видео-лекции в http://ocw.mit.edu/OcwWeb/Mathematics/18-06Spring-2005/VideoLectures/).

Класс, подобный этому, несомненно, позволит вам понять математические символы в документе, который вы предоставили - в этой статье нет ничего, что не было бы охвачено в курсе линейной алгебры первого года.

Я знаю, что это не тот ответ, который вы ищете, но это действительно лучший вариант для вас. Если кто-то попытается объяснить отдельные символы или алгоритмы вам, когда вы не хорошо понимаете основные понятия, это не очень хорошее использование никого.

Ответ 3

Это документ, который вам нужен: http://infolab.stanford.edu/~backrub/google.html (Если вы не узнаете имена авторов, вы найдете больше информации о них здесь: http://www.google.com/corporate/execs.html).

Символы, используемые в документе, описаны в документе на английском языке.

Спасибо, что сделал меня google.

Ответ 4

Вы также можете прочитать вводный учебник по математике, лежащей в основе построения матрицы Pagerank, написанной Дэвидом Остином под названием Как Google находит вашу иглу в Web Haystack; он начинается с простого примера и строит до полного определения.

Ответ 5

"Собственный вектор 25 000 000 000 долларов: линейная алгебра за Google" . от Rose-Hulman немного устарела, потому что теперь рейтинг страницы является проблемой линейной алгебры $491B. Я думаю, что статья очень хорошо написана.

"Программирование коллективного интеллекта" имеет приятное обсуждение Page Rank.

Ответ 6

Duffymo опубликовал лучший отзыв, на мой взгляд. Я изучил алгоритм ранжирования страницы в моем старшем году. Ранг страницы делает следующее:

• Определить набор текущих веб-страниц как состояний конечной цепочки марков.

• Определите вероятность перехода от сайта u к v, где существует исходящая ссылка на v из u, чтобы быть

  1/u_ {n}, где u_ {n} - количество исходящих ссылок из u.

• Предположим, что отмеченная выше марковская цепь неприводима (это может быть выполнено только при небольшом ухудшении результатов)

• Можно показать, что всякая конечная неприводимая цепь Маркова имеет стационарное распределение. Определите ранг страницы как стационарное распределение, то есть вектор, в котором вероятность случайной частицы заканчивается на каждом заданном участке, так как число переходов состояний переходит на бесконечность.

Google использует небольшую вариацию метода мощности, чтобы найти стационарное распределение (метод мощности находит доминирующие собственные значения). Помимо этого нет ничего. Его довольно простое и элегантное и, вероятно, одно из самых простых приложений марковских цепей, о котором я могу думать, но это стоит больших денег!

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

Ответ 7

Если вы хотите узнать больше о ранге страницы с меньшей математикой, то this является очень хорошим руководством по основным операциям матрицы. Я рекомендую его для всех, у кого мало математического фона, но хочет погрузиться в алгоритмы ранжирования.