Работаем с 2009 года Более 450 успешных проектов Санкт-Петербург
8 (999) 849-91-09

Построение достоверного веб-графа с учетом данных о пользовательском поведении

Аннотация

Оценка качества интернет-страниц является одной из самых значимых проблем систем информационного поиска. Для ее решения, как правило, используются такие алгоритмы гиперссылочного анализа, как Google PageRank и TrustRank. Однако, низкосортная, ненадежная, а в некоторых случаях откровенно некачественная информация, содержащаяся в гиперссылочном графе, существенно затрудняет эффективную оценку качества цифровых документов. Анализируя массивные логи пользовательского поведения при просмотре интернет-страниц мы обнаружили, что с учетом вышеуказанной информации может быть смоделирован более достоверный веб-граф. Результаты экспериментов показывают, что сконструированный с использованием предлагаемых методов веб-граф оказывается значительно меньшим по размеру, чем оригинальный веб-граф. Более того, алгоритмы, основывающиеся на модели «серфинга с предварительными знаниями» выдают более качественные оценочные результаты на подобного рода графах в задачах идентификации как высококачественных, так и спамовых документов. Гиперссылочные графы, созданные по данному методу оценивают качество веб-страничек более точно и с меньшими вычислительными затратами. Основные тезисы, освещённые в данной работе:

  1. Посредством учёта информации о пользовательском поведении при просмотре интернет-документов можно увеличить производительность алгоритмов, оценивающих качество результатов в коммерческих поисковых системах.
  2. Предлагаются три различные графоориентированные модели, комбинирующие гиперссылочную информацию и данные о пользовательском поведении.
  3. Отличия между созданными моделями и оригинальным веб-графом показывают, что первые обеспечивают нас более достоверной информацией и могут быть использованы в решении практических задач по оценке качества веб-документов.
  4. В задачах оценки качества, включение информации о пользовательском поведении оказывается более значительным фактором, нежели применение любого из алгоритмов ссылочного анализа.

1. Введение

Вследствие бурного роста веб-данных, управление и поиск информации становятся все более сложными. Для современных поисковых систем оценка качества документов играет важнейшую роль при сканировании, индексировании и в процессе ранжирования результатов в органической выдаче. По этой причине объективная оценка качества интернет-страниц рассматривается как одна из наиболее важных проблем систем информационного поиска [15]. В настоящее время присуждаемые оценки основываются на анализе гиперссылочной структуры веб-графа. Успех алгоритма глобального анализа Google PageRank [25], равно как и прочих ссылочных методологий, таких как алгоритма локального анализа HITS (Hyperlink-Induced Topic Search) [19] и алгоритма доверия TrustRank [11], первым показал интернет-общественности возможность запросо-независимой оценки качества документов. Эти ссылочные алгоритмы базируются на двух основных предположениях [8]: во-первых, если две страницы связаны гиперссылками, тогда автор ссылающегося документа рекомендует для прочтения процитированную им страничку, то есть мы допускаем рекомендательный характер вышеуказанной связи. Во-вторых, две страницы имеют тематическую схожесть, то есть мы с определенной долей вероятности допускаем их тематическую локальность. Все алгоритмы гиперссылочного анализа, которые используются как в коммерческих поисковых системах (например [5, 12, 21, 25]), так и в исследовательских работах (таких, как [11, 13, 14, 19, 20]), полагаются на эти два предположения. Однако они упускают структурные тонкости актуального веб-графа. Эти предположения и, следовательно, опирающиеся на них подходы сталкиваются с теми проблемами, которые присутствуют в среде Глобальной паутины на текущем этапе ее развития. Например, в Таблице 1 показано несколько топовых сайтов из китайского веб-корпуса, состоящего из более чем 130 миллионов страниц (июль 2008 года). Для того, чтобы определить объективность присужденных алгоритмом Google PageRank оценок, мы также собрали информацию по статистике их посещаемости согласно сервису Alexa.com .

Веб-сайт Оценка PageRank Оценка Alexa.com китайского трафика
hd315.gov.cn 2 1,655
qq.com 3 2
baidu.com 6 1
miibeian.gov.cn 7 179
sina.com.cn 9 3

Таблица 1. Высокоотранжированные по методологии Google PageRank интернет-сайты китайского гиперссылочного веб-графа

Данные таблицы демонстрируют нам, что несколько высокоранжируемых веб-сайтов, кроме их высокого PageRank, также имеют и значительное количество пользовательского трафика. Например, в соответствии с сервисом Alexa.com, такие сайты как baidu.com, qq.com и sina.com.cn являются наиболее частопосещаемыми ресурсами китайского интернета. В противоположность этому, несколько таких высокоранжируемых сайтов, как hd315.gov.cn и miibeian.gov.cn получают относительно небольшой трафик. В соответствии с [25] страницы с высоким показателем голосующей способности либо имеют частое цитирование из различных внешних источников, либо на них ссылаются другие документы с высоким значением PR. В каждом случае интернет-страница с высоким показателем Google PageRank должна быть высокопосещаемой постольку, поскольку PageRank можно рассматривать как «вероятность того, что случайный серфер посетит документ». В [25] трафик также рассматривался как одно из возможных приложений алгоритма PageRank. Тем не менее, последние высокоранжируемые сайты не получают столько пользовательского трафика, сколько им следует получать согласно их голосующей способности. Безусловно, показатель авторитетности сайта еще не обязательно должен коррелировать с высокой посещаемостью. Но с нашей точки зрения мы полагаем, что ресурсы miibeian.gov.cn и hd315.gov.cn не должны получать столь высокие показатели качества и ранжироваться выше, чем целый ряд других сайтов государственных учреждений, которые также имеют высокий авторитет в китайском интернете, но вместе с тем занимают более низкие позиции в отличие от этих двух ресурсов. Для того чтобы понять причину переоценки сайтов miibeian.gov.cn и hd315.gov.cn давайте рассмотрим их гиперссылочную структуру. Рисунок 1 показывает, что baidu.com (самая популярная поисковая система в Китае) ссылается на miibeian.gov.cn (главная страница Министерства промышленности и информационных технологий КНР)

Рисунок 1. Пример сайта (baidu.com), ссылающегося на Министерство промышленности и информационных технологий КНР (miibeian.gov.cn).

Как вы можете видеть, исходящий гиперлинк располагается в нижней части главной страницы поисковой системы, а ее анкорный текст содержит регистрационную информацию. Дело в том, что каждый веб-сайт в Китайской Народной Республике проходит регистрацию в Министерстве промышленности и информационных технологий (далее — МПИ), а его владелец обязан проставить на всех страницах ресурса регистрационную информацию. Поэтому практически все сайты в Китае имеют исходящий линк на веб-сайт МПИ; следовательно, высокое значение PageRank у miibeian.gov.cn обусловлено именно тем фактом, что ресурс имеет огромное число внешних входящих ссылок. Практически по схожим причинам интернет-сайт hd315.gov.cn имеет столь же высокий показатель Google PR — каждый коммерческий сайт в Китае обязан указывать на своих страницах регистрационные данные, которые содержат исходящий линк на hd315.gov.cn.

Исходя из приведенного выше примера, видно, что присуждаемая алгоритмом ссылочного анализа PageRank оценка качества интернет-ресурсов на практике оказывается разумной далеко не во всех случаях. Такие сайты, как МПИ имеют высокий авторитет только по той простой причине, что его цитирует практически вся внешняя среда, относящаяся к китайскому вебу. Впрочем, многие гиперссылки создаются как с целью указания правовой информации, так и по коммерческим или даже спамерским основаниям. В отличие от предположения, сделанного в [2], гиперлинки не следует рассматривать как равнозначно важные. На практике пользователи не ведут себя по образу и подобию «случайного серфера»; напротив, они проходят только по интересным для них самих ссылкам. Таким образом, те интернет-сайты, которые связаны ссылками, обычно получают высокое значение Google PageRank, хотя они этого совершенно не заслуживают по той простой причине, что пользователям они не интересны и последние по ним не следуют. Этот пример демонстрирует то, что алгоритмы анализа ссылок не всегда столь успешны в реальных условиях, как в разрабатываемых теоретических моделях, поскольку существуют гиперссылки на которые пользователи кликают крайне редко. Удаление такого рода линков из веб-графа представляется важным шагом в задачах построения более надежной системы, в которой ссылочные алгоритмы смогли бы работать с большей эффективностью. Для удаления «шума» из нашего ссылочного графа, мы анализируем информацию о поведении пользователей, собираемую посредством установленных тулбаров поисковых систем или плагинов для браузера. Поведение пользователей на странице веб-сайтов поможет нам выявить то, какие странички или ссылки являются частопосещаемыми, а какие — наоборот; тем самым, позволяя нам построить более достоверный веб-граф. Например, вопреки высокой цитируемости ресурса МПИ, лишь немногие пользователи пройдут по данным ссылкам, поскольку для подавляющего большинства людей регистрационная информация не представляет какого-либо интереса. Эти линки могут рассматриваться нами как «бессмысленные» или «недействительные», так как они не участвуют в процессе пользовательского веб-серфинга. Если мы создадим новый веб-граф без вышеописанных ссылок предложенная нами модель пользовательского поведения нисколько не пострадает, однако расчет значения Google PageRank будет выполнен с большей аккуратностью, поскольку большинство гиперссылок, ведущих на главную страницу МПИ теперь удалены. Число пользователей, посещающих тот или иной сайт, можно рассматривать как неявную обратную связь, по которой мы можем судить о значимости как интернет-документов, так и связывающих их ссылок. Однако, как вы наверное понимаете, построение столь достоверного графа с такого рода информацией представляется весьма трудоемкой задачей. Сохранение только тех узлов и вершин, которые были посещены по крайней мере единожды может рассматриваться как один из возможных вариантов. Некоторые исследователи, такие как Liu и др. [23] построили аналогичный веб-граф, названный «графом сёрфинга пользователя», а затем получили с его помощью более точные оценки качества интернет-страниц, чем при ссылочных расчетах на веб-графе оригинального исполнения. Несмотря на это, существуют и другие варианты построения веб-графа на основании данных пользовательских просмотров, которые отличны от предложенного в [25] способа. Поэтому сейчас мы переходим к тому вкладу, который привносит наша текущая работа:

  1. Создаётся новая модель веб-серфинга, учитывающая информацию о пользовательском поведении на веб-странице, и несколько отличная от широко популярной «модели случайного сёрфера», которая активно эксплуатировалась в предыдущих работах. Эта «модель серфинга с предварительными знаниями» включает в себя не только данные пользовательских просмотров, но и учитывает гиперссылочную информацию, что является для нас более точным моделированием процесса веб-серфинга.
  2. Для оценки качества новой «модели серфинга с предварительными знаниями» предлагаются два алгоритма (userPageRank и userTrustRank). Они учитывают предпочтения пользователя при прохождении по тем или иными ссылкам на странице и могут быть выполнены на графе пользовательских просмотров.
  3. Для графового моделирования предлагается ещё два отличных друг от друга алгоритма, которые, помимо того, что рассчитываются по графу пользовательских просмотров, комбинируют информацию о пользовательском поведении с данными актуальной гиперссылочной структуры. Мы изучаем особенности и эволюцию этих графов, а также сравниваем их с оригинальным веб-графом.

