Методы ссылочного ранжирования в информационно-поисковых системах

Введение

Информационно-поисковые системы в сети Интернет - на данный момент являются одним из ее краеугольных камней. Необходимость в службах, предоставляющих возможность поиска информации в Интернет, появилась сразу же после возникновения сети и на данный момент, по соотношению качества поиска и количества обработанных источников информационно-поисковые системы не имеют аналогов. Примерами подобных систем могут служить Google, MSN, Yahoo, Яндекс, Рамблер, Апорт и многие другие.

Ссылочное ранжирование позволяет увеличить качество результатов поиска. Для этого, каждому ресурсу сети присваивается ранг, отражающий его важность. В той или иной форме методы ссылочного ранжирования используют все современные информационно-поисковые системы, например они используются при вычислении индексов Тиц в Яндексе и Коэффициента Популярности Рамблера. Однако ссылочное ранжирование имеет ряд недостатков, самым главным из которых является огромная трудоемкость. Она лавинообразно нарастает с увеличением числа ресурсов в сети и является сдерживающим фактором в индексации сети ИПС. К примеру, Google располагает данными о 8 миллиардах документах, и обновляет свой индекс PageRank раз в 3 месяца. Статистические исследования показывают, что число сайтов в Интернет растет экспоненциально, и за последний год их число удвоилось. Исходя из существующих прогнозов, актуальность проблем ссылочного ранжирования будет стремительно возрастать.

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

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

Глава 1. Информационно-поисковые системы

1.1 Основные сведения

<
>

Рис 1. Рост числа web-сайтов в русскоязычном сегменте.

Интернет не только увеличивается в размерах - постоянно изменяется и его структура. Если в начале 90-х содержимое сети представляло собой группу гипертекстовых документов, то сейчас это динамические мультимедийные ресурсы, зачастую использующие СУБД для хранения данных. Информация может изменяться или исчезнуть столь же быстро, как появилась. Появление новых технологий настолько преобразило сеть, что в прессе уже используют новый термин: WEB 2.0.

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

Первая ИПС WebCrawler появилась в 1994 г. В то время каталоги смогли ненадолго составить конкуренцию ИПС: размеры WWW и аудитория Интернет были относительно невелики и каталоги во многом удовлетворяли требованиям пользователей. С ростом числа документов в сети, ИПС столкнулись с проблемой релевантности результатов. Если раньше конкуренция среди ИПС сводилась к размерам индекса, то теперь индексация все большего числа ресурсов уже не гарантировала более качественный поиск. Среднестатистический пользовательский запрос состоит лишь из 2,7 слов, а удовлетворять такому запросу могут сотни тысяч страниц. Просмотреть их все пользователь попросту не может - он ограничится первыми 10-15 результатами. В связи с этим все большую важность приобретает не обнаружение всех релевантных документов, а оценка их качества, обработка и представление результатов поиска.

Современные ИПС не просто ищут удовлетворяющие запросу документы. Они ранжируют их, исходя из предположения системы о качестве и важности найденного результата. С развитием ИПС все больше становятся индексы, и все больше факторов играет роль при ранжировании результатов поиска. Учитываются не только частота употребления слов запроса в документе, но и их расположение относительно друг друга, расположение внутри документа, их выделение в тексте (шрифт, гарнитура), соответствие документа тематике запроса и многое другое.

Настоящим прорывом в обеспечении наилучшего качества поиска стала ИПС Google основанная в 1998 г. Сергеем Брином и Ларри Пейджем. Превосходство Google над ближайшими конкурентами основывалось на использовании при ранжировании алгоритма PageRank. Этот алгоритм ставит в соответствие каждому проиндексированному документу сети ранг его важности (PR), основываясь на ранге ссылающихся на него документов. Ранжирование результатов поиска с учетом PR документов позволило обнаруживать и отображать в первую очередь документы-первоисточники и наиболее “авторитетные” ресурсы сети. В свою очередь, более качественный поиск сделал ИПС Google поисковым сервисом №1 в мире. На сегодняшний день Google предлагает своим пользователям более 50 разнообразных сервисов, а ее чистая прибыль на конец 2006 года превысила 3 миллиарда долларов.

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

