Оптимизация расчета ссылочной популярности и учета ее при ранжировании результатов поиска |
АннотацияПроблема поисковых алгоритмов, учитывающих наличие внешних ссылок на документ или сайт, состоит в возможности искусственного увеличения ссылочной популярности путем обмена ссылками, участия в ссылочных фермах. Для решения проблемы накруток обычно используют индивидуальные меры: исключение сайтов и ферм из индекса, наложение фильтров на исходящие ссылки и т.п., что требует участия человека-модератора. Кроме того, масса промежуточных случаев (тематические кольца, обмен ссылками в узких темах), могут быть ошибочно отнесены в категорию накрутчиков. В работе предложена идея по разделению индекса ссылочной популярности (PageRank, SiteRank) на независимые части, соответствующие «добровольной» и «обменной» цитируемости с тем, чтобы в алгоритме ранжирования учитывать их с разными весами. Предложенный подход позволяет количественно и алгоритмически определять степень вовлеченности в системы ссылочной накрутки. ВведениеАлгоритмы поисковых систем по ранжированию веб-документов, учитывающие наличие ссылок на других документах, подвержены внешним влияниям. Влияние на результаты ранжирования со стороны владельцев сайтов может осуществляться с помощью обмена ссылками с другими сайтами, участия в ссылочных фермах, создания ссылок на свои сайты в гостевых книгах, каталогах, форумах, создания сети поддерживающих основной сайт ресурсов, обменивающихся ссылками и ссылающимися на основной сайт. Для решения проблемы накрутки ссылочной популярности обычно используют такие меры, как: исключения сайтов из индекса, наложение фильтра на исходящие ссылки с сайтов. Однако, эти действия требуют ручной проверки ссылочных ферм и отдельных сайтов. Кроме того, ссылочная накрутка может остаться незамеченной при следующих условиях:
Кроме того, ошибки человека-модератора могут возникать в случаях, если:
В общем случае, почти любой обмен ссылками предполагает договоренность между ссылающимися сайтами. Следовательно, ценность таких ссылок в алгоритме ранжирования должна быть более низкой, нежели ценность «добровольных», односторонних ссылок. В условиях, когда около 27% всех ссылок в русскоязычном Интернете (по данным Яндекса) являются обменными (т.е., в обмен вовлечено около 14% хостов) невозможно просто исключить взаимные ссылки из рассмотрения. Кроме того, обмен ссылками, даже и договорной, не всегда является накруткой – многие владельцы сайтов обмениваются ссылками с действительно качественными ресурсами в своей тематике и не заслуживают штрафных санкций. При учете ссылочной популярности отдельных документов (хостов) часто в виде ее количественной меры используют взвешенную цитируемость, или PageRank. Алгоритм расчета PageRank документа предполагает учет цитируемости ссылающихся на него документов. Однако в алгоритме PageRank смешиваются все виды ссылок – односторонние и взаимные. Отсюда возникают следующие возможности для накрутки ссылочной популярности путем создания ссылочных ферм и массового обмена ссылками. Невозможность разделить разные компоненты PageRank ведет к необходимости принятия резких мер – сайт либо полностью принимается поисковой системой, либо полностью отвергается ей. Кроме того, в этой деятельности особую роль играет человеческий фактор. В данной работе предлагается метод количественной оценки цитируемости хостов (SiteRank), позволяющий разделить долю цитируемости, полученную путем специальных действий (обмена ссылками и т.п.) и долю цитируемости, полученную за счет добровольных односторонних ссылок. В дальнейшем эти ранги страниц можно использовать в алгоритмах ранжирования с разными весами при учете ссылочного ранжирования. Идея исследованияИдея исследования – в разделении общей системы ссылок между хостами в Интернете на 2 подсистемы, не связанные между собой ссылками. Первая подсистема состоит из только лишь обменных ссылок. Вторая подсистема состоит из всех остальных ссылок. Две подсистемы хостов могут пересекаться, т.е., один и тот же хост может находиться и в подсистеме «односторонних» ссылок (в ссылочную матрицу будут входить только односторонние ссылки) и в подсистеме «обменных» ссылок (в ссылочную матрицу будут входить только обменные ссылки). Это важный момент: это позволит не рассматривать хост либо как «только лишь накрученный» либо «абсолютно чистый». Гипотеза 1: «добровольные, односторонние» ссылки ставятся в случае действительно качественного контента сайта и его уместности в контексте ссылающегося сайта. Поэтому вероятность перехода по такой ссылке должна быть выше. «Взаимные, обменные» ссылки привлекают к себе меньше внимания посетителя в силу их расположения на сайте (в каталоге ссылок) и меньшей уместности в контексте ссылающегося сайта. Поэтому вероятность перехода посетителя по ссылкам разного типа должна быть разной, и, соответственно, при расчете pagerank нужно использовать разные значения dumping factor (d). Гипотеза 2 (следствие из 1): поскольку вероятность перехода по «добровольной» ссылке выше, чем по «обменной», должно происходить естественное «перекачивание» посетителей из подсистемы хостов с обменными ссылками в подсистему хостов с добровольными ссылками. Таким образом, вероятность посещения сайта из подсистемы «добровольных ссылок» должна быть выше, чем подсистемы «обменных ссылок». Гипотеза 3: даже при одинаковой вероятности перехода по обменной и добровольной ссылкам ценность второй для алгоритмов ранжирования выше, т.к. в первом случае выше вероятность того, что ссылки поставлены по предварительной договоренности. Отсюда следует целесообразность учета «добровольной» цитируемости в алгоритме ранжирования с более высоким весом. Методы, алгоритмы и экспериментыМетодыПоследовательность проведения исследования представлена ниже:
0. Использованные данныеИспользовался хост-граф номер 1. Данные по 4.9 млн. хостов, из которых около 500 тыс. известных Яндексу (скачанных), из которых около 250 тыс. имеют внешние ссылки на другие хосты (т.е., не являются «висящими»). 1. Уравнения расчета ранга SiteRankТ.к. данные были получены по ссылкам между хостами, рассчитывались значение не PageRank (по ссылкам между документами), а SiteRank (между хостами). При этом в уравнениях каждый хост представляет собой одну «страницу», на которой есть ссылки вовне и на которую есть ссылки извне. Для расчета использовалась система уравнений:
Где Физический смысл SiteRank в этой системе из N уравнений – число находящихся на хосте пользователей при условии, что всего в Интернете «ходят» N пользователей. Это позволяет легко сравнивать значения SiteRank для нескольких подсистем с разным числом сайтов в них. Расчет проводился с помощью итераций. Перед расчетом из матриц удалялись висящие страницы и ссылки на висящие страницы. Такая чистка матрицы проводилась несколько раз (до 6), т.к. после удаления ссылок на «висящие» хосты появлялись новые «висящие» хосты. Таким образом, при расчете не требуется использование нормировок. 2. Выбор значения
|