Оставшаяся часть материала построена следующим образом: в Разделе 2 дается обзор смежных с нашим исследованием работ по оценке качества документов и анализу пользовательского поведения при просмотре интернет-страниц. В Разделе 3 вводится «модель серфинга с предварительными знаниями» и дается описание алгоритмов, оценивающих качество документов в рамках этой модели. Раздел 4 представлены алгоритмы, позволяющие строить веб-граф как на базе поведенческих факторов, так и на основании данных гиперссылочной структуры. Раздел 5 описывает структуру и эволюцию веб-графов построенных с помощью предложенных нами алгоритмов. В Разделе 6 сообщаются результаты наших экспериментов по применению алгоритмов оценки качества интернет-страниц на разных графах. Наконец, в Разделе 7 мы подводим итоги, а также даем направления для будущих работ.

2. Смежные работы

2.1 Оценка качества страниц

Подавляющее большинство предыдущих работ по оценке качества цифровых документов в основном фокусируется на использовании ссылочного веб-графа и строят на нем все свои модели. По причине оглушительного успеха алгоритма глобального ссылочного анализа Google PageRank в конце 90-х годов, последующие исследования в основном пытались улучшить результативность и эффективность оригинальной парадигмы [12, 13, 14]. Однако основополагающая идея оставалась неизменной: качество интернет-странички оценивалось посредством вероятностных оценок выхода на нее случайного серфера в принятой модели случайного блуждания. Алгоритм локального ссылочного анализа HITS оценивает качество веб-документа с использованием двух отличных метрик, а именно оценку авторитетности (authority score) и посредническую оценку (hub score). Экспериментальные результаты, основывающиеся на оценках поисковой системы IBM CLEVER и на экспертных аннотациях [1], продемонстрировали эффективность HITS. В дополнение к указанным методам оценки качества страниц исследователи предложили ссылочные алгоритмы идентифицирующие некачественные документы, которые создаются с единственной целью манипулирования алгоритмами ранжирования поисковых систем. Для того чтобы отделить качественные страницы от спама, Gyongyi и др. [11] разработали алгоритм доверия TrustRank. За этой работой последовали и другие исследования, которые предложили такие методы анализа ссылочной структуры спам-документов, как Anti-Trust Rank [20] и Truncated PageRank [2]. Отметим, что TrustRank является эффективным алгоритмом ссылочного анализа, присваивающим веб-страницам вероятностные оценки доверия. Те цифровые документы, которые получают низкую оценку, вероятней всего, являются спамом, а те веб-страницы, что получают высокий траст, скорее всего, следует относить к качественным узлам. Все указанные выше методы ссылочного анализа стали популярными и важными инструментами в механизме ранжирования поисковых машин. Однако тот ссылочный веб-граф, на котором эти алгоритмы базируются, не является для нас достоверным по той простой причине, что линки могут легко удаляться/добавляться веб-мастерами, интересующимися продвижением сайтов в поисковой выдаче или даже самим пользователями, если мы обратимся к Web 2.0. Поэтому, как вы могли видеть из Таблицы 1, зашумленность ссылочных веб-графов создает для этих алгоритмов препятствия в эффективном оценивании качественных характеристик интернет-документов.

Было предложено несколько методов для противодействия манипулированию структурой Веба. Такие алгоритмы как DiffusionRank [28] и AIR (Affinity Index Ranking) [18] были разработаны с целью закрытия брешей в методологии Google PageRank и TrustRank. DiffusionRank был инспирирован моделью тепловой диффузии, аналогичной распределению энергии по исходящим линкам. Оценки качества веб-документа в алгоритме AIR рассчитываются на веб-графе эквивалентного электронной схеме. По аналогии с TrustRank оба алгоритма требуют создания «набора высококачественных образцов». Результаты опытов показали, что DiffusionRank и AIR лучше определяют спам не только на искусственных малых, но также и на больших реальных веб-графах по сравнению с методологиями предыдущего поколения, то есть PageRank и TrustRank. Однако помимо ссылок, сгенерированных с единственной целью манипулирования алгоритмами ранжирования и разного рода прочего спама, подавляющее большинство веб-страниц содержат бессмысленные для учета при расчетах авторитетности и низкокачественные гиперлинки. К ним можно отнести, например, ссылки на копирайт, рекламные линки, а также ссылки с регистрационной информацией. Пользователи редко кликают по таким «непопулярным» ссылкам, но именно они составляют значительную часть Веб-графов. И DiffusionRank, и модель AIR не в состоянии справиться с подобным «шумом» в данных гиперссылочной структуры.

Вследствие того, что использование только алгоритмов ссылочного анализа в реальных условиях поиска представляется достаточно проблематичным, последующие исследователи попытались использовать не только гиперлинки для оценки качества Веб-страниц за счет расширения используемых в классификаторах особенностей. Chau и др. [8] использовал как ссылочных характеристики, так и контентные особенности документов для идентификации страниц в соответствии с определённой тематикой. Liu и др. [24] предложил метод, основанный на обучении, заключающийся в идентификации целевых страниц вне зависимости от запроса, используя как особенности контента, так и ссылочные характеристики, такие как длина документа и количество внешних входящих линков. Jacob и др. [16] так же использовал для детекции веб-спама свойства обоих типов, то есть как ссылочных, так и относящихся к содержимому документа. Несмотря на то, что эти «гибридные способы» используют не только ссылочные характеристики, чистые алгоритмы ссылочного анализа по-прежнему играют важнейшую роль в идентификации высококачественных или низкосортных, спамовых страниц. Таким образом, качество гиперссылочных данных и эффективность ссылочных анализаторов остается крайне сложной проблемой. В отличие от перечисленных выше подходов для оценки качества веб-страниц, мы принимаем в расчёт поведенческие факторы. Поведение большинства пользователей определяется их интересами и информационными потребностями. Таким образом, посещённые страницы и те ссылки, по которым совершаются переходы, должны считаться более весомыми, чем страницы с низкой посещаемостью и ссылки с небогатой историей кликов. Как следствие, мы имеем возможность сократить веб-граф на основе вышеупомянутых пользовательских предпочтений.

2.2 Анализ пользовательского поведения

Несмотря на то, что такие исследователи, как, например, Page и др. [25] пытались использовать информацию о пользовательском поведении (собранную у DNS провайдеров) в оценке качества страницы при гиперссылочном анализе, непосредственное изучение поведения пользователей приобрело широкую популярность лишь в последнее время. Такие тулбары, устанавливаемые в интернет-обозреватели пользователей, как Google Toolbar и Live Toolbar занимаются активным сбором статистической информации о пользовательском поведении при веб-сёрфинге. Для поисковых машин эти данные считаются ценнейшим источником неявной обратной связи, сообщающей им о степени релевантности того или иного документа пользовательскому запросу, а также его авторитетности. Именно по этой причине тулбары широко применялись для оценки юзабилити веб-сайтов в [10, 17, 26], определений намерений пользователя в [27] и исследованиях [4, 22, 23, 29], касающихся информационного поиска. Посредством использования полученных данные пользовательского поведения мы можем уменьшить веб-граф путём удаления непосещаемых узлов и ссылок. К примеру, Liu и др. [23] сконструировал «граф пользовательских просмотров» с использованием данных о записях обращений к страницам веб-сайта. Считается, что граф сёрфинга может решить большинство проблем оригинального ссылочного веб-графа, так как используемые для построения первой модели гиперлинки выбираются, в этом случае, самими пользователями. Liu и др. так же разработал алгоритм для оценки качества веб-страницы, который называется BrowseRank и основывается на модели Марковских процессов с непрерывным временем. Практические эксперименты показали, что алгоритм BrowseRank работает лучше, нежели чем такие методы ссылочного анализа, как Google PageRank и TrustRank, особенно в том случае, когда последние работают в масштабах всего Веб-графа.

Граф пользовательских просмотров является далеко не единственным способом учета поведенческих факторов в задачах улучшения оценок качества интернет-страницы. Кроме того, интерпретация такого графа не всегда очевидна. Например, мы делаем вывод о том, что более меньший по своим размерам граф сёрфинга отличается от полноценного ссылочного графа по ряду свойств, однако остается открытым следующий вопрос:  в чем же именно отличается их структура? Как пользовательский граф эволюционирует с течением времени? Согласимся, что BrowseRank превосходит алгоритмы Google PageRank и TrustRank при расчетах последних на оригинальном ссылочном графе, но как поведут себя алгоритмы на графе сёрфинга? Мы пытаемся дать ответы на эти вопросы экспериментальным путём, а так же пытаемся понять, как полученные данные могут быть использованы для последующего создания более качественной модели рационального блуждания, а не широко используемой модели случайного сёрфинга.

3. Модель рационального серфинга с предварительными знаниями

