Ссылочное ранжирование

Коллекцию документов, связанных друг с другом через гипертекстовые ссылки, можно рассматривать в качестве многосвязного графа, по которому совершают переходы читатели. При этом он совершает переходы из одного узла в другой с некоторой вероятностью, описываемой Марковской вероятностной моделью. В этой модели вся коллекция представляется как матрица вероятностей перехода из одной вершины графа в другую вершину – документ. При этом можно определить какие вершины будут чаще посещаться, а значит иметь больший вес в данной коллекции.

Индекс цитирования или Page Rank?

PR(A)=(1-d)+d*(PR(T1))/C(T1)+…+ d*(PR(Tn))/C(Tn)
Где d – некоторый коэффициент, который обычно делают равным 0.8–0.9.

Данная формула является итерационной, ранг страницы зависит от рангов страниц, которые на нее ссылаются, а они, в свою очередь, могут зависеть от ее ранга. Существует несколько методик эффективного вычисления рангов страниц для больших коллекций документов. Обычно для этого используются методы экстраполяции, позволяющие снизить количество итераций при вычислении.

Преимущества данной модели: простота реализации (всего один параметр для каждого документа), малые затраты при поиске и индексировании. Данная модель используется почти всеми коммерческими поисковыми системами, так как специальное завышение ранга нужной страницы в данной модели требует некоторых немалых усилий. Но существуют даже целые фирмы, которые путем создания обманных страниц с множеством ссылок, организацией обмена ссылками между сайтами, автоматическим размещением ссылок на общедоступных каталогах ссылок, форумах и гостевых книгах– накручивают Page Rank? страниц заказчика. Для борьбы с такими методами в рамках данной модели используются некоторые уточнения. Например, учитываются ссылки только с главных страниц сайтов. Или же учитываются ссылки только с «достоверных» ресурсов, отобранных экспертами. Это позволяет на несколько процентов повысить полноту и точность поиска.

Тематический индекс цитирования

Статичный Page Rank? переоценивает документы нерелевантные данному запросу. Поэтому возможна модификация алгоритма, которая учитывает только ссылки между документами, которые признаны релевантными запросу.

В простейшем подходе выделяется фиксированный набор тематик и модель документа расширяется значениями Page Rank?, вычисленными по данному набору. Это позволяет не увеличивать затраты на поиск, вместе с тем незначительно увеличить затраты при индексации документа. Недостатком является необходимость отнесения поискового запроса к одной из тем и в случае ошибки соотнесения возможно ухудшение качества поиска. Другой проблемой данного подхода является необходимость выделения набора тематик документов и запросов.

В случае динамического вычисления ранга страницы в момент поиска требуется для каждого документа хранить информацию о том на какие страницы он ссылается, что может потребовать увеличения затрат памяти и других ресурсов на хранение и обработку этих данных. Построение Page Rank? по документам, которые отобраны как релевантные запросу, принято называть Local Rank?.

Также известен метод HITS (метод Клейнберга). Вводится гипотеза, что документы делятся на авторитетные источники и узлы, которые содержат ссылки на эти источники. Имея начальный список «хороших» источников можно назвать хорошими те узлы, которые на них ссылаются, получить новые источники по ссылкам данных узлов и так далее.

Описание итерационного алгоритма.
1. Пусть N – множество документов коллекции, отобранных запросом, о каждом из которых известны другие документы коллекции, на которые они ссылаются.
2. Для каждого документа n из N заполняем массивы H(n) оценок документа-узла и A[n] – оценка документа-источника. Массив H(n) инициализируем 1.
3. Далее проводим операции в цикле, пока массивы A[n] и H[n] не перестанут изменяться с заданной точностью
4. Для каждого из документов вычислить A[n] как сумму H[k], где k – каждый из документов, ссылающихся на данный.
5. Для каждого из документов вычислить H[n] как сумму A[k], где k – каждый из документов, ссылающихся на данный.
6. Нормализуются значения H[n] и A[k] на множестве документов.

Документы, получившие наибольший вес H[n] и A[n] получают больший вес в результатах поиска.