публичный образовательный интернет-портал

Ссылочное ранжирование Пейджа. Как работает сердце Google?

20/12/2020
Ларри Пейдж
Ранжирование Пейджа. PageRank
Ранжирование Пэйджа

Интернет, сразу после его изобретения, напоминал несколько крупных каналов, по которым, как вода, текла информация. Дальше – больше. Информационные каналы превратились в информационные реки, затем в информационные моря и, наконец, Интернет оказалось позволительным сравнить с информационным океаном.

Подобное сравнение было очень хорошим, потому что пловцу в информационном океане стало возможным так же легко затеряться, как в океане обычном. По старинке записанные на библиотечные карточки адреса полезных сайтов походили на портуланы мореходов времен Христофора Колумба. Но подвиг Герарда Меркатора, для всеобщей пользы собравшего много таких портуланов в одном атласе, оказался не повторённым. Попытки свести все полезные адреса Интернета в книги на манер телефонных справочников «Жёлтые страницы», конечно были. Но книги эти устаревали ещё до выхода в свет. Появлялись новые полезные адреса, исчезали старые. Попытки поиска в сети с помощью этих толстенных справочников оказывались безнадежными.

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

К настоящему времени бóльшая часть этих поисковых серверов сошла с дистанции. Кто-то помнит ещё такие славные в прошлом имена поисковых систем, как Altavista, Excite, Lycos, Апорт и даже «Иван Сусанин»? Выдаваемые ими адреса, зачастую, плохо соответствовали запросу и не содержали искомой информации. Те же сайты, которые содержали действительно нужную информацию, находились в списке результатов далеко от первой строки, а иной раз и вовсе отсутствовали.

Интересно, что в 1999 году два аспиранта Стэнфордского университета, Сергей Брин и Ларри Пейдж, предложили руководству поисковика Excite разработанный ими алгоритм ранжирования Интернет-страниц. Цена вопроса, миллион долларов, показалась расчётливым менеджерам компании завышенной, и сделка не состоялась. Позже выяснилось, что аспиранты тоже не были обделены деловой хваткой и открыли собственную компанию Google, которая обеспечивала наиболее релевантный поиск Интернет-страниц.  Этим они прикончили почти все существовавшие до начала 21 века поисковики.

Релевантность ответа на запрос оказалась ключевым вопросом. Прежние поисковые системы сортировали найденные страницы по тому, сколько раз на странице упоминались искомые слова или термины.  Пейдж и Брин предложили новую технологию, которую они назвали PageRank (ранжирование Пейджа). Термин PageRank иногда переводят на русский язык, как «ранжирование страницы», но, согласно разъяснению самой компании Google, это – эпоним, происходящий от имени Ларри Пейджа. Английское слово «page» («страница») здесь не при чём.

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

Критерий ранжирования Пейджа немного напоминает широко известный индекс цитирования, используемый в наукометрии для оценки качества научной работы учёных. Учёный тем более успешен, чем больше работ других учёных ссылаются на его труды, с учётом того, что ссылки в престижных журналах «весят» больше. Такое сходство не удивительно, потому что проект Пейджа и Брина возник в рамках разработки цифровой библиотеки Стэнфордского университета.  

Модельная сеть, состоящая из трёх страниц
Рис. 1. Модельная сеть, состоящая из трёх страниц

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

Главные объекты линейной алгебры – векторы и матрицы. Методы линейной алгебры, которые изучают во всех технических высших учебных заведениях, позволяют выявить закономерности в массиве данных. Сложности растут с ростом размерности массивов. Для совокупности страниц Интернета размерности матриц, с которыми приходится оперировать, достигают десяток и сотен миллионов. Не стоит говорить, что вычисления в столь громоздких структурах требуют гигантского времени и мощных компьютеров. Зато и сложность задач возрастает! Можно, например, классифицировать человеческие лица или определить популярность Интернет-сайта. 