С учетом тех примеров, что были продемонстрированы в Таблице 1 и на Рисунке 1 мы уже знаем, что пользователи не проходят по гиперссылкам с одинаковой вероятностью, а потому далеко не все они должны рассматриваться нами как обладающие равнозначной ценностью при построении модели серфинга. По причине определенных сложностей, связанных со сбором информации о поведении пользователей, большая часть предыдущих работ, касающихся извлечения данных, базировались на «модели случайного серфинга», которая предполагает то, что пользователь проходит по тем или иным гиперлинкам в случайном порядке. В отличие от подобного рода исследований, наша работа потребовала сбора огромного количества информации о пользовательском поведении, что было реализовано с помощью самой популярной китайской поисковой системы. Веб-записи пользовательских обращений собирались в период с 3 августа 2008 по 6 октября 2008 (60 дней; за исключением логов в период с 3 по 4 сентября, которые не были включены по причине ошибки жесткого диска). Было зарегистрировано более 2.8 млрд. прохождений по гиперссылкам, которые могли быть использованы нами в качестве предварительных знаний при построении модели серфинга. Более подробный разбор данных журнала событий приводится в разделе 4.1. Разработанный с учетом модели случайного серфинга, алгоритм Google PageRank обладает «излишней демократичностью» [28], которая является одним из его основных недостатков. Оригинальный алгоритм Google предполагает, что интернет-пользователи либо случайным образом переходят по исходящим гиперссылкам, ведущих на какую-либо веб-страницу (с вероятностью α), либо телепортируются на случайно выбираемый цифровой документ на заданном веб-графе (с вероятностью 1- α):

Формула 1.

В соответствии с Уравнением (1) голосующая способность страницы распределяется между всеми исходящими гиперссылками. Однако, как мы уже говорили, не все ссылки одинаково полезны для наших расчетов. Такие гиперлинки, как «топ новостей», находящиеся на главной странице ресурса CNN.com являются более значимыми с точки зрения пользователей, нежели чем, например, рекламного характера. Следовательно, предположение о том, что пользователи будут следовать по ним с одинаковой вероятностью, является неразумным. Если мы представим вероятность посещения страницы Xj непосредственно после посещения документа Xi, а именно P (Xi ⇒ Xj), модель случайного серфинга заменяется на модель «серфинга с предварительными знаниями», и расчёт P (Xi ⇒ Xj)  требует предварительных данных о пользовательском поведении. С учетом модели «серфинга с предварительными знаниями» веб-пользователи, вместо того, чтобы равновероятно проходить по ссылкам на случайный документ, следуют по каждому линку L с вероятностью P (Xi ⇒ Xj), где Xi является страницей-источником, а Xj — страницей-целью. Тогда, Уравнение (1) можно переписать следующим образом:

Формула 2.

В Уравнении (2) P (Xi ⇒ Xj) является вероятностью посещения страницы Xi непосредственно после посещения документа Xi. Тем не менее, на оригинальном веб-графе оценка такой вероятности представляется невозможной по причине отсутствия релевантной информации. Следовательно, Google PageRank (как и TrustRank) должен вычисляться посредством использования равных значений P (Xi ⇒ Xj) (см. Уравнение (1)). Для того чтобы включить предварительную информацию о пользовательском поведении в оригинальный веб-граф, нам необходимо выбрать посещаемые узлы и ребра, а также собрать данные о количестве пользовательских кликов по каждой гиперссылке (ребру). С учетом этой информации мы сможем определить, какие же именно линки представляют для пользователя интерес, а также произвести оценку вероятности P (Xi ⇒ Xj)  с учётом допущения о максимальном сходстве. Если мы используем UC(Xi ⇒ Xj) для обозначения количества пользовательских кликов со страницы Xi к документу Xj, оригинальная формула Google PageRank может быть переписана следующим образом:

Формула 3.

В Уравнении (3) вероятность P (Xi ⇒ Xj)  оценивается посредством взвешенного коэффициента UC с учетом гипотезы максимального правдоподобия. Значение PageRank страницы Xi распределяется между исходящими гиперссылками, взвешенных по UC всякого линка. Кроме модификации распределения голосующей способности документа никакой другой параметр оригинального алгоритма Google не изменяется. Следовательно, временная сложность алгоритма, а также его эффективность остаются соответствующие оригинальному исполнению. Аналогичные модификации могут быть применены и к алгоритму доверия TrustRank, который традиционно распределяет степень доверия равномерно между всеми исходящими линками. Оригинальный и модифицированный алгоритм представлен в Уравнениях (4) и (5) соответственно:

Формула 4.
Формула 5.

В модели «серфинга с предварительными знаниями» гиперссылки уже не рассматриваются как одинаково значимые, а вероятность прохождения по ним интернет-пользователей рассчитывается с учетом предварительных знаний и гипотезы максимального правдоподобия. Таким образом, мы надеемся улучшить производительности алгоритмов Google PageRank и TrustRank, которые в своем оригинальном исполнении основываются на модели случайного блуждания. Мы считаем, что в том случае, если возможна оценка вероятности межузлового посещения, тогда наша новая модель серфинга также может быть использована не только в условиях рассматриваемого нами ссылочного веб-графа, но и на других графах. Например, обозначим за G=(V, E) социальный граф, где V представляет собой пользователей, а E — социальные взаимоотношения между ними. Во многих социальных сервисах, таких как Twitter и Weibo (крупнейший китайский сервис микроблогов с более чем 250 млн. пользователей на 2012 год), взаимоотношения между пользователями могут быть описаны как ориентированные ребра, ведущие от постоянных читателей (follower) к блоггеру (followee), аналогично тому, как страница-источник ссылается на целевой документ. Интуитивно понятно, что оценка качества того или иного социального узла в подобного рода сетях будет схожа с расчетом авторитетности интернет-странички, а следовательно здесь мы также можем использовать такие гиперссылочные алгоритмы, как Google PageRank и TrustRank.  Мы считаем, что взаимоотношения между узлами в указанных социальных сервисах также не должны оцениваться с одинаковой степенью значимости. В данном случае это связано с тем, что одни пользователи могут подписываться на микроблог других участников сервиса по абсолютно разным причинам и более близкие отношения следует ценить в большей мере. Следовательно, на социальных графах модель «серфинга с предварительными знаниями» также представляется более адекватной, нежели чем часто используемая в исследованиях классическая модель случайного блуждания.

4. Построение веб-графа с учетом данных пользовательского поведения

4.1 Данные о поведении пользователей

На основании той модели «серфинга с предварительными знаниями», которая была описана в Разделе 3, мы модифицируем оригинальный алгоритм ранжирования Google PageRank и TustRank за счет включения в данную методологию предварительно извлеченной информации о пользовательском поведении. Таким образом, предложенные нами новые методы ранжирования страниц userPageRank и userTrustRank требуют дополнительной информации и не могут выполняться на оригинальном веб-графе. Для построения достоверного веб-графа, который учитывал бы информацию о поведении интернет-пользователей, мы собрали большую коллекцию поведенческих данных (также называемых логами веб-доступа или данными пользования вебом). В отличие от логов пользовательских запросов и данных о кликах на странице органической выдачи, эти данные собираются посредством использования панели инструментов, которая устанавливается в браузер пользователя. Такого рода данные содержат в себе поведенческую информацию, в том числе взаимодействие пользователя с поисковыми системами и прочими интернет-сайтами. Поисковые машины активно используют эту анонимную статистическую информацию в целях улучшения качества предоставляемых ими услуг. В таких предыдущих работах, как [4] было показано, как улучшается производительность функции ранжирования за счет использования в ней информации о кликах пользователей на странице поисковых результатов. Liu и др. [22] предложил алгоритм обнаружения поискового спама, который также основывался на такого рода поведенческой информации.  В настоящей работе мы также использовали данные использования веба, собранные посредством тулбаров по той простой причине, что это позволяет нам беспрепятственно собирать информацию о пользовательском поведении, не отвлекая самих пользователей. Пример данных, записываемых в этих логах представлен в Таблице 2 и Примере 1.

Наименование Описание
Time Stamp Дата и время события клика
ID Сессии Случайно назначаемый ID каждой сессии пользователя
Исходный URL URL страницы, которую пользователь посещает в данный момент
Целевой URL URL страницы, на которую пользователь переходит

Таблица 2. Информация, записываемая в логах веб-обращений.

Пример 1. Экземпляр лога веб-доступа, собранного 15 декабря 2008 года.

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

4.2 Построение графа пользовательских просмотров и человеко-ориентированного гиперссылочного графа

Используя полученную информацию о пользовательском поведении, описанную в Разделе 4.1, мы определили то, какие же именно узлы и ссылки посещаются пользователями в процессе веб-серфинга, и следующие два алгоритма используются нами для построения графа пользовательских просмотров и человеко-ориентированного гиперссылочного графа. Алгоритм 1 строит веб-граф исключительно на данных пользовательского поведения. В него включаются только те узлы и ссылки, которые были посещены в процессе веб-серфинга по крайней мере 1 раз. По-сути, он аналогичен тому графу, который был получен Liu и др. [23], за тем исключением, что количество пользовательских проходов по всякому ребру также записывается для оценки P (Xi ⇒ Xj) для алгоритмов UserPageRank и UserTrustRank. Далее, для краткости мы обозначим граф пользовательских просмотров за «BG(V,E)».

Алгоритм 1. Алгоритм построения графа пользовательских просмотров BG(V,E).

Алгоритм 1.

Алгоритм 2 строит веб-граф отличный от BG(V,E). Эти два графа имеют общие наборы узлов, однако второй граф сохраняет все рёбра между их общими узлами оригинального веб-графа. Мы называем его человеко-ориентированным гиперссылочным графом (сокращенно, user-HG(V,E)), поскольку, несмотря на наследование ссылочной структуры оригинального веб-графа, он содержит в себе только те узлы, которые отбирались с учетом наличия о них поведенческой информации. Сам оригинальный веб-граф был построен исходя из данных той же самой системой информационного поиска, которая предоставила нам пользовательские логи, и на июль 2008 года он содержал более 3 млрд. страниц, относящихся к 111 млн. интернет-сайтам, составляющих львиную долю китайского веба на тот период времени.

