Ранжирование web-страниц с использова нием взаимной информации между гиперссылками

УДК 004.738.52

РАНЖИРОВАНИЕ WEB-СТРАНИЦ С ИСПОЛЬЗОВАНИЕМ ВЗАИМНОЙ ИНФОРМАЦИИ МЕЖДУ ГИПЕРССЫЛКАМИ

P.M. Алгулиев, P.M. Алыгулиев

Институт информационных технологий Национальной академии наук Азербайджана, г. Баку

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

ВВЕДЕНИЕ

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

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

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

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

На сегодня разработаны некоторые алгоритмы для решения упомянутой проблемы. Среди них наиболее популярны алгоритмы PageRank [1, 2], HITS (Hypertext Induced Topic Search) [3] и SALSA (Stochastic Approach for Link Structure Analysis) [4]. Известные поисковые машины — Google, Yahoo и др. — в той или иной степени используют эти алгоритмы. Алгоритмы PageRank и HITS ранг web-страниц вычисляют итеративно. Алгоритм HITS с помощью обычных методов информационного поиска сначала идентифицирует web-страницы, релевантные запросу пользователя, а затем упорядочивает их таким образом, чтобы самые релевантные web-страницы были представлены в верхней части списка. Другой алгоритм PageRank ранжирует целые связанные гиперссылками web-страницы, затем среди них выбирает страницы, релевантные запросу пользователя, сохраняя при этом их ранги. Алгоритм SALSA является комбинацией алгоритмов PageRank и HITS.

Настоящая статья посвящена усовершенствованию алгоритма PageRank, где предлагаются три модификации.

1. КРАТКИЙ ОБЗОР АЛГОРИТМОВ PAGERANK И HITS

Основные обозначения:

G (W, E) — ориентированный web-граф;

W — множество web-страниц;

E — множество гиперссылок; u ^ v— гиперссылка из страницы u в страницу v;

B(u) = {v : v ^ u} — множество страниц, которые ссылаются на страницу и (Backwards links);

F(u) = {v : v ^ u} — множество страниц, на которые ссылается страница u (Forwards links); n — общее число страниц в web-графе G( W, E); PR(u) — PageRank страницы u;

A(u) — ранг страницы u как «авторитет»;

H(u) — ранг страницы u как «концентратор»; \U | — мощность множества U; sim(u, v) — мера близости страниц u и v, которая определяется метрикой косинуса; ra(v ^ u) — вес гиперссылки u ^ v; r (q, t)— степень релевантности запроса q тематике T.

Для извлечения информации из структуры гиперссылок и перекрестных ссылок, отслеживания дефектов их структуры, анализа связей между ссылками и объектами ссылок (Web Structure Mining) широко применяется алгоритм PageRank. Это статический алгоритм, предназначенный для оценки качества страниц, не зависящий от каких-либо запросов, т. е. с его помощью вычисляется «глобальная значимость» страниц. Суть алгоритма заключается в следующем. Представьте себе случайного пользователя, перемещающегося по Web. Пусть пользователь посещает страницу v. На каждом шаге пользователь либо «перепрыгивает» на другую страницу в Web, выбранную случайным образом, либо он следует по гиперссылке на текущей странице, при этом не возвращаясь и не посещая одну и ту же страницу дважды. Если через (1 — d) обозначить вероятность случайного прыжка, то вероятность перехода по ссылке будет d. Таким образом, показатель PageRank страницы u можно вычислить по следующей рекурсивной формуле:

RP

n v e B(u) lF(v)l

В правой части 1/n соответствует тому, что среди n страниц каждая страница выбирается с одинаковой вероятностью. Здесь также предпо-

лагается, что исходящие ссылки на странице v выбираются с одинаковой вероятностью, равной 1/|F(v)|. Для сходимости процесса (1) вероятность d (ее называют коэффициентом демпфирования [1, 2]) выбирается из интервала d є [0,8; 1]. Из алгоритма (1) видно, что чем больше ссылок на страницу, тем она становится «важнее».

