Разработан новый метод вычисления PageRank

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

Как известно, PageRank учитывает количество ссылок, ведущее на заданную веб-страницу, а также "качество" ссылающихся страниц, определяемое по количеству их исходящих ссылок. В одной из версий алгоритма, PageRank страницы A вычисляется по формуле PR(A) = (1-d)/N + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn)), где N - количество всех страниц сети; PR(T1) - PageRank страницы T1, ссылающейся на А; C(T1) - количество исходящих ссылок на странице Т1; и d - демпфирующий фактор (мера вероятности того, что случайный серфер продолжит переходить по ссылкам), которому обычно присваивается значение 0,85.

Группа ученых из Италии, Испании и Хорватии представила PageRank с помощью аналога волновой функции, описываемой волновым уравнением Эрвина Шредингера. Данное уравнение связывает вероятность нахождения квантовой частицы в заданной точке с ее энергией.

Для одной веб-страницы аналог волновой функции был приравнен к результату деления значения ее PageRank на число исходящих ссылок. Новое представление позволило вычислять указанную функцию и PageRank с достаточной точностью без использования применяемого обычно итерационного метода, при котором удовлетворительный результат может быть получен только после десятков повторений циклов вычислений.

С помощью нового метода исследователи подсчитали индексы цитирования части доменной зоны .eu, при этом время вычисления PageRank было уменьшено на три порядка. Тем не менее, для всей Всемирной паутины, имеющей около 1010 узлов, новый метод пока неприменим из-за ее больших размеров.

Также исследователи разработали модель Сети в виде ориентированного (учитывающего направление гиперссылок) графа, каждая вершина которого представляла веб-страницу, а ребро - гиперссылку. Разность между числом исходящих и входящих ребер, а также демпфирующий фактор определили значение "потенциала" V.

При равенстве числа исходящих и входящих ребер и отсутствии "потенциалов" граф становился менее ориентированным, что указывало на такую проблему, как обмен ссылками в целях накрутки популярности сайтов.

Как оказалось, пространственное распределение PageRank зависило от "потенциала" - страницы с низким PageRank были локализованы в области с максимальным V и наоборот. Данное открытие легло в основу нового метода представления топологии PageRank, который, возможно, облегчит изучение динамики индексов цитирования и влияющих на них факторов.