Алгоритм 2. Алгоритм построения человеко-ориентированного гиперссылочного графа user-HG(V,E).

Алгоритм 2.

Таким образом, графы BG(V,E) и user-HG(V,E) строятся с учетом информации пользовательского поведения. Последний граф содержит в себе больше гиперссылок, в то время как предыдущий сохраняет только те из них, по которым следуют пользователи. Мы обнаруживаем, что алгоритмы UserPageRank и UserTrustRank не могут выполняться на графе user-HG(V,E) по той просто причине, что в отношении всех его ребер данные о пользовательском поведении не учитываются.

4.3 Сравнение графа пользовательских просмотров и человеко-ориентированного гиперссылочного графа

Мы построили графы BG(V,E) и user-HG(V,E), опираясь на данные пользовательского поведения (см. Раздел 4.1), а Таблица 3 демонстрирует различие между ними.

  Число общих рёбер Число рёбер Процент общих рёбер
BG(V,E) 2,951,716 10,564,205 24.53%
user-HG(V,E) 139,125,250 1.86%

Таблица 3. Реберное различие графов BG(V,E) и user-HG(V,E).

По Таблице 3 можно обнаружить, что вопреки тому обстоятельству, что человеко-ориентированный гиперссылочный граф user-HG(V,E) имеет общий с графом BG(V,E) набор узлов, композиции двух этих моделей существенно различаются. Во-первых, граф пользовательских просмотров BG(V,E) составляет менее чем 1/10 объема user-HG(V,E). Процент общих страниц графа user-HG(V,E) составляет только 1.86%; следовательно, более (98.14%) ссылок на графе user-HG(V,E) не представляют для пользователей какого-либо интереса и они по ним не проходят к следующим узлам. Это отличие согласуется с тем опытом, который говорит нам об избыточном числе ссылок, присутствующих в содержимом документе, по которым пользователи могут пройти в процессе своего серфинга далее. Еще один интересный вывод, которой можно сделать в ходе сравнительного анализа двух систем, заключается в том, что человеко-ориентированный гиперссылочный граф user-HG(V,E) содержит в себе не все ребра, наличествующие в графе BG(V,E). Менее чем 1/4 страниц графа пользовательских просторов BG(V,E) также появляются в user-HG(V,E). Этот феномен можно отчасти объяснить тем, что граф user-HG(V,E) был создан в ходе сканирования веба, процесс которого не может предполагать получение в наше распоряжение всей гиперссылочной структуры веба в целом по той простой причине, что Глобальная паутина велика и подвержена быстрым изменениям. Когда мы проинспектировали те линки, которые появились только в графе пользовательских просмотров BG(V,E),мы обнаружили еще одну причину, по которой человеко-ориентированный гиперссылочный граф user-HG(V,E) не имеет их в своей структуре. Большая часть данных линков содержит в себе информацию о переходах пользователей со страниц выдачи поисковых результатов (SERP). Таблица 4 показывает количество SERP-ориентированных гиперссылок на графе BG(V,E).

Поисковая система Число рёбер вне user-HG(V,E)
Baidu.com 1,518,109
Google.cn 1,169,647
Sogou.com 291,829
Soso.com 147,034
Yahoo.com 143,86
Всего 3,270,479 (30.96% всех рёбер в BG(V,E))

Таблица 4. Количество SERP-ориентированных ребер, не включенных в человеко-ориентированный гиперссылочный граф user-HG(V,E)

Таблицы 3 и 4 показывают нам, что из всего количества ссылок, наличествующих исключительно в BG(V,E) (в общей сложности 7.97 млн. ребер), более 3.27 млн. приходится на SERP пяти наиболее популярных поисковых систем КНР. Это число составляет 30.96% всех рёбер графа пользовательских просмотров BG(V,E). Несмотря на то, что пользователи совершают многократные переходы с SERP, почти ни одна из этих ссылок не может быть проиндексирована нашим краулером. Безусловно, данные линки несут в себе ценнейшую информацию, как потому, что они ведут на оригинал тех веб-документов, которые порекомендованы для ознакомления системами информационного поиска, так и потому, что пользователи их поиска совершили по ним соответствующий переход. Поскольку количество подобного рода ссылок оказывается чрезмерно велико, процесс веб-краулинга исключает возможность сканирования всех ссылок со страницы результатов поисковой выдачи без наличия информации пользовательского поведения. Другим важным типом ссылок, который встречается только в графе пользовательского поведения BG(V,E), являются те гиперссылки, по которым был осуществлен пользовательский переход в рамках защищенной сессии. Например, после соответствующей авторизации, веб-пользователь получает доступ к той части ресурса, которая доступна только авторизованным пользователям. В то время, как содержащиеся в ней ссылки не могут быть обработаны обычным веб-сканером по причине защищенности интернет-страниц, в случае использования тулбаров, устанавливаемых в браузер пользователя, данные о его поведении все равно могут быть записаны.

4.4 Построение человеко-ориентированного комбинированного графа

В предыдущем разделе было показано отличие графа пользовательских просмотров от человеко-ориентированного гиперссылочного графа по меньшей мере в двух моментах: во-первых, в сравнении с user-HG(V,E) большая доля ребер (98.14% E человеко-ориентированного гиперссылочного графа user-HG(V,E)) не обнаруживаются в графе пользовательских просмотров BG(V,E) постольку, поскольку по ним не совершается пользовательских переходов. Во-вторых, BG(V,E) содержит ссылки, индексация которых представляется невозможной или затруднительной. Таким образом, каждый граф сам по себе содержит уникальную информацию, которую следует учитывать. По этой причине, если мы решим создать граф, содержащий все ребра и узлы графа пользовательских просмотров BG(V,E) и человеко-ориентированного гиперссылочного графа user-HG(V,E), это позволит получить нам более полную информацию, касающуюся гиперссылочной структуры веба. Для реализации этой задачи мы используем соответствующий алгоритм (см. Алгоритм 3), который позволит создать веб-граф, комбинирующий всю гиперссылочную информацию BG(V,E) и user-HG(V,E):

Алгоритм 3.

Алгоритм 3. Алгоритм построения человеко-ориентированного комбинированного графа.

Этот алгоритм позволяет построить такой граф, который, несмотря на содержание только единого для графов BG(V,E) и user-HG(V,E) набора узлов, имел бы полную гиперссылочную структуру обоих моделей. Так как в нем комбинируются наборы ребер BG(V,E) и user-HG(V,E) мы называем его человеко-ориентированным комбинированным графом или, для краткости, user-CG(V,E). Поскольку, как и человеко-ориентированный гиперссылочный граф user-HG(V,E), он также не содержит в себе всей информации по прохождению веб-пользователей по имеющимся в нем ребрам, предложенные нами алгоритмы UserPageRank/UserTrustRank не могут быть выполнены на данной модели.

4.5 Дескриптивная статистика построенных графов

С помощью полученных данных пользования вебом, описанных нами в Разделе 4.1, а также исходного оригинального веб-графа (для краткости, мы будем называть его whole-HG(V,E)), упомянутого нами в Разделе 4.2, мы построили три графа, а именно: BG(V,E), user-HG(V,E), и user-CG(V,E). Для достижения большей эффективности все три графа были построены на уровне веб-сайтов, а не отдельных страничек. Вообще, использование здесь графа сайтов является уместным еще и по той простой причине, что подавляющее число поисковых систем применяют алгоритмы ссылочного анализа на уровне веб-сайтов прежде чем распространить соответствующие оценки на те документы, которые относятся к анализируемому интернет-ресурсу. Еще одна сложность, возникающая в случае построения графов на уровне страниц, заключается в разреженности данных, то есть мы имеем крайне незначительное число пользовательских визитов для подавляющей части интернет-страниц, что может привести к недостоверности поведенческой информации. Однако для графа сайтов среднее значение пользовательских визитов, приходящихся на веб-ресурс оказывается во сто крат большим, что в значительной степени решает вышеупомянутую проблему разреженности данных. Согласно результатам тех экспериментов, которые были получены в нашей предыдущей работе [29], мы обнаружили, что узловая модель обладает более высоким значением быстродействия. В случае использования графа сайтов усредненные числовые показатели пользовательской активности оказывается большими, чем при использовании постраничных моделей, что также дает нам более достоверный источник поведенческой информации. Дескриптивная статистика построенных нами графов, представлена в Таблице 5.

Граф Число вершин Число рёбер Соотношение рёбер/вершин
BG(V,E) 4,252,495 10,564,205 2.48
user-HG(V,E) 4,252,495 139,125,250 32.72
user-CG(V,E) 4,252,495 147,097,739 34.59
whole-HG(V,E) 110,960,971 1,706,085,215 15.38

Таблица 5. Размеры построенных нами трех графов, а также оригинального веб-графа.

Как мы можем видеть из Таблицы 5, BG(V,E), user-HG(V,E) и user-CG(V,E) покрывают только малый процент (3.83%) вершин оригинального веб-графа. Реберные наборы всех наших трех графов также оказываются меньшими, нежели чем оригинального веб-графа, однако среднее число гиперссылок, приходящихся на узел в человеко-ориентированном гиперссылочном user-HG(V,E) и комбинированном user-CG(V,E) графе выше, чем у оригинального веб-графа whole-HG(V,E). Такое положение вещей означает буквально следующее: доступные для пользовательского посещения узлы оказываются сильно связанными в отличие от прочих частей веб-графа. Такой паттерн намекает на наличие значительной компоненты сильной связанности пользовательского графа,  представленного в [9].  Еще одним выводом может считаться то, что по сравнению с user-HG(V,E) и user-CG(V,E), соотношение ребер и вершин на графе пользовательских просмотров BG(V,E) оказывается крайне несущественным. Таким образом, большая доля гиперссылок удаляется на данном графе по причине отсутствия по ним пользовательских переходов. Сохраненные линки предположительно полагаются нами как более значимыми для пользователей. В дальнейшем нам еще предстоит ответить на крайне важный вопрос, который заключается в том, создаст ли потеря этой информации, пусть даже неактуальной для веб-пользователя, проблему для алгоритмов ссылочного анализа?