Алгоритм HITS [3], как и алгоритм PageRank, основан на анализе web-структуры, но в отличие от него у каждой страницы выделяются две роли: роль «авторитета» (authority) и роль «концентратора» (hub). Алгоритм HITS, анализируя входящие и исходящие гиперссылки, ранжирует web-страницы. По этому алгоритму страница, на которую ссылаются другие страницы, называется «авторитетом», а страница, которая ссылается на другие страницы, называется «концентратором»:

A(u) = X H(v),

v є B

H(u) = X A(v).

v є F

Цель алгоритма HITS заключается в поиске наиболее качественных «авторитетов» и наиболее качественных «концентраторов». Из формул (2) и (3) видно, что для каждой страницы алгоритм HITS вычисляет два ранга: ранг A(u), показывающий качество страницы как «авторитета», и ранг H(u), показывающий качество страницы как «концентратора». Как и в алгоритме PageRank, в первом приближении рангам страниц присваивается произвольное ненулевое значение и затем производится итерационный процесс, состоящий из последовательного применения операций (2) и (3).

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

Для улучшения качества ранжирования предложены некоторые модифицированные варианты алгоритмов PageRank и HITS. Далее приводятся некоторые модифицированные варианты алгоритма PageRank.

Например, при ранжировании web-страниц алгоритм Topic-Centric [5] учитывает меру близости страниц:

PR

sim

PR

X sim

x є F

Согласно определению, sim(u, v) = 1 соответствует максимальной близости страниц и и v, а sim(u, v) = 0 — их полному различию.

В алгоритме TSPR (Topic-Sensitive PageRank) [6] web-страницы сначала группируются по тематике, а потом на каждом тематическом разделе вычисляется ранг страницы. Тематические разделы отбираются из верхнего уровня ODP (Open Directory Project). Пусть Uk означает множество URL-адресатов страниц в тематическом разделе Tk. При вычислении PageRank вектора для тематического раздела Tk алгоритм TSPR предполагает, что случайный пользователь двигается (следует по гиперссылкам или «прыгает») только по страницам из множества Uk, т. е. не выходит за рамки тематики. Тогда показатель PageRank страницы u на тематическом разделе Tk будет определен так:

PR(v ) I -( v) I

+

+

v є B

( 1 - d)/| Uk, если u 0, если u g U^.

U

k ,

Тогда зависящий от запроса показатель значимости (query sensitive importance score) страницы u

Sq(u) = I PRk(u)r (q, Tk).

k

Подчеркнем, что результат поиска ранжируется с учетом этих счетов.

В модели Intelligent Surfer [7] для вычисления ранга страницы u, зависящего от запроса q, алгоритм PageRank преобразуется к следующему виду:

PR» =

q X r

+

+ d X

x є W

r

^ PRq(v).

v e B

У e F

В моделях Topical PageRank и Topical HITS [8] каждой странице u сопоставляется два вектора: контент-вектор C(u) и авторитет-вектор A(u).

