«

»

Июнь 02

Алгоритм Page Rank

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

Сейчас поисковые системы (Яндекс, Mail — близкие российскому сегменту интернета) имеют свой собственные алгоритмы, основанный на гиперссылочном рейтинге. Как пример, Яндекс использует свой алгоритм для расчёта ТИЦ (Тематический индекс цитирования)

PageRank производит статический рейтинг веб-страницы. Значение PageRank рассчитывается для каждой страницы в автономном режиме и не зависит от поисковых запросов.

В сущности, PageRank интерпретирует ссылку со страницы x на страницу у, как голос, х страницы, на страницу у.

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

Сначала приведем некоторые основные понятия в контексте Web.

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

Идеи, лежащие в основе алгоритма Page Rank:

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

Рассмотрим Web как ориентированный граф G = (V, E),

  • где V — это множество вершин, то есть множество страниц;
  • E — это множество ориентированных ребер, то есть множество гиперссылок.

Общее число страниц в Интернете представим как n = |V|

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

P(i) = Sum(i,j)E(P(j)/Oj)

где Oj — количество исходящих ссылок со страницы j.

С математической точки зрения мы имеем n линейных уравнений с n неизвестными. Используем матрицу для представления всех уравнений.

А — матрица смежности графа нашего графа:

A = 1/Oj, если (i, j) принадлежит множеству E,

A = 0, в противном случае.

Мы можем записать систему n уравнений в виде:

P = ATP

Это будет характеристическим уравнением системы, решением которой является вектор P с соответствующими значениями 1.

Реализация алгоритма Page Rank на C#

/// <summary>
/// Вычисление Page Rank
/// </summary>
/// <param name=”a”>матрица Смежности</param>
/// <param name=”n”>размерность матрицы</param>
/// <param name=”sumLink«>Колво ссылок на i страницу</param>
/// <returns>Page Rank сайта</returns>

private double PageRank(int[,] a, int n, int[] sumLink)
{
double PR;
double sum;
double eps;
const double kZatuhania = 0.85; // Коэффициент затухания
double[] pagesRankOld = new double[n];
double[] pagesRank = new double[n];

for (int i = 0; i < n; i++)
pagesRankOld[i] = 1;

do
{
eps = 0;
PR = 0;
for (int j = 0; j < n; j++)
{
sum = 0;
pagesRank[j] = (1 — kZatuhania);
for (int i = 0; i < n; i++)
{
if (a[j, i] > 0)
sum += pagesRankOld[i] / sumLink[i];
else
sum += 0;
}
sum = kZatuhania * sum;
pagesRank[j] += sum;
}

for (int i = 0; i < pagesRank.Length; i++)
PR += pagesRank[i];
for (int i = 0; i < pagesRank.Length; i++)
eps += (pagesRank[i] — pagesRankOld[i]) * (pagesRank[i] — pagesRankOld[i]);

pagesRankOld = pagesRank;
}
while (eps > 0.0001);
return PR;
}

Параметр d называется коэффициентом затухания, которsq может быть установлен в диапазоне от 0 до 1. В нашем случае d = 0.85.

Итерационный процесс заканчивается, когда значения Page Rank не изменяются или сходятся.

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

Запатентованный Google алгоритм Page Rank для ранжирования веб-страниц получил применение — в химии. На его основе химики из Университета штата Вашингтон (Аврора Кларк, Барбара Логан Муни и Рене Корралес) разработали свой алгоритм, получивший наименование moleculaRnetworks.

В отличие от Page Rank, оценивающего релевантность ссылок, moleculaRnetworks «ранжирует» молекулы воды по количеству производимых каждой из них водородных связей, а также то, каким количеством таких связей обладает каждая из окружающих её молекул.

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

Презентацию статьи можно скачать по ссылке Page Rank.
Реализация на C#