5. Структура и эволюция построенных графов

5.1 Структура построенных графов

Для описания структуры веб-графа многими исследователями, в том числе Broder и др. [6] использовалось степенное распределение. Существование степенного закона распределения было верифицировано в ходе нескольких обходов веб-графов [6,9] и рассматривается на сегодняшний день как одно из основных свойств Глобальной паутины. Нам было интересно узнать, поддаются ли распределение полустепеней захода и исхода созданных нами графов степенному закону. Экспериментальные результаты степенного распределения графов BG(V,E) и user-HG(V,E) представлены на Рисунке 2 и 3. Мы не стали рассматривать степенное распределение человеко-ориентированного комбинированного графа user-CG(V,E) поскольку он является комбинацией графов BG(V,E) и user-HG(V,E). В том случае, если распределение полустепеней захода и исхода этих двух графов поддаются степенному закону, тогда аналогичная картина будет наблюдаться и на user-CG(V,E).

Рисунок 2.

Рисунок 2. Распределение полустепени захода графов BG(V,E) и user-HG(V,E), подчиняющееся степенному закону.

Рисунок 2 демонстрирует нам, что распределение полустепени захода обоих графов BG(V,E) и user-HG(V,E) подчиняются степенному закону. По причине того, что мы используем ссылочный граф сайтов, а не веб-страниц, экспонента степенного закона (1.75) оказывается меньшей, чем в результатах предыдущих исследований (приблизительно 2.1 [6,9]). В нашем случае имеется меньшее число непопулярных узлов (в отношении количества входящих ссылок), как это было бы в случае построения графа на уровне интернет-страниц. Интересно отметить еще и ту особенность, что экспонента степенного закона распределения графа BG(V,E) (2.30) оказывается выше, чем у человеко-ориентированного ссылочного графа user-HG(V,E) (1.75). Это отличие подразумевает, что с увеличением полустепени захода i, на графе сёрфинга пользователя количество вершин со входящими ссылками i сокращается быстрее, чем на графе user-HG(V,E). Этот паттерн можно объяснить тем, что на графе BG(V,E) некоторые веб-сайты обладают относительно большей популярностью (имеют большее число входящих ссылок), нежели чем на человеко-ориентированном гиперссылочном графе user-HG(V,E).

Рисунок 3.

Рисунок 3. Распределение полустепени исхода графов BG(V,E) и user-HG(V,E), подчиняющееся степенному закону.

Рисунок 3 демонстрирует нам, что распределение полустепени исхода обоих графов BG(V,E) и user-HG(V,E) также подчиняются степенному закону. В предыдущих исследованиях [6,9] экспонента распределения полустепени исхода составляла 2.7. В случае же нашего графа сайтов ее значение составляет только 1.9; мы опустили из рассмотрения те исходящие ссылки, которые не выходят за пределы единого для них ресурса. Это предположение позволяет уменьшить не только количество исходящих ссылок для множества вершин нашего графа, но и разницу между вершинами, имеющих крайне высокий и низкий показатель полустепени исхода. Экспонента распределения полустепени исхода графа пользовательских просмотров BG(V,E) оказывается ниже, чем у user-HG(V,E). Здесь это различие означает то, что с увеличением полустепени исхода o, количество вершин с исходящими ссылками o сокращается быстрее на человеко-ориентированном гиперссылочном графе. Результаты экспериментов, приведенные на Рисунках 2 и 3, на которых распределение полустепени захода и исхода графов BG(V,E) и user-HG(V,E), подчиняются степенному закону, подтверждают наше предположение о том, что построенные нами графы схожи по своей структуре с исходным оригинальным веб-графом whole-HG(V,E). Так как построенный нами граф пользовательских просмотров и человеко-ориентированный граф имеют меньшее число бесполезных с точки зрения пользователей ссылок и узлов, экспоненты степенного закона отличаются от whole-HG(V,E). Тот факт, что  BG(V,E) и user-HG(V,E) наследуют структурные особенности Глобальной Паутины, позволяет внедренному нами алгоритму ссылочного анализа исполняться на данных графах.

5.2 Эволюция графа пользовательских просмотров BG(V,E) и оценка качества недавно посещенных страниц

Целью нашей работы является оценка качества цифровых документов с помощью информации пользовательского поведения. Для практического применения на системах информационного поиска, наиболее важным представляется вопрос того, могут ли оценки качественной составляющей веб-страниц, рассчитанные в off-line режиме, использоваться в процессе поиска on-line. Граф пользовательских просмотров BG(V,E), человеко-ориентированный гиперссылочный граф user-HG(V,E), а также человеко-ориентированный комбинированный граф user-CG(V,E) были построены с учетом информации поведения веб-пользователей, собранной поисковыми системами. Такого рода информация собирается в течение определенного периода времени. Следовательно, поведение пользователя вне заданных временных рамок не может быть включено в сконструированные нами модели. Если страницы, востребованные пользователями, оказываются не включенными в заданные графы, тогда последующая оценка качественной составляющей интернет-документов оказывается невозможной. Следовательно, нам необходимо определить, во-первых, то, каким образом будут эволюционировать композиции этих трех графов с течением времени, а во-вторых, возможно ли включение в данные модели недавно посещенных пользователем веб-документов. Чтобы узнать, можно ли при создании графов BG(V,E) , user-HG(V,E) и user-CG(V,E) избежать проблем, связанных с недавно посещёнными страницами и отсутствующими документами, мы провели следующий эксперимент:

Шаг 1. Каждый день создается огромное количество web-страниц, который попадают в поисковый индекс, но только часть из них посещается пользователями. Здесь мы будем делать акцент только на недавно посещенных пользователем веб-документах, поскольку недостаток таких страниц в предложенной нами модели может оказывать существенное влияние на данные, касающиеся взаимодействия с пользователем. Следовательно, рассмотрим, как много недавно посещённых страниц включаются в конструируемые графы.

Рисунок 4.

Рисунок 4. Эволюция графа пользовательских просмотров BG(V,E). По оси абсцисс X отложена дата, начинающаяся от 3 августа 2008. По оси ординат Y — процент страниц/ссылок, по которым были осуществлены свежие переходы, изначально не включенные в граф BG(V,E).

На рисунке 4 каждый результат обработки данных показывает нам процент страниц/ссылок, по которым были осуществлены свежие переходы, изначально не включенные в граф BG(V,E). Ежедневно, по данным за предыдущий день создаётся граф пользовательских просмотров. Его конструируют с учётом информации о пользовательском поведении, собранной начиная от 3 августа 2008 года (первый день на рисунке). Мы ориентируемся на BG(V,E) по той причине, что человеко-ориентированный гиперссылочный user-HG(V,E) и комбинированный user-CG(V,E) графы обладают смежным набором вершин. Так как до начала наших наблюдений никакие свежие данные не были включены в граф пользовательских просмотров BG(V,E), то в первый день в категорию недавно посещенных попали все ребра и вершины графа. Начиная со второго дня наблюдений вплоть до 15 дня, процент недавно посещенных пользователями ребер и вершин начинает падать. Для каждого дня, следующего за 15-м, новыми оказываются приблизительно 30% ребер и 20% вершин. В течение первых 15 дней падение недавно посещенных вершин и ребер обусловлено тем, что структура нашего графа становится все более и более полной, и на 15-й день он содержит 6.12 млн. ребер и 2.56 млн. вершин. Начиная с этого дня, динамика недавно посещенных ребер и вершин оказывается достаточно стабильной, и каждые последующие сутки граф прирастает на порядка 0.3 млн. новых ребер и около 0.1 млн. новых вершин. Таким образом, для построения стабильного графа пользовательских просмотров нам потребовалось около 15 дней; следовательно, в граф BG(V,E) ежедневно не включается до 20% новых веб-сайтов, посещенных пользователями.

Шаг 2. Итак, согласно Шагу 1, приблизительно 20% сайтов, относящихся к числу недавно посещенных, будет отсутствовать в нашей модели в том случае, если мы будем использовать граф пользовательских просмотров BG(V,E) для оценки качества веб-страниц (предполагается, что BG(V,E) обновляется ежедневно). Для того, чтобы определить какой эффект окажет это недостающее множество недавно посещенных сайтов на присуждаемые оценки, касающихся качественной составляющей ресурсов, мы исследовали данные веб-сайты на предмет наличия их в поисковом индексе систем информационного поиска. В том случае, если они не были проиндексированы поисковыми системами, тогда у нас нет необходимости присваивать им качественные оценки, та как они не будут приниматься в расчет при ранжировании результатов в органическом поиске. Мы выбрали 30,605 страниц из тех интернет-сайтов, которые имели пользовательский трафик за отчетный период, однако не были учтены в модели BG(V,E) (приблизительно 1% от всех посещенных документов, относящихся к текущим веб-ресурсам) и проверили их на предмет наличия их в индексе популярных китайских поисковиков (Baidu.com, Google.cn, Sogou.com, Yahoo.cn). Результаты этого эксперимента приведены в Таблице 6 (вместо названий поисковых машин мы использовали обозначения SE1-SE4, соответствующие их порядку, данному чуть выше).

Поисковая система Процент проиндексированных страниц
ПС1 8.65%
ПС2 11.52%
ПС3 10.47%
ПС4 14.41%
Среднеарифметическая простая 11.26%

Таблица 6. Процент недавно посещенных пользователями страниц, проиндексированных системами информационного поиска.

Результаты опыта, приведенные в Таблице 6, показывают, что большая часть этих документов (в среднем 88.74%) не проиндексированы китайскими поисковыми системами. Отсюда, у нас нет никакой острой необходимости включать их в наш граф пользовательских просмотров, так как поисковики не будут учитывать присвоенные им оценки при ранжировании результатов в органическом поиске.

