Реализация алгоритма PageRank и его тестирование на реальных данных

Актуальность

Необходимость ранжировать те или иные объекты является часто встречающейся задачей. Методы ранжирования достаточно разнообразны и постоянно совершенствуются. Один из наиболее широко распространённых методов – PageRank. Этот метод используется для ранжирования результатов работы поисковых систем в интернете. Он положен в основу поисковой системы компании Google и является очень удобным средством, позволяющим найти необходимую информацию в интернете и отсеять второстепенные страницы.

Цель

Знакомство и реализация алгоритма ранжирования PageRank.

Задачи

1. Изучить элементы линейной алгебры и теории графов, необходимые для реализации алгоритма PageRank.

2. Реализовать алгоритм PageRank на языке Python.

3. Написать код, позволяющий представлять совокупность id-адресов в виде матрицы связности в формате excel, а также реализовать визуализацию связей в виде графа.

Оснащение и оборудование, использованное при создании работы

• Методы линейной алгебры и теории графов

• Язык Python

• Программа Excel

Описание

В ходе выполнения проекта автором приведён обзор различных методов ранжирования. В матричных терминах подробно рассмотрен метод ранжирования PageRank, а также метод его вычисления. Наглядно продемонстрированы неочевидные свойства работы алгоритма. Алгоритм вычисления PageRank реализован на языке Python. Он апробирован и изучен в ходе нескольких вычислительных экспериментов: ранжирование участников группы ВКонтакте, станций Московского метрополитена, команд-участниц чемпионата РФПЛ. Алгоритм апробирован на матрицах большой размерности (до 5500). Показана квадратичная зависимость времени работы алгоритма от размерности входной матрицы. В ходе работы освоена графическая библиотека Python, а также на языке PHP-7 реализована автоматическая обработка данных социальной сети VК. Разработан онлайн-калькулятор PageRank, использовать который можно для решения ряда задач в различных областях.

Результаты работы

На языке Python реализован алгоритм ранжирования Pagerank, позволяющий ранжировать объекты с учётом множества взаимодействий между ними. Реализация алгоритма включает более широкую область его использования по сравнению с аналогичной встроенной функцией библиотеки NumPy.

Перспективы использования результатов работы

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

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

Сотрудничество с вузом/учреждением при создании работы

ИВМ РАН

Награды/достижения

Высший балл на олимпиаде «Шаг в будущее»

Мнение автора

«Я считаю, что проект «Инженерный класс в московской школе», через который я уже почти полностью прошёл, может реально заинтересовать тех, кто хочет научиться чему-то интересному. По моему мнению, было бы неплохо выстроить партнёрские отношения школ с реальными организациями, например, ВКонтакте или Яндексом. Ведь школьники могут предложить неожиданные решения гигантам ранка, а взамен уже начать получать реальные прикладные навыки, возможно, оплату»