---

Маяки в океане

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

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

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

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

Решение задачи

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

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

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

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

Математическая модель

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

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

Как же действует алгоритм расчёта 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).

В нашей модели из трёх страниц распределение рангов страниц будет происходить по следующим правилам, определённым конфигурацией графа на рис. 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.

---