Ранжування PageRank як марківської ланцюга: Модель випадкового серфера

Марковські ланцюги та стаціонарний розподіл

Марковський ланцюг — це послідовність станів, де ймовірність наступного стану залежить лише від поточного, закодована у матриці переходу P, де Pᵢⱼ — ймовірність переходу з стану i до стану j. Для вебсайтів стани – це сторінки, а Pᵢⱼ = 1/k, якщо у сторінці i є k вихідних посилань і одне з них вказує на j. Стаціонарний розподіл π* задовольняє π*·P = π* — лівий власневектор матриці P з власним значенням 1 — і π*ᵢ – це довгострокова частка часу, яку ланцюг проводить у стані i, за умови, що ланцюг є неповнозв’язним та періодичним. PageRank є точно π* для веб-переглядацького ланцюга: сторінки з найвищою стаціонарною ймовірністю ранжуються вищими.

Випадковий серфер та коефіцієнт гасіння

Уявіть собі серфера, який на кожному кроці випадковим чином обирає вихідний посилання з рівномірним розподілом ймовірностей (коефіцієнт гасіння, зазвичай 0.85), або втрачає інтерес і телепортується на випадкову сторінку з ймовірністю (1-d). Цей термін випадкового стрибка запобігає постійному ув’язненню серфера в підграфу без виходу та гарантує, що ланцюг є непослідовним і періодичним, отже існує завжди унікальне стаціонарне розподілення ймовірностей незалежно від форми графа зв'язків. «Звисаюча» вузол — сторінка з нульовою кількістю вихідних посилань — отримує перерозподіл його ймовірнісної маси рівномірно між усіма N сторінками, ніби вона пов’язана зі всіма; без цього виправлення ймовірнісна маса просто зникає з системи.

Ітерації сили: множення матриці, повторне

Замість того, щоб розв’язувати π·P = π безпосередньо — неможливо для мільярдів сторінок — PageRank використовує ітерацію сили: починається з рівномірного розподілу та повторно множиться на перехідну матрицю до тих пір, поки вона не зупиниться змінюватися. Кожен ітераційний крок коштує O(E), торкаючись кожного краю один раз, що робить PageRank обчислюваним у масштабах веб-сайтів — щільне множення матриць коштувало б O(N²) і було б повністю неможливим. Збіжність гарантована теоремою Perron-Frobenius: оскільки кожна вхідна матриця приглушеної перехідної матриці є більшою або рівною (1−d)/N > 0, матриця має власну унікальну найбільшу власне значення λ₁ = 1 з строго позитивним власним вектором, і повторне множення придушує всі інші компоненти власних векторів на швидкості, обмеженій коефіцієнтом затухання d.

PR(p) = (1 − d)/N + d · Σ_(q→p) PR(q) / L(q)

d = 0.85 → ~50-100 power-iteration steps to converge
π_t = π₀·P^t → v₁ as t → ∞     (convergence rate ∝ |λ₂|^t, bounded by d)

Пояснення квантового тунелювання

Однакова ідея "випадкового перебігу + стаціонарної розподіленої" проявляється скрізь, де потрібно ранжувати вузли за їх структурною важливістю, а не за локальними властивостями: оцінки впливу соціальних мереж, рейтинги наукових робіт з урахуванням цитування (оригінна біометрична натхнення PageRank), персоналізовані рекомендаційні системи, які спотворюють крок телепортації до відомих інтересів, структурно центральні білки в біологічних мережах взаємодії та методи Metropolis-Hastings, що живлять марковські ланцюги Монте-Карло.

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте the simulation і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.