Алгоритм Page Rank Тверь, 2012г.

Page Rank был представлен и опубликован Сергеем Брином и Ларри Пейджем на 7ой международной конференции World Wide Web (WWW7) в апреле 1998 года. Это поисковый алгоритм ранжирования с использованием гиперссылок в Интернете. На основе алгоритма, они построили поисковой движок Google, который имел огромный успех. Сейчас поисковые системы имеют свой собственный алгоритм, основанный на гиперссылочном рейтинге.

Page Rank рассчитывается для каждой страницы в автономном режиме и не зависит от поисковых запросов. В сущности, Page Rank интерпретирует ссылку со страницы x на страницу у, как голос, страницы х, на страницу у.

Введем формулу Page Rank

Сначала приведем некоторые основные понятия в контексте Web. Входящие ссылки. Это ссылки, которые получает страница i с других страниц. Как правило, ссылки с сайта, которому принадлежит страница i не учитываются. Исходящие ссылки. Это ссылки, которые получают другие страницы от страницы i. Как правило, ссылки на страницы того же сайта не рассматриваются.

Ссылки с сайтов A и B являются бэклинками сайта С

Идеи, лежащие в основе алгоритма Page Rank: Гиперссылки со страницы, указывающие на другую страницу, передают ей полномочия (увеличивают престиж страницы, PR). Другими словами, чем больше ссылок получит страница i, тем больше будет ее престиж, PR. Страницы, указывающие на страницы i имеют свои собственный престиж, PR.

Рассмотрим Web как ориентированный граф G = (V, E), где V – это множество вершин, то есть множество страниц; E – это множество ориентированных ребер, то есть множество гиперссылок. Общее число страниц в Интернете представим как n = |V|

Очки Page Rank для страницы i вычисляются по следующей формуле: где O j – количество исходящих ссылок со страницы j.

С математической точки зрения мы имеем n линейных уравнений с n неизвестными. Используем матрицу для представления всех уравнений. А – матрица смежности графа нашего графа:

Мы можем записать систему n уравнений в виде: P = A T P Это будет характеристическим уравнением системы, решением которой является вектор P с соответствующими значениями 1.

Алгоритм Page Rank

С тех пор как был представлен алгоритм Page Rank, исследователи предложили много усовершенствований и альтернатив его вычисления, вводя дополнительные критерии.

Запатентованный Google алгоритм PageRank для ранжирования веб-страниц получил применение в химии. На его основе химики из Университета штата Вашингтон (Аврора Кларк, Барбара Логан Муни и Рене Корралес) разработали свой алгоритм, получивший наименование moleculaRnetworks. В отличие от PageRank, оценивающего релевантность ссылок, moleculaRnetworks «ранжирует» молекулы воды по количеству производимых каждой из них водородных связей, а также то, каким количеством таких связей обладает каждая из окружающих её молекул. Так, например, используя эту программу, можно быстро смоделировать, как будут располагаться относительно друг друга молекулы воды и ионы соли и в течение какого времени они сохранят своё взаиморасположение.

Спасибо за внимание