Шаг 3. Опираясь на результаты предыдущих Шагов, не трудно подсчитать, что только 2.2% (11.26% x 20%) из недавно посещенных пользователями документов, которые изначально отсутствовали в предложенной нами модели, также потребуют от нас оценки их качественных параметров. Те документы, которые не только проиндексированы системами информационного поиска, но и имеют пользовательский трафик, будут включены в граф пользовательских просмотров BG(V,E) при условии его ежедневного обновления и поступления новых пользовательских логов, содержащих поведенческую информацию. Следовательно, в задачах присуждения качественных оценок целесообразней всего представляется использование именно BG(V,E). Что же касается человеко-ориентированного гиперссылочного user-HG(V,E) и комбинированного user-CG(V,E) графов, то они имеют смежные вершины с графом пользовательских просмотров, поэтому проблема трафика неучтенных страниц, если и коснется двух данных моделей, то крайне несущественно. Таким образом, эти графы также представляются для нас пригодными для оценки качества интернет-документов.

6. Результаты экспериментов и их обсуждение

6.1 Подготовка эксперимента

В Разделе 1 мы выдвинули предположение, что куда более достоверной частью веб пространства является та часть, которая имеет пользовательский трафик в отличие от той, которая его не имеет. На основании этого предположения мы построили три отличных друг от друга ссылочных графов, в основу которых положена информация о пользовательских просмотрах интернет-страниц и прохождениям по линкам. Для того, чтобы определить превосходят ли построенные наши графы оригинальный веб-граф мы решили использовать два метода. Первый метод нашей проверки базируется на метрике ROC/AUC. Для создания тестового множества ROC/AUC мы рандомно выбрали 2.279 сайтов в соответствии с частотой пользовательских визитов, а также попросили двух асессоров оценить их качество. Приблизительно 39% данных веб-сайтов были классифицированы асессорами как «высококачественные», порядка 19% — как «спам»; все остальные ресурсы имели отметку «ординарные». После исполнения алгоритмов ссылочного анализа каждому веб-сайту из тестового множества была присвоены соответствующие качественные оценки. Мы можем оценить производительность алгоритма ссылочного анализа на основании того, были ли присуждены более высокие оценки качественным страницам, а некачественным, соответственно, более низкие. Нашим вторым методом является попарное ранжирование. Впервые этот способ был предложен Gyongyi и др. в [11], который опирался на то предположение, что идеальный алгоритм должен ранжировать качественные документы выше, нежели чем некачественные страницы. Для реализации этого метода мы составили тестовый набор, состоящий из 782 пар веб-сайтов. Данные пары были прокомментированы менеджерами в ходе опроса, проведенного среди веб-пользователей компании. Считается, что попарное ранжирование показывает различия между репутациями интернет-ресурсов. Например, video.sina.com.cn и v.blog.sohu.com. являются двумя наиболее популярными в КНР видеообменниками, однако первый сайт представляется более популярным и получает больше трафика, чем его конкурент, то есть с точки зрения качества video.sina.com.cn > v.blog.sohu.com. В том случае, если алгоритм присваивает более высокую оценку video.sina.com.cn, он проходит попарное тестирование (pairwise orderedness test). Для оценки производительности попарного ранжирования мы используем степень аккуратности классификации, который определяется как процент корректно отранжированных пар веб-сайтов. Посредством этих двух методологий мы исследовали возможность более эффективного исполнения традиционных алгоритмов гиперссылочного анализа на графе пользовательских просмотров BG(V,E), человеко-ориентированном гиперссылочном user-HG(V,E) и комбинированном user-CG(V,E) графах по сравнению с оригинальным веб-графом.

В дополнение к этому мы также исследовали эффективность специально разработанных для графов пользовательских промоторов алгоритмов ссылочного анализа (таких как BrowseRank) перед применением традиционных методов (таких как Google PageRank и TrustRank). Сначала, мы сравнили производительность алгоритмов ссылочного анализа на четырех графах (BG(V,E), user-HG(V,E), user-CG(V,E) и whole-HG(V,E)). Затем, мы сравнили производительность Google PageRank, TrustRank, DiffusionRank и BrowseRank на графе пользовательских просмотров BG(V,E). Последнее сравнение проводилось только на графе BG(V,E) постольку, поскольку алгоритм BrowseRank требует информации о времени пребывания пользователя на странице, что применимо только для BG(V,E). Кроме того, для изучения предложенных нами алгоритмов UserPageRank и UserTrustRank мы сравнили эффективность их работы с оригинальными гиперссылочными алгоритмами PageRank и TrustRank на графе пользовательских просмотров и социальном графе, созданного по данным крупнейшего китайского сервиса микроблогов weibo.com.  Для алгоритмов TrustRank и DiffusionRank нам потребовалось создание исходного набора высококачественных страниц. Для этого мы следуем той методологии, которая была предложена Gyongyi и др. в [11] и которая основывается на алгоритме инверсивного Google PageRank, а также экспертных суждениях. Алгоритм инверсивного (обратного) Google PageRank был исполнен на исходным оригинальном веб-графе whole-HG(V,E), и мы аннотировали ТОП 2000 веб-сайтов, отранжированных по данной технологии. В итоге, для создания исходного множества мы отобрали 1153 высококачественных и популярных веб-сайтов. Параметры в реализованных нами алгоритмах Google PageRank, TrustRank и DiffusionRank были настроены в соответствии с их оригинальными реализациями [11, 25, 28]. В соответствии с [25] и [11] параметр α в алгоритмах PageRank и TrustRank составляет 0.85; количество итераций для обоих алгоритмов, необходимых для достижения точки сходимости, составило 30. В соответствии с [28] параметры, используемые в алгоритме DiffusionRank, были следующие: γ = 1.0, α=0.85, M=100.

6.2 Оценка качества по разным графам

Ко всем четырём различным гиперссылочным графам, показанным в Таблице 5, мы применили алгоритм PageRank и оценили производительность расчёта качества веб-страницы. Результаты эксперимента по идентификации высококачественной страницы, спамовой страницы и попарного тестирования показаны на Рис. 5. Производительность идентификации высококачественных и спамовых страниц измеряется значением AUC, в то время как попарное тестирование оценивается по метрике точности.

Рисунок 5.

Рисунок 5. Результаты оценки качества страниц при помощи PageRank по BG(V,E), user-HG(V,E), user-CG(V,E) и whole-HG(V,E).

Рисунок 5 показывает, что PageRank, применённый на первоначальный веб-граф (whole-HG(V,E)) работает хуже всего. Результаты показывают, что графы, построенные алгоритмами 1-3 могут намного лучше оценивать качество Веб-страницы, чем оригинальный веб-граф. Улучшения в производительности по каждому из трёх графов показаны в Таблице 7.

Тестируемый Улучшение в сравнении с whole-HG(V,E)
метод BG(V,E) user-HG(V,E) user-CG(V,E)
Идентификация высококачественной страницы +5.69% +7.55% +7.12%
Идентификация спамовой страницы +3.77% +7.44% +7.46%
Попарное тестирование +15.14% +20.34% +19.67%

Таблица 7. Прирост производительности графов, сконструированных по Алгоритмам 1-3 в сравнении с оригинальным веб-графом.

В соответствии с Таблицей 7, графы, построенные по информации о пользовательском поведении превосходят оригинальный веб-граф примерно на 5-25%. Использование данных о пользовательском поведении снижает зашумленность оригинального графа и повышает его надёжность. Это открытие согласовывается с результатами [23], где BG(V,E) превосходит оригинальный веб-граф. Так же оно подтверждает наше предположении из Раздела 1, что доступная пользователям часть Веба является более надёжной, чем скрытая часть, никогда не посещаемая пользователями.

В соответствии с Рисунком 5 и Таблицей 7 среди трёх графов, построенных с использованием информации о пользовательском поведении, BG(V,E) работает хуже всех, в то время как user-HG(V,E) и user-CG(V,E) показывают весьма похожие результаты. Как описывается в Разделе 3.5, BG(V,E) содержит меньше рёбер по сравнению с двумя другими графами. Оставшиеся ссылки в среднем более информативны, чем рёбра в других графах, однако крупная потеря данных о рёбрах так же затрудняет оценку качества страницы. User-HG(V,E) и user-CG(V,E) работают с одним и тем же набором вершин, а их наборы рёбер весьма похожи (добавлено только 7.97 млн рёбер к user-CG(V,E), что составляет 5.14% от рёбер во всём графе). Поэтому оба графа оценивают веб-страницы примерно одинаково.

BG(V,E), user-HG(V,E) и user-CG(V,E) имеют одинаковый набор вершин, составленный из всех доступных пользователям сайтов, записанных в логах Веб-доступа. Несмотря на то, что BG(V,E) содержит наименьшее число рёбер из всех четырёх графов, он по-прежнему превосходит whole-HG(V,E). Результаты показывает, что выбор набора вершин намного важнее выбора набора рёбер. Снижение числа непосещаемых узлов в первоначальном Веб-графе может быть эффективно при конструировании гиперссылочного графа.

В Разделе 1 мы показываем в Таблице 1 список веб-сайтов, которые ранжируются выше всего в соответствии с оценками PageRank по оригинальному Веб-графу. Мы так же обнаружили, что некоторые государственные веб-сайтв (например, miiberan.gov.cn, hd315.gov.cn) ранжируются достаточно высоко, однако не привлекают внимания пользователей. Эти сайты авторитетны и важны, но они ни должны ранжироваться так высоко, так как прочие государственные веб-сайты имеют гораздо более низкую оценку. Взглянув на результаты PageRank проведённого на BG(V,E) мы обнаружили, что оценки miiberan.gov.cn и hd315.gov.cn более адекватны.

  Ранжирование на whole-HG(V,E) Ранжирование на BG(V,E)
miibeian.gov.cn 5 23
hd315.gov.cn 2 117

Таблица 8. Сравнение ранжирования PageRank правительственных сайтов в графах whole-HG(V,E) и BG(V,E).

В соответствии с Таблицей 8 как miiberan.gov.cn, так и hd315.gov.cn ранжированы ниже по PageRank на BG(V,E), чем на whole-HG(V,E). Они считаются важными ресурсами в соответствии с алгоритмом по графу сёрфинга пользователей, но не такими важными, как топовые сайты. Мы считали, что оценки качества по BG(V,E) являются более точными в соответствии с популярностью и авторитетностью ресурсов.