Как же действует алгоритм расчёта PageRank? Разберём это на упрощённой модели, содержащей только три страницы. На рис. 1 эта модель представлена математическим объектом, который называется графом. Страницы представлены в виде трёх кругов, узлов графа, обозначенных X, Y и Z. Ссылка с одной страницы на другую обозначается направленным вектором, стрелкой. Вектор этот будет направлен от страницы, содержащей ссылку, к той странице, на которую ссылка производится.

Страница X содержит две исходящие ссылки, на страницу Y и на страницу Z. Страница Y ссылается только на страницу Z. Тем временем страницы X и Z ссылаются друг на друга. Страница Z – с двумя входящими ссылками.

Назначим каждой странице PageRank, дробное число, находящееся в промежутке от 0 до 1. Это число и будет измерять «важность» страницы по отношению к другим. Сумма рангов по всей сети должна составлять 1. Определение рангов происходит по алгоритму, описанному ниже.

Алгоритм ранжирования начинается с некоторого предположения о ранге каждой страницы.  Изначально алгоритм присваивает всем страницам равные ранги. Всеобщее равенство! В нашем примере три страницы, поэтому для каждой страницы PageRank равен 1/3.

Затем начинается пересчёт рангов страниц. Пересчёт происходит пошагово. На каждом шаге с номером i для каждой страницы с номером j берется актуальное значение ранга R(i,j) и равномерно распределяется по всем страницам, на которые данная страница ссылается. Пересчёт прекращается, когда ранг страницы перестанет изменяться: R(i+1,j) = R(i,j).

i

X

Y

Z

0

0.33

0.33

0.33

1

0.33

0.17

0.50

2

0.50

0.17

0.33

3

0.33

0.25

0.42

4

0.42

0.17

0.42

5

0.42

0.21

0.38

6

0.38

0.21

0.42

7

0.42

0.19

0.40

8

0.40

0.21

0.40

9

0.40

0.20

0.41

10

0.41

0.20

0.40

11

0.40

0.20

0.40

 

Табл. 1. Первые 11 шагов процесса перераспределения рангов между страницами

В нашей модели из трёх страниц распределение рангов страниц будет происходить по следующим правилам, определённым конфигурацией графа на рис. 1.

X (i+1) = Z(i)

Y (i+1) = ½ X (i)

Z (i+1) = ½ X + Y(i)

Отсюда, учитывая, что для каждого шага будет верно равенство  

X (i) + Y (i) + Z(i) = 1

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

X (i+1) = X(i) = x

Y (i+1) = Y (i) = y

Z (i+1) = Z(i) = z

Откуда

x = z         y = ½ x     z = ½ x + y

2½ x =1   

 x = 2/5    y = 1/5    z = 2/5

Пошаговый процесс перераспределения рангов между страницами с разным числом ссылок представлен в таблице 1.

В маленькой модельной системе всё происходит просто и хорошо. Необходимые вычисления можно быстро произвести вручную или ещё быстрее с помощью программы вроде Excel. Но как только происходит выход на просторы Интернета, начинаются сложности. Количество переменных драматически возрастает, размерности обрабатываемых матриц исчисляются миллионами. И такие гигантские матрицы следует «прошерстить» ни один и ни два раза. Вызов? Несомненно! Но как всякая возникающая проблема, необходимость обрабатывать огромные массивы данных привела к разработке новых, более быстрых, алгоритмов для решения больших систем линейных уравнений с огромным числом неизвестных. Заметим, что любое усовершенствование алгоритмов, востребованных поисковиком Google, находит применение во многих других сферах жизни. Точно так же, необходимость быстрого решения задач поиска информации в сети Интернет, постоянно подстёгивает развитие суперкомпьютеров. Как в 1970-е годы под влиянием необходимости решения многомерных задач в области ядерного оружия, энергетики и метеорологии появились первые суперкомпьютеры Cray-1.


Text.ru - 100.00%