1.2. Структура и механизм работы информационно-поисковых систем

Согласно БСЭ: “Информационно-поисковая система - это совокупность информационно-поискового языка, правил перевода с естественного языка на информационно-поисковый и обратного перевода, а также критерия соответствия, предназначенная для осуществления информационного поиска”. Сразу оговорюсь, что в данной работе рассматривается куда более узкий класс ИПС, предназначенный для поиска информации на web ресурсах компьютерных сетей. Подобные системы появились относительно недавно (порядка 10 лет) и терминология еще не устоялась. Во всех зарубежных источниках используется термин “search engines”, что дословно можно перевести как “поисковая машина” или “поисковый двигатель”. В российской прессе часто используется “поисковый движок” или попросту “поисковик”. В то же время, и Яндекс и Рамблер всегда именовали себя “поисковыми системами”, что является еще более широким понятием.

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

Поиск информации в сети осуществляется с помощью поискового робота (web crawler), в составе которого выделяют две подпрограммы: паук (spider) и червяк (crawler). Первая осуществляет загрузку данных с информационного ресурса, а вторая ищет в них ссылки на другие ресурсы, добавляя их в список целей паука. Подобным образом поисковый робот движется от ресурса к ресурсу сети. Чаще всего ИПС используют сразу несколько параллельно исследующих сеть поисковых роботов, распределяя нагрузку между ними.

Стоит отметить, что далеко не все данные могут быть обнаружены ИПС. Существует проблема т.н. глубокой (скрытой или невидимой) паутиной (deep/hidden/invisible web). Информация, предоставляемая ресурсами сети, может храниться в базах данных и извлекаться из нее динамически, по запросу пользователя. К тому же, часть ресурсов не предоставляют свободного доступа, требуя аутентификации клиента. И, наконец, многие ресурсы могут быть недоступны или неработоспособны в момент их посещения поисковым роботом. По различным оценкам “невидимая” часть Интернет превосходит исследованную пауками от 10 до 500 раз [2].

Скаченная информация передается программе-индексатору, в задачу которой входит разбор и классификация этих данных. Например, в гипертекстовых страницах определяются заголовок документа и текст, выделенный размером или гарнитурой шрифта, выявляется тема документа и его ключевые слова, производится автореферирование. Процесс обработки информации индексатором и называют индексацией данных ресурса. Современные поисковые системы могут также индексировать документы в форматах pdf, ps, djvu. Предпринимаются попытки индексации графических файлов, а также аудио и видео данных (вещание TV и радио в сети).

Проиндексированные данные заносятся в индекс ИПС - специализированную базу данных. Индекс может достигать огромных размеров и проектируется с учетом повышенной отказоустойчивости, обеспечивать высокую скорость поиска и извлечения данных, а также возможность их распределенного хранения и параллельной обработки. Индекс - одна из самых сложных функциональных частей ИПС и во многом от него зависит производительность всей системы [6].

Ввиду особой важности правильности проектирования индекса ИПС, мы рассмотрим структуру индекса более подробно на примере Google. На данный момент, это - самый большой индекс, он хранит данные о более чем 8-ми миллиардов документов. Все данные размещены в виртуальной распределенной файловой системе GFS - Google File System (до 2003г. использовалась BigFiles). GFS предназначена для работы с файлами большого размера, и хранит информацию в блоках (chunk) по 64Мб. Все блоки маркируется 64-х битными идентификаторами. GFS содержит в себе кластеры, в каждом из которых выделяется главный сервер (master) и хранилища (chunkservers). Хранилища являются рабочими станциями под управлением Linux, а блоки GFS хранятся на них как обычные файлы. Главный сервер играет роль таблицы размещения файловой системы - он содержит метаданные, позволяющие найти идентификаторы блоков запрашиваемого файла и определить хранилища, в которых они находятся. Кроме того, он проверяет работоспособность хранилищ данных. GFS содержит как минимум 3 копии каждого файла в различных хранилищах, и в случае отказа одного из них, главный сервер кластера должен переадресовать запрос другому. Чтобы не допустить превращение главного сервера в “бутылочное горлышко” системы, Google использует порядка 50 кластеров, в каждом из которых находятся сотни хранилищ [16].