6.3 Оценка качества с различными алгоритмами ссылочного анализа

В [23] Liu и др. показал, что специальный алгоритм ссылочного анализа (BrowseRank) превосходит TrustRank и PageRank как в противостоянии спаму, так и в идентификации высококачественных веб-страницы, когда последние два алгоритма используются на оригинальном Веб-графе. Они объяснили, что BrowseRank улучшает производительность по причине того, что алгоритм может лучше отражать предпочтения пользователей по сравнению с PageRank и TrustRank. Однако по-прежнему неясно, что именно вносит свой вклад в производительность: конструктивные особенности алгоритма или непосредственно использование данных о поведении пользователей. Поэтому мы решили протестировать PageRank, TrustRank и BrowseRank на одном и том же графе BG(V,E). Это сравнение проводилось только на графе BG(V,E), так как расчёт BrowseRank требует информацию о длительности посещения, что применимо только на графе BG(V,E). PageRank работает на BG(V,E) лучше, чем на оригинальном веб-графе (Рисунок 5). Поэтому существует вероятность того, что BrowseRank имеет повышенную производительность просто потому, что используется на графе, построенном из данных о пользовательском поведении при сёрфинге. Результаты эксперимента на Рисунке 6 подтверждают это предположение. В свою очередь TrustRank показал наилучшие результаты как в идентификации спамовых, так и высококачественных страниц, в то время как PageRank немного превосходит прочие алгоритмы только в попарном тестировании. Высокая производительность TrustRank, возможно, обеспечивается предварительным данными в трастовой выборке.

Рисунок 6.

Рисунок 6. Результаты оценки качества разными алгоритмами ссылочного анализа на графе BG(V,E).

По результатам эксперимента TrustRank превосходит BrowseRank на 4.12% и 2.84% в идентификации высококачественных и спамовых страниц, соответственно. Улучшения в производительности невелики, но, тем не менее, наглядно демонстрируют, что алгоритм TrustRank так же может быть весьма эффективен на графе BG(V,E). Алгоритм PageRank работает не хуже BrowseRank во всех тестах. Это означает, что улучшение производительности, заявленное в [23], обеспечивается и самим принципом алгоритма, и что, вероятно важнее, использованием информации о пользовательском поведении. Кроме того, PageRank и TrustRank эффективнее BrowseRank, так как они не требуют сбора данных о длительности визита каждого пользователя.

Эти результаты и примеры показывают, что хоть BrowseRank и разработан специально для BG(V,E), он не работает лучше PageRank, TrustRank и DiffusionRank на данном графе. BrowseRank отдаёт предпочтение страницам, на которых пользователи проводят больше времени, но длительность визита необязательно отражает предпочтение пользователя и качество страницы. В сравнении с принципом алгоритма, включение в анализ данных о пользовательском поведении при построении ссылочных графов, возможно, является более важным.

6.4 UserPageRank и UserTrustRank на графе сёрфинга пользователя

В Разделе 3 мы предположили, что алгоритмы UserPageRank и UserTrustRank, модифицирующие соответствующие оригиналы путём введения расчёта P (Xi ⇒ Xj) по данным о пользовательском поведении, записанным в BG(V,E). Для изучения эффективности этих алгоритмов мы сравнили их производительность с оригинальными алгоритмами PageRank/TrustRank (Рисунок 7).

Рисунок 7.

Рисунок 7. Результаты оценки качества исходными алгоритмами PageRank/TrustRank и UserPageRank/UserTrustRank на графе BG(V,E).

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

Примером спамового сайта являлся URL 11sss11xp.org. Среди 2279 веб-сайтов в тестовой выборке ROC/AUC, данный URL был ранжирован на 1030-ю позицию оригинальным TrustRank и 1672-ю позицию его модификацией – UserTrustRank. Так как спамовый сайт должен ранжироваться ниже всего, очевидно, что модификация алгоритма сработала лучше в данном случае. Мы провели исследование гиперссылочной структуры этого сайта, чтобы понять, почему UserTrustRank сработал лучше.

Сайт-источник Сайт-цель Число визитов пользователей
web.gougou.com 11sss11xp.org 3
image.baidu.com 11sss11xp.org 1
yahoo.cn 11sss11xp.org 1
domainhelp.search.com 11sss11xp.org 1
my.51.com 11sss11xp.org 1

Таблица 9. Веб-сайты, ссылающиеся на спамовый сайт 11sss11xp.org в графе BG(V,E).

Сайт Число исходящих ссылок Число визитов пользователей
yahoo.cn 35,000 208,658
my.51.com 86,295 19,443,717
image.baidu.com 148,611 8,218,706

Таблица 10. Характеристики сайтов, ссылающихся на спамовый сайт 11sss11xp.org.

По таблицам 9 и 10 можно заметить, что данный сайт получил множество входящих ссылок от поисковых систем (yahoo.cn и image.baidu.com). Данное явление объясняется спецификой разработки спам-сайта, нацеленной на получение неоправданно высоких оценок поисковыми системами. Кроме того, данный сайт так же получал входящие ссылки от нескольких сайтов Web 2.0, таких как сервис блогов my.51.com. В оригинальном алгоритме TrustRank оценки оригинальных сайтов должны равномерно распределяться по исходящим ссылкам. В отличие от оригинала, модификация UserTrustRank назначает оценки путём расчёта P (Xi ⇒ Xj) вероятности посещения сайта Xj после посещения Xi. Так как пользователи добровольно не посещают спамовые сайты, вероятность P (Xi ⇒ Xj) должна иметь весьма малое значение. К примеру, на yahoo.cn размещено 35,000 исходящих ссылок в графе BG(V,E). В целом по этим ссылкам было совершено 208,658 кликов пользователями и только один из кликов вёл на 11sss11xp.org. Оригинальный TrustRank даёт этому сайту 1/35000 оценки траста Yahoo, в то время как UserTrustRank назначает только 1/208658 траста. UserTrustRank назначает оценку траста в соответствии с количеством переходов, таким образом, существенно улучшая идентификацию спамовых сайтов.

6.5 UserPageRank и UserTrustRank на социальном графе

Для более глубокого изучения эффективности UserPageRank и UserTrustRank мы сконструировали социальный граф, описанный в Разделе 3 и анализировали работу алгоритмов.

Данные были собраны в сентябре 2011 с weibo.com, крупнейшей социальной сети Китая. Выборка содержала информацию о 2,631,342 пользователях и 3.6 млрд связей между ними. Насколько нам известно, эта выборка являлась одним из самых крупных корпусов, задействованных в изучении социальных сетей. Типы анализируемых данных сведены в Таблицу 11.

Данные Описание
ID пользователя Уникальный идентификатор каждого пользователя
Имя пользователя Имя пользователя
Подтверждённый аккаунт Подтвержден ли аккаунт администрацией weibo.com
Читает Список ID, за которыми следит пользователь
Фолловеры Список ID, которые читают пользователя
Тэги Список интересов пользователя в графе «О себе»

Таблица 11. Информация, записанная в собранных данных микро-блоггинга.

Как описывалось ранее в Разделе 3, UserPageRank и UserTrustRank требуют расчёта P(XiXj). В процессе создания социального графа мы решили ввести несколько распространённых тегов для выявления пользователей со схожими интересами. Мы считаем, что это допущение адекватно, так как данные об отношениях пользователей со схожими интересами надёжнее формируют социальную картину. Поэтому вес ребра в социальном графе эквивалентен числу общих тегов между узлами, которые оно соединяет. Применив UserPageRank и UserTrustRank на взвешенный социальный граф были получены оценки социального влияния. Результаты показаны на Рис. 8.

Рисунок 8.

Рисунок 8. Результаты оценок социального влияния исходными алгоритмами PageRank/TrustRank и UserPageRank/UserTrustRank на социальном графе weibo.com.

Рисунок 8 иллюстрирует эффективность AUC различных алгоритмов оценки влияния на социальном графе. В нашей оценки принято считать пользователей с подтверждёнными аккаунтами более влиятельными, так как их личность была удостоверена weibo.com: в соответствии с их политикой верификации только «авторитетные» лица или организации получают подтверждение аккаунта. Трастовая выборка для TrustRank и UserTrustRank была создана из «Зала Славы Weibo», откуда мы выбрали 100 человек. В «Зал Славы Weibo» включено множество известных персон из различных областей, например, развлекательной сферы, политики или индустрии.

По результатам на Рисунке 8 видно, что эффективность PageRank, UserPageRank и UserTrustRank примерно одинакова, а оригинальный TrustRank имеет самый слабый результат среди всех алгоритмов. Несмотря на то, что эффективность AUC PageRank практически идентична с UserPageRank и UserTrustRank, алгоритмы имеют серьёзные отличия в списках ранжирования. Топовые результаты работы алгоритмов в Таблице 12 показывают, что и PageRank и TrustRank высоко котируют поп-звёзд (таких как Xidi Xu, Chen Yao и Mi Yang). В то же время UserPageRank и UserTrustRank отдают предпочтение аккаунтам, на которых размещаются остроумные шутки, цитаты и афоризмы.

Позиция PageRank UserPageRank TrustRank UserTrustRank
1 Kangyong Cai Шутки Kangyong Cai Kangyong Cai
2 Xidi Xu Kangyong Cai Mi Yang Шутки
3 Чёрный юмор Классические цитаты Na Xie Xiaoxian Zhang
4 Chen Yao Чёрный юмор Weiqi Fan Классические цитаты
5 Xiaogang Feng Мода Lihong Wang Чёрный юмор

Таблица 12. Топ-5 результатов по алгоритмам PageRank, TrustRank, UserPageRank и UserTrustRank на социальном графе weibo.com.

Различия в ранжировании топовых результатов вызваны тем, что, несмотря на наличие множества подписчиков у знаменитостей, большая часть фолловеров не имеют общих тегов с поп-звёздами. К тому же многие знаменитости (например, Xidi Xu и Chen Yao) не добавляют никаких тегов и подробной информации о своих интересах к себе на страницу. Пользователи подписываются на паблики юмористической направленности и классических цитат, так как подобная информация пользуется спросом и оказывает влияние на мнение людей. По этой причине мы считаем, что UserPageRank и UserTrustRank показывают наиболее адекватную оценку социального влияния.

