ПРИМЕНЕНИЕ МАТРИЧНЫХ МЕТОДОВ И СОБСТВЕННЫХ ВЕКТОРОВ В АЛГОРИТМЕ РАНЖИРОВАНИЯ ВЕБ-СТРАНИЦ(PAGERANK)

APPLICATION OF MATRIX METHODS AND EIGENVECTORS IN THE WEB PAGE RANKING ALGORITHM (PAGERANK)

Ermolaev Artemiy Sergeevich

1st year student, Department of Higher Mathematics, Ulyanovsk State Technical University,

Russia, Ulyanovsk

Kireev Sergey Vladimirovich

Scientific supervisor, Candidate of Physical and Mathematical Sciences, Professor, Ulyanovsk State Technical University,

Russia, Ulyanovsk

АННОТАЦИЯ

В статье рассматривается математическая основа алгоритма PageRank, используемого поисковой системой Google для ранжирования веб-страниц. Приводится модель случайного блуждания, стохастическая матрица переходов, и показывается, что искомый вектор рангов является собственным вектором матрицы, соответствующим собственному значению 1. Выполнен численный расчёт для сети из четырёх страниц, проиллюстрирована итерационная схема степенного метода. Показана связь с теорией цепей Маркова и линейной алгеброй.

ABSTRACT

The article discusses the mathematical foundation of the PageRank algorithm used by the Google search engine for ranking web pages. The random walk model, the stochastic transition matrix are presented, and it is shown that the desired rank vector is an eigenvector of the matrix corresponding to eigenvalue 1. A numerical calculation for a network of four pages is performed, and the iterative power method is illustrated. The connection with Markov chain theory and linear algebra is demonstrated.

Ключевые слова: PageRank, собственный вектор, стохастическая матрица, цепи Маркова, степенной метод, линейная алгебра.

Keywords: PageRank, eigenvector, stochastic matrix, Markov chains, power method, linear algebra.

Современный интернет содержит миллиарды веб-страниц, и для эффективного поиска необходимо ранжировать результаты по важности. Один из самых известных алгоритмов — PageRank, предложенный основателями Google Ларри Пейджем и Сергеем Брином. В основе алгоритма лежат понятия линейной алгебры: собственные векторы, стохастические матрицы и итерационные методы [1, с. 112].

Идея PageRank заключается в моделировании поведения «случайного пользователя», который переходит по ссылкам. Чем больше важных страниц ссылаются на данную страницу, тем выше её ранг. Формально, пусть имеется n веб-страниц. Построим ориентированный граф, где вершины — страницы, а дуги — гиперссылки. Матрица смежности H размера n х n определяется так: H_ij = 1, если со страницы j есть ссылка на страницу i, иначе 0. Затем нормируем столбцы, чтобы получить стохастическую матрицу P (сумма элементов каждого столбца равна 1). Если на странице j нет исходящих ссылок (висячая вершина), заменяем столбец на 1/n (телепортация).

Однако чистая матрица P может быть нерегулярной (неприводимой). Поэтому вводится телепортация с вероятностью ɑ (обычно ɑ = 0.85). Итоговая матрица Google имеет вид:

где 1 — вектор из единиц, а 11^T – матрица, все элементы которой равны 1. С вероятностью (1-ɑ) пользователь телепортируется на случайную страницу, а с вероятностью ɑ — переходит по ссылкам.

По теореме Перрона–Фробениуса у стохастической матрицы существует единственный собственный вектор r, удовлетворяющий Gr = r, с положительными компонентами, сумма которых равна 1. Этот вектор и есть вектор рангов PageRank [2, с. 45].

Для нахождения r используется степенной метод (power iteration): r^(k+1) = Gr^(k), сходящийся к главному собственному вектору. Скорость сходимости определяется отношением |λ₂| / λ₁ = |λ₂|, так как λ₁ = 1.

Рассмотрим численный пример. Пусть имеется 4 страницы, ссылки между ними изображены на рисунке 1 (условный граф). Структура ссылок:

· Страница 1 ссылается на страницы 2 и 3.

· Страница 2 ссылается только на страницу 4.

· Страница 3 ссылается на страницу 1.

· Страница 4 ссылается на страницы 1 и 3.

Рисунок 1. Ориентированный граф ссылок между веб-страницами

Построим матрицу H (столбцы соответствуют страницам-источникам, строки – целевым):

Положим ɑ = 0.85. Тогда матрица Google:

Начальный вектор r⁽⁰⁾ = (0.25, 0.25, 0.25, 0.25)^T. Выполним несколько итераций вручную (с округлением до трёх знаков). Результаты приведены в таблице 1.

Таблица 1.

Итерационное вычисление PageRank для 4 страниц

Как видно из таблицы, после 4–5 итераций значения стабилизируются. Финальный ранг: PR₁ = PR₃ ≈ 0.293, PR₂ ≈ 0.213, PR₄ ≈ 0.201. Страницы 1 и 3 являются наиболее значимыми, несмотря на то, что на страницу 4 ссылается страница 2, но сама страница 2 имеет низкий вес. Результат согласуется с интуицией: страница 1 получает ссылки от страницы 3 и 4, а страница 3 – от страницы 1 и 4, образуя взаимно усиливающую связь.

На практике алгоритм PageRank применяется не только для веб-поиска, но и для анализа социальных сетей, цитируемости научных публикаций, оценки влиятельности пользователей [3, с. 92]. С вычислительной точки зрения для миллионов страниц используются итерационные методы (как в примере) и разреженные матрицы.

Таким образом, метод PageRank – яркий пример применения аппарата линейной алгебры (собственные векторы, цепи Маркова) к реальной задаче из области информационных технологий. Студенты могут реализовать простейший вариант алгоритма на Python, используя библиотеки NumPy, что помогает глубже понять связь между абстрактными понятиями и практикой.

Список литературы:

1. Brin S., Page L. The Anatomy of a Large-Scale Hypertextual Web Search Engine // Computer Networks and ISDN Systems. – 1998. – Vol. 30, № 1-7. – P. 107–117.
2. Лэнгвилл Э. Google PageRank: алгоритм ранжирования. – М.: Вильямс, 2012. – 256 с.
3. Manning C.D., Raghavan P., Schütze H. Введение в информационный поиск. – М.: ООО “И.Д. Вильямс”, 2011. – 528 с.