Для выполнения распределенных вычислений Google была разработана программа Workqueue, объединяющая множество серверов в одну вычислительную систему. Она предназначена для планирования задач, выделения аппаратных ресурсов, сбора статистики и результатов. Workqueue устанавливается на те же сервера, что используются в GFS, так как их вычислительные ресурсы в основном простаивают. Для упрощения программирования распределенных вычислений над огромными (порядка 100 терабайт) массивами данных в кластерах GFS была создана платформа MapReduce framefork. MapReduce - это библиотека, скрывающая от программиста процесс распределения задач между серверами кластера (map) и сбора воедино результатов их работы (reduce). Она контролирует обработку ошибок и отказоустойчивость вычислений, а также заботиться о том, чтобы сервера по возможности выполняли операции с данными, которые физически расположены на них [9], [24]. Также в Google создан реализующий концепцию MapReduce язык Sawzall, позволяющий максимально упростить программирование параллельных вычислений [24], [30].

Все вышеперечисленное позволило Google спроектировать единую распределенную систему хранения и управления структурированными данными Bigteable. Эту систему используют более 60 продуктов и проектов Google. В документации Google ее никогда не называют базой данной, хотя Bigteable и выполняет схожие функции. Дело в том, что Bigteable не поддерживает реляционную модель данных. Принято считать, что Bigteable представляет собой распределенный упорядоченный многомерный массив. По сути - это таблица, заголовки строк и столбцов которой - произвольные строки, а каждая ячейка измеряется еще и по времени (timestamp). Все данные в этой таблицы - никак не интерпретируемые наборы байт.

Примечательно, что Bigteable оптимизирована для считывания данных из столбцов, а не из строк [8].

<
>

Рис 2. Структура ИПС Google.

Все вышеперечисленное касалось технического аспекта реализации хранения и обработки индекса, теперь рассмотрим подробнее его содержимое.

Как только документ передается программе-индексатору, она предпринимает попытку определить, был ли он уже проиндексирован. Индексатор ищет в базе не точную копию обрабатываемого документа, а наиболее похожий по содержанию образец. Это позволяет избежать двойного индексирования одного и того же документа, взятого из различных источников, или представленного в другом формате (например, html и pdf). Если документ системе не известен или претерпел изменения, то индексатор предпринимает следующие шаги:

1. Документу присваивается идентификатор.

2. В документе выделяются все слова, отфильтровываются не имеющие смысловой нагрузки (предлоги, союзы и т.п.), а затем определяются лексемы.

3. Данные о соответствии документа содержащимся в нем лексемам заносятся в базу индекса.

В индекс могут помещаться сведения о частоте использования термина в документе, его расположение в тексте, были ли применены к слову средства выделения (шрифт, цвет и т.п.). Также могут присутствовать т.н. “координатные данные” данных: позволяющие быстро найти первые n вхождений лексемы в документе (это позволяет быстро сравнить насколько “близко” в документе несколько различных лексем, не обрабатывая его текст).

Различают прямой и обратный индекс (inverted index). В прямом индексе записи отсортированы по документам, в обратном - по словам [1].

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

Большинство поисковых запросов пользователей ИПС содержат не более 3-5 слов, и число релевантных им документов измеряется десятками тысяч. Естественно, пользователю предоставляются ссылки лишь на первые 10-15 самых “лучших” результатов. Для этого ИПС определяет не только релевантность документа запросу, но и его “качество” или “авторитетность”. Всем проиндексированным ИПС документам ставится в соответствие рейтинг - некая числовая характеристика. В Google она носит название PageRank, в Яндексе - ТИЦ, в Рамблере - Коэффициент популярности. При вычислении рейтинга документа могут использоваться множество факторов, например наличие регистрации ресурса в различных каталогах (таких как DMOZ), но главным является суммарный ранг ссылающихся на него документов.

Документы и их связи удобно представить в виде сети, получившей название web-граф. Эта сеть строится ИПС на основе данных индекса. Ссылочное ранжирование - механизм, ставящий в соответствие каждой вершине web-графа ранг, в зависимости от ранга ссылающихся на нее вершин. Во всех моделях ссылочного ранжирования, документ получает от ссылающегося на него документа лишь часть ранга, в зависимости от числа содержащихся в нем ссылок. Это позволяет проводить более “честное” ранжирование и избежать неоправданного возрастания ранга информационного ресурса за счет его регистрации в каталогах.

