Навігація
Головна
ПОСЛУГИ
Авторизація/Реєстрація
Реклама на сайті
 
Головна arrow Інформатика arrow Моделирование сложных сетей
< Попередня   ЗМІСТ   Наступна >

Алгоритм PageRank

Алгоритм PageRank был придуман компании Google для ранжирования веб-страниц. Он получил название по фамилии одного из его изобретателей Лари Пейджа (Larry Page).

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

Алгоритм PageRank близок по идеологии к литературному индексу цитирования, который рассчитывается для произвольного документа с учетом количества ссылок от других документов на данный документ, но при этом в PageRank как и в HITS, в отличие от литературного индекса цитирования, не все ссылки считаются равнозначными.

Принцип рассчета ранга веб-страницы РаgeRаnк следующий: рассматривается модель - процесс, при котором некоторый пользователь Интернет открывает случайную вебстраницу, с которой переходит по случайно выбранной гиперссылке. Потом он перемещается на другую вебстраницу и снова активизирует случайную гиперссылку и т. д., постоянно переходя от страницы к странице, никогда не возвращаясь. Иногда ему такое блуждание надоедает, и он снова переходит на случайную веб-страницу - не по ссылке, основателями а набрав вручную некоторый URL. В этом случае вероятность того, что блуждающий в Сети пользователь перейдет на некоторую определенную веб-страницу - это ее ранг. Очевидно, PageRank веб-страницы тем выше, чем больше других страниц ссылается на нее, и чем эти страницы популярнее.

Пусть есть n страниц D = {dj, dn}, которые ссылаются на данный документ (веб-страницу A) , а C(A) общее число ссылок с веб-страницы A на другие документы. В соответствии с приведенной моделью поведения пользователя определяется некоторое фиксированное значение δ (damping factor) как вероятность того, что пользователь, пересматривая какую-нибудь вебстраницу из множества D , перейдет на страницу A по ссылке, а не набирая ее URL в явном виде. В рамках модели вероятность продолжения этим пользователем веб-серфинга по сети из N веб-страниц без использования гиперссылок, путем ручного ввода адреса (URL) со случайной страницы составит 1— δ (альтернатива перехода по гиперссылкам). Индекс PageRank PR(A) для страницы A

рассматривается как вероятность того, что пользователь окажется в некоторый случайный момент времени на этой странице:

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

Несмотря на различия HITS и PageRank, в этих алгоритмах общее то, что авторитетность (вес) узла зависит от веса других узлов, а уровень "посредника" зависит от того, насколько авторитетны узлы, на которые он ссылается.

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

Проиллюстрируем вышесказанное на примере. Рассмотрим небольшую часть сети, состоящую из узлов А с рангом гА = 0.5 , В с рангом гв = 0.3 и определим ранг узла С см. рис 2.3.1.

Фрагмент сети

Рис. 2.3.1 - Фрагмент сети

Каждый из узлов сети А и В ссылается на узел С и для них ранг уже известен. Узел А при этом ссылается еще на три узла, а узел В еще на два узла. Чтобы вычислить ранг узла С ранги каждого узла, ссылающегося на С, делятся на общее количество ссылок для этого узла, после чего полученные значения складываются.

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

множества узлов, ранги которых еще неизвестны? Решение состоит в том, чтобы присвоить всем узлам произвольный начальный ранг и провести несколько итераций.

В общем виде можно записать следующую формулу для (п +1) -ого шага итерации:

где суммирование по 7е Е(У) означает суммирование по всем узлам, которые имеют ссылку на У -й узел, а коШ7 -число исходящих связей для узла ]. В матричном виде (2.3.6) записывается следующим образом:

где

- нормализованная матрица инцидентности и А - матрица инцидентности сети.

Для итерационного процесса (2.3.7) возникает ряд вопросов, а именно:

— Сходится ли данный процесс?

Какими свойствами должна обладать матрица чтобы процесс гарантировано сходился?

H, Зависит ли конечный вектор

от начальных условий?

Рассмотрим два простых примера. Первый:

Пример 1

Рис. 2.3.2 - Пример 1

После выполнения итераций (2.3.7) получаем:

Итерация

0

1

2

3

Ранг узла

1

1

0

0

0

2

0

1

0

0

Результат явно не соответствует ожиданиям. Рассмотрим еще один, похожий пример.

Пример 2

Рис. 2.3.3 - Пример 2

Здесь получаем следующую таблицу:

Итерация

0

1

2

3

Ранг узла

1

1

0

1

0

2

0

1

0

1

Из приведенной таблицы видно, что сходимости процесса не наблюдается. Можно привести еще много контрпримеров, показывающих ограниченность формулы (2.3.8). С другой стороны, можно увидеть что (2.3.8) напоминает "power method" для вычисления собственного вектора матрицы H (соответствующего собственному значению - единица) примененному к Марковским цепям с матрицей вероятностей переходов P = H . В данном случае речь идет о "левом" собственном векторе. А поскольку теория Марковских цепей очень хорошо изучена, то можно сразу ответить на вопрос каким свойствам должна удовлетворять матрица вероятностей переходов P , чтобы процесс сходился, не зависел от начальных условий и т.д.

Матрица вероятностей переходов должна быть стохастической, неприводимой и непериодической. Первое условие удовлетворяется путем перехода к матрице S .

где a, = 1 если из i-ого узла не выходит ни одна связь (так называемый "dangling node") и равен нулю в другом случае, e - вектор состоящей из n единиц, n - число узлов в сети. И чтобы удовлетворить оставшимся двум условиям запишем матрицу G:

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

Рассмотрим первый контрпример. Для него:

Из (2.3.10) получаем матрицу О (для определенности положим а= 0 85 ).

Находим левые собственные значения матрицы О.

Видно, что второй узел более значимый, нежели первый, что полностью соответствует интуитивному представлению. Т.к. первый узел ссылается на второй (см. рис. 2.3.2). Совершенно аналогично для второго контрпримера получаем следующие ранги:

Как и должно было быть (см рис. 2.3.3), мы получили равнозначные значения для рангов.

Рассмотрим более сложный пример сети, изображенный на рис. 2.3.4.

Пример сети Запишем матрицу Н и вектор а для этой сети.

Рис. 2.3.4 - Пример сети Запишем матрицу Н и вектор а для этой сети.

Найдем матрицу О, взяв а= 0.85 :

Находим левый собственный вектор (для собственного значения - единица):

Для наглядности перенумеруем узлы в соответствии с их рангами - первый номер присвоим узлу с самым большим рангом - см. рис. 2.3.5.

Можно отметить, что без вычислений (интуитивно) даже такую несложную сеть практически невозможно ранжировать.

Сеть с ранжированными узлами

Рис. 2.3.5 - Сеть с ранжированными узлами

 
Якщо Ви помітили помилку в тексті позначте слово та натисніть Shift + Enter
< Попередня   ЗМІСТ   Наступна >
 
Дисципліни
Агропромисловість
Банківська справа
БЖД
Бухоблік та Аудит
Географія
Документознавство
Екологія
Економіка
Етика та Естетика
Журналістика
Інвестування
Інформатика
Історія
Культурологія
Література
Логіка
Логістика
Маркетинг
Медицина
Менеджмент
Нерухомість
Педагогіка
Політологія
Політекономія
Право
Природознавство
Психологія
Релігієзнавство
Риторика
РПС
Соціологія
Статистика
Страхова справа
Техніка
Товарознавство
Туризм
Філософія
Фінанси
Інші