Контент-вектор Cu: [C(ux), ...,C(u'), ..., C(um)] является вероятностью распределения контента страницы u, где компонента C(u') представляет собой относительный вклад /-го тематического раздела в контент страницы u.

Авторитет-вектор Au: [A(ux), ..., A(u'), ..., A(um)] определяет степень значимости страницы u по те-магическим разделам, где компонента A(u') определяет степень значимости страницы u относительно /-го тематического раздела (как известно, в алгоритме HITS, кроме авторитет-вектора определяется и концентратор-вектор).

Степень значимости A(u') страницы u на /-м тематическом разделе вычисляется таким образом:

A(u!) = d(1 - а) X

1

B(и ) lF( v )l

A(v') +

+ da X

+

C(u‘) X X A(vk),

n vє Gkє T

где / е Т = {1, 2, ..., т}, а — вероятность перехода пользователя на /-й тематический раздел на странице.

Пусть А(у) = X А(/) и X А(у) = 1, тогда

к е Т V е О

формула (5) примет более компактный вид:

,) = ^ X (1 - а)А( 1'') + а С(у')А(у) +

V еХ( и) 1Д V)|

+

C(u').

Когда на странице тематические переходы скрыты, т. е. при a = 0, данная модель сводится к оригинальному PageRank-алгоритму.

В Topical HITS-алгоритме зависимость между векторами A(u) и H(u) задается следующими соотношениями:

A(u') = X

v є B

tf(v‘) = X

v є F

FI :

где H(v) = X H(/) и A(u) = X A(uk). k є T k є T

В случае, когда страница не разбита на тематические разделы, т. е. если на странице тематические детали скрыты, эта модель сводится к нормализованному алгоритму HITS или упрощенному варианту алгоритма SALSA [4]:

A(u) = X г-))--!

v є B(и) lF(v)l

1

H(v),

H(v) = X

і A(u).

v є F(u) lB(v)l

В работе [9] была предложена модель WPSS (Web Page Scoring Systems), обобщающая все вышеупомянутые модели. Прежде чем произвести

n

ранжирование, алгоритм WICER (Weighted InterCluster Edge Rank) [10] предлагает кластеризацию страниц по тематике. Для уточнения весов гиперссылок в алгоритме WLRank (Weighted Links Rank) [11] предлагается учитывать различные атрибуты. А именно, полагается, что атрибуты — tag, anchor text и др. — дают гиперссылкам дополнительные веса, в результате чего улучшается точность поисковых машин.

Заметим, что во всех перечисленных работах главная цель — найти web-страницы с максимальным рангом, отвечающим потребностям пользователей. В этом контексте и работа [12] не исключение. Для нахождения web-страниц с максимальным рангом в ней, на основе теории потока в сетях, предложена оптимизационная модель ранжирования web-страниц, которая была сведена к задаче линейного программирования.

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

2. ТРИ МОДИФИКАЦИИ АЛГОРИТМА PAGERANK

Первая модификация. Как было отмечено, вероятность нахождения страницы с максимальным рангом непосредственно связана с выбором гиперссылок. В данной модификации для определения вероятности выбора гиперссылки используется точечная взаимная информация (Pointwise Mutual Information — PMI) [13]. При определении вероятности выбора гиперссылки точечной взаимной информацией учитывается, что если web-страницы указываются (цитируются) одной и той же страницей, то каждая гиперссылка (ссылочная страница) содержит долю информации о других гиперссылках (ссылочных страницах).

Пусть F(v) — множество страниц, на которые ссылается страница v. Тогда, следуя работе [13], точечная взаимная информация между гиперссылками v ^ u. и v ^ u. определяется формулой:

Интуитивно, точечной взаимной информацией между гиперссылками V ^ ы и V ^ ы. измеряется количество информации по отношению друг к другу.

Из определения (6) следует, что если вероятности выбора гиперссылок V ^ ы. и V ^ ы. незави-

* }

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

* }

независимы, то р(ы., ы.) = р(ы.)р(ы.) и, следова-

тельно,

g Г Р

g2 ^p ( u i )p(Uj

PMI(up u.) = log2 ( _*( ' ~ ч*’_ ( j ч ) = log21 = 0.

Для определения вероятности выбора гиперссылки V ^ ы*. вычисляется суммарная точечная взаимная информация РМДы*), которая определяется между ней и остальными исходящими гиперссылками страницы V, и общая точечная взаимная информация РМДД^), которая вычисляется между всевозможными парами гиперссылок, исходящими из страницы V.

Суммарную точечную взаимную информацию гиперссылки V ^ ы. будем определять формулой:

PMI(u;) = X PMI(up u.).

и, е F

Общая точечная взаимная информация PMI(F(v)) получается суммированием формулы (7):

PMI(F(v)) = X PM/(u;) =

и,- е F

= X X PMI(u;, u.).

и, е F

( р(ы', ы,) л

PMI

* 1 2 ^р( ы')р( и,.)/

где р(ы*)— вероятность цитирования страницы ы*. (вероятность следования пользователя по гиперссылке V ^ ы*), а р(ы*, ы.) — вероятность коцитиро-вания страниц ы; и ы. (совместная вероятность сле-

* }

дования пользователя по гиперссылкам V ^ ы*. и v ^ .

В дальнейшем для простоты записи вместо обозначения РМЛ^ ^ ы;, V ^ ы.) будем применять

* } обозначение РМ1(ы,., ы.).

Тогда доля ранга РР(^, которая распределяется по страницам ы*. е Р(^, т. е. вес гиперссылки V ^ ы*. будет вычисляться отношением формул (7) и (8):

ra(v ^ u.) =

PMI

X PMI

и, е F

X X PMI

и, е F

, u e F

Легко видеть, что если вероятности выбора ги-

Условная вероятностьp(u.|w.) определяется сог-

перссылок V ^ ы*. и V ^ ы. независимы, то приходим ласно формуле Байеса:

к неопределенности. Во избежание неопределенности формула (9) преобразуется к виду:

1 + X PM/

Uj g F

Uj Ui

I F( v) | X X pM/( и г-, j

U g F

P(uj |wk) =

ы* е /

Таким образом, оригинальный PageRank-алгоритм имеет вид:

РДы) = + й X «

п V е В

Из формулы (11), как следствие, легко можно получить оригинальный PageRank-алгоритм. Действительно, если предположить, что выбор гиперссылок независим, тогда из формулы (10) вытекает, что вероятность выбора каждой гиперссылки равна величине «(V ^ ы*) = 1/|Д^|, которая совпадает с вероятностью выбора гиперссылки в оригинальном PageRank-алгоритме, выраженным формулой (1).

Теперь переходим к вычислению вероятности р(ы*, ы.), которую можно определить так:

р

Поскольку каждая страница представляется как «мешок слов», то условная вероятность

к

р(ы/.1ыг) = х р. к = 1

где К означает общее число слов в наборе страниц {V} и /(V).

При допущении независимости появления слова wk в страницах ы*. и и. последнюю формулу можно выразить так:

к к

р(ы|ыг) = х р(ы* X P(ul' к = 1 к = 1

и формула (12) принимает вид:

к

р

к = 1

Пусть — число появления слова wk в странице ы*.. Тогда вероятность появления слова ^к в странице ы*

K

p(wk|u/) = fiJ X /&.

s = 1

p ( w*| Uj ) p ( Uj ) p( wk) :

где p(Wk) = X P(Wkl«i)p(«i).

i = 1

С учетом формул

p(u Uj) =

p

v

K

K

X

fjk 1 P ( )'

Подставляя последнее выражение в формулу (6), для точечной взаимной информации получим следующую формулу:

РМДи, U.) = log2

1

K

f't f't *, 1 p( w * >

KK

X 4 X fs

V s = 1 s = 1

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

ra+(v ^ u)[0, 1] и ra-(v ^ u).

Вес ra+(v ^ u) определяется числом входящих гиперссылок страницы u и ссылочных страниц страницы v:

ю (v ^ u) =

X |B(x)l

x g F

а вес « (V ^ ы) — числом исходящих гиперссылок страницы ы и всех страниц множества /(V):

ro-(v ^ U) = F k)l

x g F

С учетом формул (16) и (17) оригинальный PageRank-алгоритм модифицируется так [14]:

PR(u) = li^vk) +

+ й X «+С^ ^ ы)« (V ^ ы)РД^.

V е В

Как можно заметить из формул (16) и (17), в этой модификации не учитывается тематическая близость страниц. Для учета тематической близос-

ти страниц нами предлагаются следующие определения весов (16) и (17):

X sim

ra+

X X sim

y e F

X sim

ra-

X X sim

y e F

Если предположить, что для любой гиперссылки (х ^ у) мера подобия между страницами x и у принимает одно и то же значение, то из нашего определения, как следствие, получается результат работы [14]. Действительно, пусть для любой гиперссылки (х ^ у) sim(x, у) = а = const, тогда из формул (18) и (19) получаются соответствующие формулы (16) и (17).

Третья модификация. Предлагаемая модификация является усовершенствованным вариантом алгоритма Topic-Centric [5]. В отличие от алгоритма Topic-Centric в нашем варианте вероятность выбора гиперссылки не только зависит от степени близости страниц v и u е F(v), она также зависит от степени близости страниц множества F(v):

= (izud) + n

Xsim

PR

+ d X

v e B

x e F(v) x Ф u

X £ sim

x e F

х рад,

где о т х т 1.

Если влияние мер близости страниц множества /(V) свести к нулю, т. е. если в формуле (20) положить X = 1, то получается формула (4).

Можно предложить и другую модификацию:

РЯ(ы) = +

п

sim

х е Д V) х Ф и

+

d X

v e B

^ sim

x e F

y * x

PR(v).

ЗАКЛЮЧЕНИЕ

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

ностью. Проведенные эксперименты показали, что такой подход не гарантирует нахождение релевантных страниц, отвечающих потребностям пользователей. Одна из главных причин заключается в том, что в традиционных алгоритмах ранг страницы определяется числом гиперссылок. Дальнейшие исследования подтверждают, что без контентного анализа документов невозможно решить проблему эффективности поисковых машин. Эффективность поиска оценивается степенью релевантности отобранных документов к запросу пользователя. Для повышения эффективности поиска в работе предложены три модификации алгоритма PageRank. Каждая модификация при определении веса гиперссылки учитывает тематическую близость страниц и их соседей, связанных гиперссылками. Предложенные в данной статье модификации алгоритма PageRank представляют собой усовершенствованные варианты результатов работ [1, 2, 5, 14].

ЛИТЕРАТУРА

1. Br/n S., Page L. The anatomy of a large-scale hyper-textual Web search engine // Computer Networks and ISDN systems. — 1998. — Vol. 30, — N 1—7. — P. 107—117.

2. Berkh/n P. A survey on PageRank computing // Internet Mathematics. — 2005 — 2006. — Vol. 2, N 1. — P. 73—120.

3. Kle/nberg J.M Authoritative sources in a hyperlinked environment // Journal of the ACM. — 1999. — Vol. 46, N 5. — P. 604—632.

4. Lempel R., Moran S. SALSA: the stochastic approach for link-structure analysis // ACM Trans. on Information Systems. — 2001. — Vol. 19, N 2. — P. 131—160.

5. Ingongngam P., Rungsawang A. Topic-centric algorithm: a novel approach to Web link analysis // Proc. of the 18th Intern. Conf. on Advanced Information Networking and Applications (AINA'04). — Fukuoka, Japan, 2004. — Vol. 2. — P. 299— 301.

6. Havel/wala T.H. Topic-sensitive PageRank: a context-sensitive ranking algorithm for Web search // IEEE Trans. on Knowledge and Data Eng. — 2003. — Vol. 15, N 4. — P. 784—796.

7. R/chardson M., Dom/ngos P. The intelligent surfer: probabilistic combination of link and content information in PageRank // Advances in Neural Information Processing Systems. MIT Press. — 2002. — Vol. 14. — P. 1441—1448.

8. N/e L., Dav/son B. D., Q/ X. Topical link analysis for Web search // Proc. of the 29 Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. — Seattle, USA, 2006. — P. 91—98.

9. D/l/gent/ M., Gor/ M., Magg/n/ M A unified probabilistic framework for Web page scoring systems // IEEE Trans. on Knowledge and Data Engineering. — 2004. — Vol. 16, N 1. — P. 4—16.

10. Padmanabhan D., Des/kan P., Sr/vastava J. WICER: a weighted inter-cluster edge ranking for clustered graphs // Proc. of the 2005 IEEE/WIC/ACM Intern. Conf. on Web Intelligence (WI’2005). — Compiegne, France, 2005. — P. 522—528.

11. Baeza-Yates R... Dav/s E. Web page ranking using link attributes // Proc. of 13th World Wide Web Conference (WWW13). — New York, USA, 2004. — P. 328—329.

12. Алыгулиев Р.М Оптимизационная модель ранжирования Web-страниц // Системы управления и информационные технологии. — 2006. — № 3(25). — С. 4—7.

13. Efron M. Using cocitation information to estimate political orientation in Web documents // Knowledge and Information Systems. — 2006. — Vol. 9, N 4. — P. 492—511.

14. X/ng Ж, Ghorban/ A. Weighted PageRank algorithm // Proc. of the Second Annual Conf. Communication Networks and Services Research (CNSR'04). — Fredericton, Canada, 2004. — P. 305—314.

е-mail: rasim@science.az; a.ramiz@science.az

Статья представлена к публикации членом редколлегии

В.Л. Эпштейном.