При индексации нового документа поисковым роботом, к web-графу должна быть добавлена новая вершина. В результате, возрастает общее число исходящих дуг в ссылающихся неё вершинах, и уменьшается доля ранга, которую они могут передать другим документам. Таким образом, добавление или удаление документа может оказать влияние на ранг даже непосредственно не связанных с ним документов. На результаты ранжирования может повлиять любое изменение структуры web-графа, например - изменение количества ссылок в одном из документов.

Необходимость пересчета ранга большого числа вершин при незначительных изменениях делает невозможным вычисление ранга нового ресурса непосредственно в момент его индексации. В связи с этим ИПС ранжируют документы индекса через значительные промежутки времени, например в Google процесс обновления PageRank в базе получил название “Google Dance” и происходит раз в 3 месяца.

Из этого следует ряд недостатков ссылочного ранжирования:

Во-первых - возможность злонамеренного завышения ранга документа владельцем информационного ресурса. Попадание в первую десятку или двадцатку результатов поиска имеет большую значимость в электронной коммерции. Поэтому владельцы Интернет-магазинов и им подобных ресурсов, а также администраторы, предоставляющие услуги по размещению рекламы на своем сайте, часто прибегают к недобросовестной конкуренции, “накручивая” свой рейтинг с помощью грамотной расстановки ссылок и наполнения документа “ключевыми” словами. Для этих целей были разработаны такие механизмы как:

• Дорвеи (doorway) - генерация множества страниц с определенным образом подобранным наполнением и структурой гиперссылок, ссылающихся на ресурс.

• Сервисы обмена ссылками (например, WebRing). С их помощью владелец сайта может обменяться ссылками с документом, имеющим высокий ранг, или даже купить такую ссылку.

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

• Клоакинг (cloacking) - определение по IP адресу поискового робота и предоставление ему заранее подготовленного документа, отличного от оригинала.

• Флуд (flood) - замусоривание веток форумов сообщениями рекламного характера, содержащего ссылки на ресурс. Для этих целей применяются специальные скрипты. Страницы форумов существуют достаточно долго и могут содержать потенциально интересную информацию, поэтому часть из них индексируются поисковым роботом и рассматриваются как обычный документ.

В настоящий момент существует множество организаций, предоставляющих услуги по “раскрутке” сайтов с помощью как вполне законных так и не совсем легальных средств. Это направление деятельности было названо поисковой оптимизацией (search optimization).

Многие ИПС относятся к поисковой оптимизации крайне отрицательно: недобросовестная конкуренция среди информационных ресурсов снижает качество поиска, к тому же, владельцы ИПС теряют часть прибыли - деньги, потраченные на оптимизацию, могли бы достаться принадлежащим им рекламным службам. Для борьбы с этим явлением применяются алгоритмы выявления вышеназванных способов накрутки рейтинга. Существуют также т.н. “черные списки” в которые заносятся ресурсы, уличенные в поисковой оптимизации. ИПС могут занижать ранг принадлежащих им документов или совсем исключить их из результатов поиска.

Вторым и наиболее весомым недостатком ссылочного ранжирования является высокая трудоемкость. Нельзя рассчитать точный ранг вершины web-графа, рассматривая лишь некоторый содержащий ее подграф - нельзя гарантировать, что в этом множестве содержаться все документы, оказывающие существенное влияние на результаты ранжирования вершин подграфа.

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

2.1. Web-граф

Web-граф - связный орграф, вершинами которого являются документы (в основном статические html страницы) информационных ресурсов сети, а дугами - гипертекстовые ссылки между ними.

Еще в 1999г. R. Kumar [23] и независимо A.L. Barabasi и A. Albert [3] обнаружили, что число входящих в вершину дуг имеет экспоненциальное распределение с коэффициентом 2,1. Также ими было выдвинуто предположение о том, что число исходящих дуг имеет экспоненциальное распределение с коэффициентом 2,7. Следует отметить, что последнее утверждение не находит подтверждение в работах других исследователей.

