PageRank разобрали на формулы

    Примерно 95% текста в 25 млрд документов, проиндексированных Google, составлены из маленького словаря в десять тысяч слов. Это значит, что почти любой поисковый запрос выдаст миллионы документов. Таким образом, вычисление релевантности документа представляет собой нетривиальную математическую задачу. Для этого используется комбинация сложнейших математических методов. К тому же, содержимое веба постоянно изменяется, так что показатель релевантности нужно постоянно пересчитывать. Центральное место в системе ранжирования Google занимают алгоритмы PageRank.

    Все мы знаем, что конечным результатом работы PageRank является некий показатель «важности» страницы PR, который принимает значения от PR0 до PR10 и вычисляется путем анализа входящих ссылок. Их количество и качество говорит о важности данной страницы для интернет-сообщества.

    Тот уровень PR, который мы видим, является сильно округленным значением, а точный показатель известен только программистам Google. Показатель PR изменяется по логарифмической шкале, то есть значение PR5 на порядок больше, чем PR4.

    Какие же формулы используются для вычисления PR? Об этом рассказывается в подробной статье на сайте Американского математического общества.

    Вот как работает PageRank. Предположим, что на странице Pj размещено lj ссылок. Если одна из этих ссылок ведет на страницу Pi, то Pj передаст 1/lj своей «важности» странице Pi (примерно по такому же алгоритму работает передача кармы на «Хабре»).

    Уровень важности (то есть, PR) страницы Pi есть сумма всех таких значений со всех входящих ссылок. Если представить набор страниц, ссылающихся на страницу Pi, как Bi, то «важность» Pi вычисляется по следующей формуле:



    Все это похоже на проблему курицы и яйца. Чтобы узнать PR страницы, нам нужно сначала знать PR всех страниц, которые на нее ссылаются. Впрочем, математические методы позволяют решить и эту проблему.

    Для этого создается матрица гиперссылок , в которой строка i столбца j будет иметь следующий вид:



    Это стохастическая матрица, то есть матрица, в которой все столбцы и/или строки — ряды неотрицательных действительных чисел, дающих в сумме единицу.

    Сформируем вектор , элементами которого являются значения PR, то есть «важность» всех страниц. По нашим условиям вектор получается стационарным.

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



    Этой ситуации соответствует такая матрица



    и стационарный вектор



    Расчет показывает, что страница 8 выигрывает конкурс по популярности. Вот та же самая картинка, где наиболее «авторитетные» страницы окрашены более светлым цветом.



    Примерно так работает PageRank, с математической точки зрения. Это только базовые принципы работы алгоритма. С подробностями можно ознакомиться в оригинале статьи.
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 16

      –1
      Сейчас кто-нибудь разберётся в PageRank'е и будет продавать услуги самого охренительного Google-оптимизатора.
        0
        Математики из американского математического общество уже охренели. Чувак потом еще грант попросит на дальнейший реверинжиниринг гуглевской математики.
          0
          и получит ;)
            0
            его гугл на работу возьмет и все :)
              0
              сделает предложение, от которого он не сможет отказаться?
                0
                ну да, вместо гранта ;)
                0
                Это пять:-)
              –1
              А чего такого? Разобрался сам, поделился с другими. Ничего ни у кого не украл. Кроме того, мне кажется тот алгоритм, который использует Гугль на порядок сложнее. А то, что он в своей статье написал, так или иначе давно уже было известно в общих чертах...
                +1
                То, что он написал, уже давно и в общих, и в конкретных чертах изместно - баян.
              +3
              Наконец-то все стало ясно.
              А три года работал на ощупь...
                +6
                А ты яблоки сортировал? Или тёток учил испанским танцам?
                  +1
                  И теток учил, и яблоки сортировал, все было. Но без формулы такой, конечно, приходилось трудно.
                  Подозреваю, что тетки интуитивно это чувствовали. Насчет яблок не уверен - недостаточно данных для анализа.
                    0
                    "Наконец-то все стало ясно" - это всего-лишь иллюзия...
                      +1
                      Вся наша жизнь состоит из подобных иллюзий - но от этого менее живым я себя не чувствую.
                        +2
                        Главное не потерять вкус и интерес к жизни.
                0
                lol, алгоритм запатентован, гуглится через гугл патенты.

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

                Самое читаемое