7. Заключение и будущие исследования

Адекватная оценка качества страницы по-прежнему является сложнейшей задачей для поисковых систем. Алгоритмы ссылочного анализа далеко продвинулись в этой сфере, однако и они сталкиваются со всё более сложными проблемами в реальной среде Веба. В данной работе мы исследуем пользовательское поведение и предлагаем два алгоритма гиперссылочного анализа, основанных на модели «сёрфинга с предварительным знаниями» вместо модели случайного блуждания пользователя. Мы так же строим надёжные ссылочные графы, в которые включается информация о пользовательском поведении. Было разработано три алгоритма конструирования для создания трёх различных типов ссылочных графов (BG(V,E), user-HG(V,E) и user-CG(V,E)). Мы исследовали структуру этих графов и обнаружили, что они наследуют от оригинального Веб-графа такие характеристики, как, например, степенной закон распределения исходов и заходов. Кроме того, проводилось изучение эволюции данных графов, в процессе которого подтвердилась адекватность их использования для оценки качества страниц поисковыми системами.

Результаты эксперимента показали, что графы, созданные с использованием данных о поведении пользователей являются более эффективными по сравнению с оригинальным Веб-графом при решении задачи по оценке качества веб-страницы. PageRank по BG(V,E), user-HG(V,E) и user-CG(V,E) превосходит PageRank по всему Веб-графу. Кроме того, user-HG(V,E) и user-CG(V,E) работают лучше графа BG(V,E), возможно, в силу того, что BG(V,E) в процессе своего создания пропускает множество важных гиперссылок. Мы так же выяснили, что PageRank, TrustRank и DiffusionRank не менее (а иногда и более) эффективны, чем BrowseRank, когда они применяются на одном и том же графе (BG(V,E)). Это наблюдение наглядно демонстрирует, что использование данных о пользовательском поведении может быть на порядок важнее выбора алгоритма ссылочного анализа. К тому же, создание графов сёрфинга пользователей предоставляет дополнительную информацию. Таким образом, возможно провести модификацию исходных алгоритмов TrustRank/PageRank, дополнив их методом оценки важности исходящих ссылок. Модификации алгоритмов (UserPageRank и UserTrustRank) более эффективны как в идентификации спама, так и в оценке социального влияния.

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

Однако остаются нерешёнными несколько вопросов технического плана, которые мы будем исследовать в будущих работах:

Во-первых, веб-страницы, посещаемые пользователями составляют лишь малую долю от всех страниц в Интернете. И хотя было выяснено, что большинство страниц, которые требуются пользователям могут быть включены в набор вершин графа BG(V,E), поисковым системам всё ещё требуется хранить намного больший объём страниц в индексе, чтобы удовлетворить все потенциальные нужды пользователей. Для оценки качества этих страниц мы хотим прогнозировать предпочтения пользователей для каждого документа, используя ранее посещённые пользователем страницы как обучающую выборку. Если мы сумеем рассчитать вероятность того, что веб-страниц будет посещена пользователями в будущем, то станет возможным построить надёжный ссылочный граф крупного масштаба, который не будет ограничен рамками пользовательского поведения.

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

Благодарности

Данное исследование получило поддержку от организаций Natural Science Foundation (60903107, 61073071) и National High Technology Research and Development (863) Program (2011AA01A207) в Китае. На ранних этапах работы существенный вклад внес Yijiang Jin. Мы выражаем благодарность Jianli Ni за любезное оказание помощи по сбору информации и созданию корпуса данных. Так же мы благодарим Tao Hong, Fei Ma и Shouke Qin из Baidu.com и всех анонимных рецензентов данной работы за их ценные комментарии и предложения.

Биография автора

Фотография автора Yiqun Liu.

Yiqun Liu родился в январе 1981 года. В 2003 году получил степень бакалавра, а в 2007 – Доктора философии на факультете Computer Science and Technology в университете Tsinghua. На сегодняшний день работает доцентом в университете Tsinghua и куратором студентов факультета C.S.&T. Его исследовательские интересы включают в себя информационный поиск, анализ пользовательского поведения и оценка производительности онлайн-сервисов. Большинство последних работ и публикаций может быть найдено на домашний странице по адресу thuir.cn/group/~YQLiu/

Ссылки 

[1] В. Amento, L. Terveen, W. Hill, Does authority mean quality? Predicting expert quality ratings of Web documents. In Proc. of 23rd ACM SIGIR Conference (2000) 296-303

[2] L. Becchetti, C. Castillo, D. Donato, S. Leonardi, R. Baeza-Yates, Using Rank Propagation and Probabilistic Counting for Link Based Spam Detection. Proceedings of the Workshop on Web Mining and Web Usage Analysis (2006).

[3] M.Bendersky, W. Bruce Croft, Y. Diao, 2011. Quality-biased ranking of web documents. In Proceedings of the fourth ACM international conference on Web search and data mining (WSDM ’11). ACM, New York, NY, USA, 95-104.

[4] M. Bilenko, R. W. White, Mining the search trails of surfing crowds: identifying relevant Web sites from user activity. In Proc. the 17th WWW Conference. (2008) 51-60.

[5] S. Brin, L. Page, The anatomy of a large-scale hypertextual Web search engine. Comput.Netw. ISDN System 30 (1998), 107-117.

[6] A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, J. Wiener, Graph structure in the Web. Computer Networks 33 (2000) 309-320.

[7] M. Chau, H. Chen, A machine learning approach to web page filtering using content and structure analysis. Decision Support Systems, 44(2) (2008) 482-494.

[8] N. Craswell, D. Hawking, S. Robertson, Effective site finding using link anchor information. Proceedings of the 24th ACM SIGIR Conference (2001) 250-257.

[9] D. Donato, L. Laura, S. Leonardi, S. Millozzi, The Web as a graph: How far we are. ACM Transaction on Internet Technology 7(1) (2007), 4.

[10] X. Fang, С. W. Holsapple, An empirical study of web site navigation structures’ impacts on web site usability, Decision Support Systems, 43(2) (2007) 476-491.

[11] Z. Gyongyi, H. Garcia-Molina, J. Pedersen, Combating web spam with trustrank. In Proceedings of the Thirtieth international VLDB Conference (2004) 576-587.

[12] T. Haveliwala, Efficient computation of PageRank. Technical Report, Stanford University, 1999. dbpubs.stanford.cdu/pub/l999-31

[13]T. Haveliwala, 2003. Topic-sensitive pagerank: A context-sensitive ranking algorithm for Web search. IEEE Transaction on Knowledge and Data Engineering. 15,4, 784-796.

[14] T. Haveliwala, S. Kamvar, G. Jeh, An analytical comparison of approaches to personalizing PageRank. Stanford Technical Report, ilpubs.stanford.edu:8090/596/

[15] M. R. Henzinger, R. Motwani, C. Silverstein, 2002. Challenges in web search engines. SIGIR Forum 36, 2 (Sep. 2002), 11-22.

[16] A. Jacob, C. Olivier C. Carlos, WITCH: A New Approach to Web Spam Detection. Yahoo! Research Report No. YR-2008-001. (2008).

[17] Y. Kang, Y. Kim, Do visitors’ interest level and perceived quantity of web page content matter in shaping the attitude toward a web site? Decision Support Systems, 42(2) (2006) 1187-1202.

[18] R. Kaul, Y. Yun, S. Kim, Ranking billions of web pages using diodes. Communications of the ACM, 52(8) (2009), 132-136.

[19] J. M. Kleinberg, Authoritative sources in a hyperlinked environment. Journal of ACM 46(5) (1999) 604-632.

[20] V. Krishnan, R. Raj, Web Spam Detection with Anti-TrustRank. In the 2nd International Workshop on Adversarial Information Retrieval on the Web, (2006).

[21] R. Kumar, P. Raghavan, S. Rajagopalan, A. Tomkins, Core algorithms in the CLEVER system, in ACM Transactions on Internet Technology 6(2) (2006) 131-152.

[22] Y. Liu, F. Chen, W. Kong, H. Yu, M. Zhang, S. Ma, L. Ru. Identifying Web Spam with the Wisdom of the Crowds. ACM Transaction on the Web. Volume 6, Issue 1, Article No. 2, 30 pages. March 2012.

[23] Y. Liu, B. Gao, T. Liu, Y. Zhang, Z. Ma, S. He, H. Li, BrowseRank: letting web users vote for page importance. In Proc. of 31st ACM SIGIR Conference (2008) 451-458.

[24] Y. Liu, M. Zhang, R. Cen, L. Ru, L., S. Ma, Data cleansing for Web information retrieval using query independent features. Journal of the American Society for Information Science and Technology, 58(12) (2007), 1884-1898.

[25] L. Page, S. Brin, R. Motwani, T. Winograd, The PageRank citation ranking: bringing order to the Web. Stanford Technical Report. (1999) ilpubs.stanford.edu:8090/422/.

[26] H. Wu, M. Gordon, K. DeMaagd, W. Fan, Mining web navigations for intelligence. Decision Support Systems, 41(3) (2006) 574-591.

[27] D. Xu, Y. Liu, M. Zhang, L. Ru, S. Ma. Predicting Epidemic Tendency through Search Behavior Analysis. In Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI-11) (Barcelona, Spain), pp. 2361-2366.

[28] H. Yang, I. King, M.R. Lyu, DiffusionRank: A Possible Penicillin for Web Spamming. In Proc. of 30th ACM SIGIR Conference (2007) 431-438.

[29] В. Zhou, Y. Liu, M. Zhang, Y. Jin, S. Ma, Incorporating Web Browsing Information into Anchor Texts for Web Search, Information Retrieval Volume 14, Issue 3: 290-314, 2011.

Перевод материала «Constructing a Reliable Web Graph with Information on Browsing Behavior» выполнили Константин Скоморохов и Роман Мурашов

Полезная информация по продвижению сайтов:

Перейти ко всей информации