В том же году было выявлено еще одно удивительное свойство web-графа. На макроскопическом уровне он имеет структуру “бабочки” [7]. Ее центром является группа страниц, образующих компонент сильной связности (SCC). Также имеются страницы, ссылающиеся на центральную группу (IN), страницы на которые ссылается центральная группа (OUT), множество несвязных с ними страниц, а также “трубы” - ссылки между “крыльями” бабочки. В web-графе размером 200 млн. страниц, предоставленным компанией Alexa в 1997г. было обнаружено свыше 100000 подобных сообществ.

Вероятность существования пути между двумя случайно выбранными вершинами этого web-графа составила 24%, а средняя длина такого пути равна 16.

<
>

Рис 3. Структура “бабочки”.

J. Kleinberg и D. Watts [31], [21] рассмотрели неориентированный web-граф и подтвердили наличие в нем феномена “Малого мира” (Small world phenomen), типичного для динамических социальных сетей. За исключением небольшого процента дуг, почти все вершины такого графа достижимы из любой другой через огромный центральный компонент связности, составляющий около 90% web-графа. В структуре web-графа также было выделено удивительно большое число специфических топологических структур, таких как двудольные клики небольшого размера (3-10 вершин). Это связывают с наличием неявных кибер-сообществ: групп ресурсов сходной тематики, имеющих общие “авторитетные” страницы. Двудольные клики интерпретируются как ядро подобных сообществ - они состоят из множества “фанатских” и “авторитетных” страниц, причем все страницы из первого множества ссылаются на страницы второго.

В виду особой практической важности PageRank и ему подобных алгоритмов G. Pandurangan, P. Raghavan, и E. Upfal проанализировали результаты ранжирования web-графа [28]. Их исследование показало, что распределение PageRank, также как и число ссылающихся страниц, подчиняется экспоненциальному закону с коэффициентом 2.1, но корреляция между этими параметрами очень невелика, а значит, страница с большим количеством входящих ссылок может получить очень низкий ранг.

В 2002г. D.M. Pennock, G.W. Flake и др. [29] установили, что такие группы страниц, как домашние сайты студентов университета, или все страницы сайтов новостей, испытывают значительные отклонения от экспоненциального закона в различной степени.

