Math
Случайные блуждания и PageRank
Проследите движение вероятностной массы по ориентированному графу и сравните итерации матрицы с ансамблем случайных блужданий. Телепортация позволяет PageRank сходиться к единственному распределению. Сравните периодический цикл и граф, в котором необработанные висячие вершины вызывают утечку массы.
Что происходит
Столбцы показывают распределение на текущем шаге, а тонкие столбцы — ансамбль блуждающих частиц. Это не доля времени, которую одна частица провела в каждой вершине. В ориентированном цикле распределение, сосредоточенное в одной вершине, продолжает вращаться, хотя доли посещений за длительное время могут приближаться к равномерному стационарному распределению.
При положительной вероятности телепортации и заполненных висячих строках матрица переходов стохастическая, и все вершины сообщаются: стационарное распределение единственно, а итерации сходятся. Пустая висячая строка создаёт субстохастическую модель с утечкой массы. Здесь эталонное решение для неё отключено; это не означает, что у любого субстохастического графа нет стационарного распределения.
Модуль субдоминантного собственного значения описывает асимптотическую скорость экспоненциального затухания ошибки при сходимости. Отдельные шаги могут колебаться, а особое начальное состояние может не возбуждать самую медленную моду. Сравните точечный и равномерный старты при разных значениях затухания.
Уравнения модуля
Уравнения блуждание: P[i][j] = w[i][j] / (сумма по j от w[i][j]); строка из нулей - ВИСЯЧАЯ вершина матрица Google: G = d·P + (1 − d)/n, где висячая строка заменена равномерной строкой стационарное распределение: pi·G = pi при sum(pi) = 1; достигается степенными итерациями и решается напрямую для проверки сходимость: ошибка убывает как |lambda_2|^n, поэтому |lambda_2| И ЕСТЬ скорость - но размер шага отслеживает её только в среднем, потому что комплексная субдоминантная пара заставляет затухание ВРАЩАТЬСЯ (среднее геометрическое отношений шагов восстанавливает её, среднее арифметическое оказывается на 1.5 % выше) граница демпфирования: |lambda_2| = d·|mu_2(P)| точно, поэтому |lambda_2| ≤ d - НЕРАВЕНСТВО; измерено до 5.0e-16, граница неплотная на малой сети (коэффициент 0.667) и точная на цикле, где |mu_2| = 1 сток ранга: если висячая строка остаётся пустой, суммарная масса убывает до нуля - ранг полностью утекает из системы периодический случай: ориентированный n-цикл имеет в качестве собственных значений корни n-й степени из единицы, все по модулю 1; из начальной точки он возвращается в неё каждые n шагов и никогда не устанавливается неориентированный случай: блуждание обратимо, и pi - это просто степень / 2|E| - одна строка арифметики и проверка того, что итерация решает именно то, что заявлено
