ЯдроКодаподготовка к экзаменам
Подготавливаем текст, источники и редакционные примечания без изменения разметки страницы.
Автор: Казачкин Даниил Михайлович · Обновлено
Собственный граф на Python объясняет итерации PageRank, переходы между страницами и обработку вершин без исходящих ссылок.
У двух страниц одинаковое число входящих ссылок. На первую ссылаются малоизвестные заметки, на вторую — хорошо связанный обзор. Простое число ссылок считает их равными. Но можно поставить другой вопрос: как часто случайный читатель, переходящий по ссылкам, будет оказываться на каждой странице? Тогда значение имеет и количество ссылок, и положение ссылающихся страниц в графе.
Это удобно изучать как задачу линейной алгебры и вероятностей. Не требуется настоящий поисковик, сбор миллионов сайтов или доступ к чужим данным. Достаточно определить модель переходов и проследить, как распределяется единичная масса вероятности. При этом математический ранг не следует автоматически называть качеством статьи или достоверностью информации.
В работе Brin и Page 1998 года описан ранний поисковый движок Google, использующий содержание страниц и структуру гиперссылок. PageRank — одна из идей этой системы. Статья не раскрывает современное ранжирование Google или Яндекса и не позволяет предсказывать сегодняшние позиции сайта. Первичная публикация.
Для учебной модели выберем нормировку: сумма рангов равна единице. На каждом шаге с вероятностью d читатель переходит по одной из исходящих ссылок равновероятно, а с вероятностью 1 − d выбирает любую страницу равновероятно. Если исходящих ссылок нет, распределим соответствующую массу между всеми страницами. Такая договорённость устраняет потерю вероятности на тупиковой вершине.
Пусть A ссылается на B и C, B — на C, C — на A, а D не имеет исходящих ссылок. Начнём с равных рангов. Код выполняет итерации, пока сумма абсолютных изменений не станет меньше выбранного порога. Ограничение числа итераций оставлено явно, чтобы вычисление не могло незаметно зависнуть при изменении модели.
graph = {"A": ["B", "C"], "B": ["C"], "C": ["A"], "D": []}
n = len(graph)
damping = 0.85
rank = {node: 1 / n for node in graph}
for _ in range(1000):
next_rank = {node: (1 - damping) / n for node in graph}
for node, links in graph.items():
destinations = links or list(graph)
share = damping * rank[node] / len(destinations)
for target in destinations:
next_rank[target] += share
change = sum(abs(next_rank[node] - rank[node]) for node in graph)
rank = next_rank
if change < 1e-12:
break
else:
raise RuntimeError("iterations exhausted")
assert abs(sum(rank.values()) - 1) < 1e-10
assert rank["C"] > rank["A"] > rank["B"] > rank["D"]
print({node: round(value, 3) for node, value in rank.items()})
# {'A': 0.369, 'B': 0.205, 'C': 0.378, 'D': 0.048}У A и B по одной входящей ссылке, но их ранги различаются. A получает поток от C, тогда как B получает лишь половину ссылочного потока A. Вершина D остаётся с ненулевым рангом благодаря случайным переходам. После округления сумма напечатанных значений может слегка отличаться от единицы; проверка выше использует неокруглённые числа.
Попробуйте добавить к B ссылку на D. Изменится не только ранг D: вероятность, которую раньше целиком получала C, теперь делится. Через последующие шаги эффект возвращается к другим вершинам. Такой эксперимент показывает, почему оценка является свойством всего выбранного графа, а не постоянным атрибутом одной страницы.
В учебном графе мы знаем каждое ребро. В реальном корпусе требуется решить, что считать ссылкой: повторные ссылки, навигацию, внешние переходы, архивные документы. Если один шаблон сайта создаёт тысячи одинаковых ссылок, он может доминировать над содержательными связями. Сначала определите смысл графа, затем выбирайте алгоритм.
Ещё один вопрос — какую аудиторию моделировать. Равномерный случайный переход одинаково относится ко всем документам. Тематический поиск может использовать иной вектор переходов, усиливая определённый раздел. Это меняет постановку и результат. Нельзя сравнивать два рейтинга без указания корпуса, направления рёбер, коэффициента d и выбранного распределения переходов.
Для проверки полезны маленькие симметричные графы: например, цикл должен давать одинаковые ранги при одинаковых настройках. Отдельно проверьте изолированную вершину и граф без рёбер. Сопоставьте результат собственного кода с NetworkX pagerank, учитывая различия критериев остановки и настроек тупиковых вершин.
Рейтинг графа также отделён от конкретного поискового запроса. Если человек ищет настройку окружения, центральный материал об алгоритмах не становится подходящим только из-за высокого ранга. Можно сначала отобрать тематические кандидаты и уже затем использовать структурный сигнал, но такое объединение требует собственной проверки качества выдачи. Создайте несколько реальных учебных вопросов и оцените, получает ли читатель полезную страницу среди первых результатов. Изменение формулы без контрольных запросов способно сделать список математически стройнее и одновременно менее удобным для поиска.
PageRank описывает выбранную модель движения по связям. Он не доказывает полезность, научную корректность или новизну документа. Одинокая качественная статья может получить низкую оценку из-за отсутствия ссылок, а плотная группа слабых материалов — высокий внутренний поток. Поэтому ранги разумно рассматривать как один сигнал рядом с тематической релевантностью и другими требованиями продукта.
В собственном приложении алгоритм пригоден для исследования связей между учебными материалами, зависимостей и навигации. Сохраните снимок графа и параметры расчёта, чтобы изменение рейтинга можно было объяснить. Прежде чем показывать результат пользователю, определите название метрики: «важность в графе ссылок» честнее, чем безусловное «лучшее». Такой выбор превращает эффектную формулу в понятный и проверяемый инструмент.
Самостоятельный русскоязычный разбор ЯдроКода. Описания первоисточников отделены от авторских учебных примеров и инженерных выводов. Материал не является переводом или перепечаткой.
Учебные данные, расчёты, таблицы и программные примеры созданы для этой публикации. Иллюстрации и программный код из первоисточников не воспроизводятся.