S. Dill в своей работе [10] исследовал различные фрактальные свойства web-графа. Изучая различные связанные группы страниц (напр. страницы, принадлежащие одному сайту, или страницы общей тематики), было обнаружено подобие их структуры структуре всего графа. Центральная часть структуры этих коллекций была названа “Тематически Объединенным Кластером” (Thematically Unified Cluster" (TUC)).

<
>

Рис 4. Фрактальные свойства web-графа.

2.2. Модели ссылочного ранжирования

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

Одной из самых знаменитых стала модель вычисления ранга алгоритма PageRank, предложенного С. Брином и Л. Пейджем в 1997г [27]. В этой модели ранг вершины равен вероятности его нахождения бродящим случайным образом по сети пользователем. Эта вероятность складывается из некоей минимальной вероятности и из суммы вероятностей перехода на него пользователя с ссылающегося документа помноженной на некоторый коэффициент затухания.

Пусть связный орграф <
- web-граф на множестве вершин
и дуг
.
- множество ссылающихся на
вершин.
- число исходящих из вершины
дуг. В этом случае PageRank в вершине
вычисляется по формуле:>

<
(2.2.1)>

Где <
- (dumping factor) т.н. фактор затухания, отражающий вероятность перехода пользователя по ссылке на следующий документ. В этом случае
- вероятность случайного просмотра документа пользователем.>

PageRank уже 10 лет используется в ИПС Google. Индекс ТиЦ Яндекса также основан на этой модели “с точностью до реализации”.

Модель HITS использовалась в проекте ИПС Clever фирмы IBM. Согласно этой модели все страницы делятся на источники (“autority”) и хабы (“hubs”). [20]. Источники являются наиболее популярными ресурсами данной тематики, а хабы - ресурсы ссылающиеся на множество источников. Всем источникам присваивается начальный ранг <
, а каждому хабу - ранг
. Согласно модели, ранг источника равен сумме рангов ссылающихся на него хабов, а ранг хаба - сумме рангов ссылающихся на него источников. Ранжирование с помощью алгоритма HITS является итерационным процессом, на каждой итерации которого выполняются 3 фазы:>

1. Вычисление рангов всех источников.

2. Вычисление рангов всех хабов.

3. Нормирование рангов для выполнения условия: <
   .>

В отличие от PageRank, ранжирование с помощью HITS применяется в момент выполнения поискового запроса на небольшом (до 5000) подграфе. В работе [11] было показано, что модель HITS является плохо обусловленной. Ее развитием стала модель SALSA, объединившие идеи HITS и PageRank [25].

Модель HillTop (в некоторых источниках - LocalScore) предложена в 2000г. Krishna Bharat и George A. Mihaila [5]. В настоящее время патент на нее принадлежит Google. HillTop получил широкую известность в ноябре 2003 года, когда Google внес значительные изменения в систему ранжирования. Это масштабное обновление получило название “Florida” и вызвало сильное беспокойство поисковых оптимизаторов и владельцев ресурсов: некоторые результаты поиска не включали сайты с более высоким PageRank. Было выдвинуто предположение, что часть запросов дополнительно ранжируется при помощи HillTop. Google не подтвердил, но и не опроверг это мнение.

В отличии от PageRank, определяющим абсолютный ранг документа, HillTop вычисляет ранг относительно поискового запроса. Работа алгоритма HillTop предполагает следующие этапы:

Этап 1. Предобработка web-графа. Выделение экспертных документов.

Этап 2. Определение релевантных запросу экспертных документов. Присвоение им ранга в зависимости от количества содержащихся в документе ключевых слов запроса и их местонахождения.

Для каждого экспертного документа вычисляется кортеж из трех чисел <
. Пусть
- число лексем в поисковом запросе
. Тогда
, где
- ключевая фраза, содержащая
терминов.
- функция от местонахождения фразы (возвращает 16 для заголовка документа, 6 для названия главы документа и 1 для текста ссылки).
- мера покрытия лексем запроса
лексемами запроса
. Функция определяется следующим образом: пусть
- число лексем в
,
- число лексем в
,
. Тогда
. Ранг экспертного документа вычисляется как
.>

Этап 3. Вычисляется ранг документов, на которые ссылаются экспертные документы. Для этого в экспертном документе выделяются релевантные запросу ссылки. Считается, что ключевая фраза характеризует дугу <
в следующих случаях:>

1. Фраза содержится в заголовке документа <
   >

2. Фраза содержится в названии главы документа <
   , а ссылка, соответствующая дуге
   содержится в этой главе.>

3. Фраза содержится в тексте этой ссылки.

Каждой характеризуемой ссылке присваивается вес, вычисляемый следующим образом: Пусть <
- число различных ключевых фраз в экспертном документе
, содержащих лексему
. Тогда вес ссылки вычисляется по формуле:
.>

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

Вычисление ранга с помощью модели <
еще более трудоемко, и требует существования как минимум двух релевантных запросу экспертных документов. >

Модель BackRank как и PageRank использует в качестве ранга вершины вероятность попадания на нее пользователем, но при этом учитывает использование кнопки Back браузера [26]. Существует 2 разновидности модели: обратимая и необратимая. В первой, после перемещения с помощью кнопки Back покинутая страница помещается в историю. Поэтому повторное перемещение фактически отменяет первое, в “истории” хранится всего одна страница, а возврат к предыдущей страницу возможен всегда (кнопка Back всегда активна). В необратимой модели возвращение лишь удаляет верхнюю запись в истории, число записей в истории равно <
, и
полагают равной 1. Утверждается, что необратимая модель считается более простой в расчетах и сходится быстрее PageRank. Рассмотрим ее подробнее:>

Пусть <
- вероятность попадание в вершину
по ссылке из вершины
в момент
.
- вероятность попадания в вершину v с помощью кнопки Back браузера. Тогда
,
>

Заметим, что <
не зависит от
. В этом случае расчетные формулы принимают вид:>

<
,
>

Введя в модель параметр затухания (dumping factor), получим:

<
,
>

Таким образом:

<
>

Аналогично методу Зейделя, вместо <
можно положить
.>

Утверждается, что данная модель сходится быстрее PageRank, но я не располагаю сведениями об использовании идей BackRank какой либо ИПС, хотя вполне можно допустить, что разработчики просто не афишируют ее применение.

2.3. Постановка задачи

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

<
(2.3.1)>

<
(2.3.2)>

В этом случае, стационарное распределение вероятностей <
будет содержать искомые ранги страниц. >

Неотрицательную матрицу <
можно рассматривать как матрицу переходов в Марковской цепи. Для этого она должна быть построчно стохастической, но это условие не выполняется для “висящих” вершин (вершин, не имеющих ни одной исходящей ссылки) - в соответствующих им строках содержаться только нули.>

Есть множество способов устранить это препятствие. Во-первых, висящие вершины можно удалить (так как они не влияют на ранг других вершин) и вернуть на последних итерациях вычисления ранга. Во-вторых, можно создать в каждой висящей вершине петлю или добавить к графу одну псевдо-вершину, на которую они будут ссылаться. Но чаще используется следующий прием: для каждой висящей вершины задаются искусственные дуги, соединяющие их со всеми вершинами графа. Пусть <
, тогда матрица
примет вид:
, где вектор
содержит
элементов
[4]. Стационарным распределением в этом случае будет вектор, удовлетворяющий:
>

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

<
(2.3.3)>

<
(2.3.4)>

Где <
- константа,
- единичная матрица. Вектор
для модели PageRank является единичным, и называются “вектором телепортации”. Если
не является единичным, его часто называют “вектором персонализации”. Установлено, что для матрицы

[14]. Величина
является вероятностью перехода случайно бродящего по сети пользователя по ссылке, а
- вероятностью перехода пользователя на любую страницу web-графа.>

Значение <
выбирается в диапазоне от 0,85 до 0,99 (на практике до 0,9) [6, 14]. Число итераций, необходимых для ранжирования web-графа с помощью степенного метода равно
, где
- точность ранжирования [4].>

Для модели PageRank и ряда других линейных моделей задача ссылочного ранжирования может быть переформулирована в виде СЛАУ:

<
(2.3.5)>

<
(2.3.6)>

Для матрицы <
выполняются условия диагонального преобладания и обратимости [12] . Она также является хорошо обусловленной [19]. Это позволяет применять прямые и итерационные методы решения СЛАУ.>

2.4. Методы ссылочного ранжирования

Итерационный процесс, описанный формулой (2.3.2), является степенным методом вычисления собственного значения матрицы <
. Для итерационного процесса (2.3.4) степенной метод сходится к главному собственному вектору матрицы
с собственным значением
независимо от начального значения вектора
.>

Для увеличения сходимости степенного метода может быть применена экстраполяция. В работе [18] подробно рассмотрены различные виды экстраполяции, в том числе экстраполяция Эйткена (Aitken) и квадратичная экстраполяции. Экспериментально было подтверждено увеличение сходимости при помощи квадратичной экстраполяции на 59%. Методы экстраполяции, описанные в [13], позволяют ускорить степенной метод на 30%.

Еще одним приемом, позволяющим увеличить быстродействие степенного метода, является адаптивный метод [17], позволяющий не пересчитывать ранги вершин, для которых итерационный процесс уже сошелся. Пусть степенной метод на <
-той итерации (2.3.4) не сошелся для
вершин. Тогда матрица
может быть разложена на подматрицу
размерности
, соответствующую вершинам в которых процесс не сошелся, и подматрицу
размерности
, соответствующую вершинам в которых процесс сошелся. Аналогично, вектор
раскладывается на вектора
и
. В этом случае, вычисление
будет представлять собой следующее:
. Так, как для вершин, соответствующих
и
степенной метод уже сошелся, то вычисление
может быть упрощено:
. Этот метод применим только для относительно небольших графов.>

Для решения задачи (2.3.6) наиболее часто применяются итерационные методы. Метод Якоби на практике почти не применяется - вместо него предпочитают использовать метод Зейделя, сходящийся почти на 40% [4] быстрее.

Кроме того, для увеличения сходимости также могут быть применены методы верхней релаксации и симметричной верхней релаксации [32], но они требуют выбора подходящего параметра <
, способы определения которого для web-графа не ясны [4].>

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

Глава 3. Увеличение сходимости на основе метода релаксации

Рассмотрим одну из вершин графа. Пусть <
- ранг в вершине
на
-той итерации. Web-граф содержит большое число контуров, в результате чего ранг вершины на
-той итерации отчасти определяется рангом этой же вершины на предыдущей итерации.>

Значение, принимаемое <
, можно представить в виде:>

<
(3.1)>

где <
- ранг вершины на предыдущей итерации,
- коэффициент влияния и
- доля ранга, получаемая из других вершин, в том случае, если бы из web-графа были удалены все содержащие вершину
контуры. Ранг вершины, не содержащейся ни в одном из контуров графа, полностью определяется рангами других вершин графа. Если бы web-граф не содержал контуров, его вершины можно было бы подвергнуть топологической сортировке и рассчитать их ранги за один проход.>

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

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

<

Рис 5. Вычисление коэффициента влияния в контуре.

Последовательность вершин и дуг <
образует контур.>

Пусть ранг каждой вершины вычисляется с помощью модели PageRank, т.е.:

<
(3.2)>

В этом случае ранг второй вершины на <
-той итерации будет содержать часть ранга первой вершины:
. Ранг третьей вершины будет содержать
. Ранг четвертой вершины:
. И, наконец, вернется в первую вершину:
. Таким образом:
.>

Коэффициент влияния вершины <
в контуре
для модели PageRank может быть найден следующим образом:>

<
(3.3)>

<
(3.4)>

Заметим, что <
не зависит от номера итерации.>

Т.к. метод сходится, то, начиная с некоторой итерации <
:
(3.5)>

С другой стороны <
, следовательно, для сходимости необходимо выполнение условия:
или
. Таким образом, зная коэффициент влияния, мы можем на каждой итерации
вычислить
.>

1. Результаты численного эксперимента

Для экспериментальной оценки эффективности вышеизложенного метода, результаты его работы сравнивались с результатами метода Зейделя. Оба метода были реализованы на языке C++. Экспериментальными данными служили графы различной размерности, сгенерированные согласно копирующей модели web-графа [22]. Результаты тестирования приведены в таблице 1. В качестве модели ссылочного ранжирования была использована модель PageRank.

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

Заметим, что в модели PageRank коэффициент влияния для всех принадлежащих контуру вершин одинаков: <
.>

Для вычисления коэффициента влияния был применен следующий метод:

Шаг 1. Все вершины графа помечаются как не просмотренные.

Шаг 2. Выбирается еще не просмотренная вершина.

Шаг 3. С помощью поиска в глубину ищется содержащий выбранную вершину контур, длиной не превосходящий заданный параметр и не содержащий ни одной уже просмотренной вершины. Как только контур обнаружен, по формуле (3.3) вычисляется коэффициент влияния вершины в контуре. Найденный коэффициент прибавляется к коэффициентам влияния всех содержащихся в контуре вершин. Шаг 3 выполняется до тех пор, пока не обнаружены все отвечающие заданным требованиям контуры. Если ни одного контура не осталось, то выбранная вершина помечается как просмотренная и алгоритм переходит к Шагу 2.

Таблица 1. Эффективность метода ранжирования на основе релаксации.

Заключение

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

1. Т. к. коэффициент затухания < 1, то с ростом числа вершин в контуре коэффициент влияния стремительно убывает. Поэтому на практике достаточно ограничится рассмотрением контуров малой длины.

2. Коэффициент влияния зависит только от структуры графа (учитывая первый пункт - небольшого подграфа). Поэтому, в отличие от ранга вершины, коэффициент влияния может вычисляться непосредственно в момент внесения изменений в web-граф. В этом случае, отпадает необходимость в дополнительных вычислениях перед ранжированием - достаточно поддерживать актуальность коэффициентов влияния.

3. Возможно использование уже вычисленного коэффициента влияния контура для расчета коэффициентов влияния содержащих его контуров.

4. Существуют алгоритмы поиска всех контуров заданной длины, допускающие простую параллельную реализацию [15].

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

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

Библиография