PageRank як ланцюг Маркова: випадковий серфер і стаціонарний розподіл

Ланцюги Маркова: стани та переходи

Ланцюг Маркова — послідовність станів, де ймовірність переходу до наступного стану залежить лише від поточного стану, а не від історії, що до нього призвела, — марковська властивість. Формально ланцюг над станами {1, …, n} задається матрицею переходів P, де P_ij — ймовірність переходу зі стану i в стан j:

Для веба «станами» є сторінки, а Pᵢⱼ — ймовірність того, що серфер на сторінці i натисне посилання на сторінку j. Якщо сторінка i має k вихідних посилань, найпростіша модель призначає Pᵢⱼ = 1/k для кожної сторінки j, на яку є посилання, і 0 — інакше.

Стаціонарний розподіл

Нехай π — рядок-вектор, де πᵢ — ймовірність перебування у стані i. Після одного кроку новий розподіл дорівнює π·P. Стаціонарний розподіл π* — це нерухома точка цього перетворення:

π*ᵢ — це довгострокова частка часу, яку ланцюг проводить у стані i, незалежно від початкового стану — за умови, що ланцюг незвідний (кожен стан досяжний з будь-якого іншого) та аперіодичний (без жорсткої довжини циклу). PageRank — це саме π* для ланцюга «веб-серфер»: сторінки з найвищою стаціонарною ймовірністю посідають найвищі місця.

Модель випадкового серфера

Уявіть серфера, який на кожному кроці або (a) клацає рівномірно випадкове вихідне посилання з ймовірністю d (коефіцієнт загасання, зазвичай 0.85), або (b) йому набридає і він переходить на рівномірно випадкову сторінку будь-де у вебі з ймовірністю (1 − d). Це дає повний перехід PageRank:

Термін випадкового переходу запобігає тому, щоб серфер назавжди застряг у підграфі без виходу, і гарантує, що ланцюг незвідний та аперіодичний — тому унікальний стаціонарний розподіл існує незалежно від форми веб-графа.

Тупикові вузли та коефіцієнт загасання

Тупиковий вузол — сторінка без вихідних посилань (PDF, зображення, глухий кут). Без спеціальної обробки вся її ймовірнісна маса просто зникає із системи, а рядки P більше не сумуються до 1. Стандартне рішення — перерозподілити масу тупикової сторінки рівномірно на всі N сторінок, ніби вона посилається на всіх:

Степеневий метод у JavaScript

Замість того, щоб розв'язувати π·P = π напряму (нездійсненно для мільярдів сторінок), PageRank використовує степеневий метод (power iteration): почати з рівномірного розподілу і повторно множити на матрицю переходів, доки він не перестане змінюватися.

function pageRank(adjacency, d = 0.85, iterations = 100, tol = 1e-9) {
  const N = adjacency.length;
  const outDegree = adjacency.map(links => links.length);
  let pr = new Float64Array(N).fill(1 / N);

  for (let iter = 0; iter < iterations; iter++) {
    const next = new Float64Array(N).fill((1 - d) / N);

    // Перерозподілити масу тупикових вузлів рівномірно на всі N сторінок
    let danglingMass = 0;
    for (let i = 0; i < N; i++)
      if (outDegree[i] === 0) danglingMass += pr[i];
    const danglingShare = d * danglingMass / N;

    // Розподілити ранг кожної сторінки по її вихідних посиланнях
    for (let i = 0; i < N; i++) {
      if (outDegree[i] === 0) continue;
      const share = d * pr[i] / outDegree[i];
      for (const j of adjacency[i]) next[j] += share;
    }
    for (let j = 0; j < N; j++) next[j] += danglingShare;

    // Перевірка збіжності по L1-нормі
    let delta = 0;
    for (let j = 0; j < N; j++) delta += Math.abs(next[j] - pr[j]);
    pr = next;
    if (delta < tol) break;
  }
  return pr; // pr[i] ≈ π*ᵢ, сума дорівнює 1
}

Чому це сходиться: теорема Перрона-Фробеніуса

Степеневий метод сходиться завдяки теоремі Перрона-Фробеніуса: матриця з усіма додатними елементами (якою є демпфована, телепортуюча матриця переходів, оскільки кожен елемент не менший за (1−d)/N > 0) має унікальне найбільше власне значення λ₁ = 1, а її власний вектор строго додатний. Повторне застосування матриці геометрично пригнічує всі інші компоненти власного вектора зі швидкістю, яка визначається |λ₂/λ₁|:

Саме тому коефіцієнт загасання впливає на швидкість збіжності: він безпосередньо обмежує друге за величиною власне значення, тому менше d сходиться швидше (але дає більш однорідні ранги), а більше d зберігає структуру посилань, проте сходиться повільніше.

Поза вебом: інші застосування

Та сама ідея «випадковий обхідник + стаціонарний розподіл» з'являється в інформатиці й поза нею всюди, де потрібно ранжувати вузли графа за структурною важливістю, а не за локальними властивостями:

• Вплив у соціальних мережах: ранжування облікових записів за тим, наскільки часто на них потрапляє випадковий «обхід підписників».
• Мережі цитувань: ранжування статей за важливістю, зваженою цитуваннями (оригінальне джерело натхнення для PageRank з бібліометрії).
• Рекомендаційні системи: персоналізований PageRank зміщує крок телепортації до відомих інтересів користувача замість рівномірного перезапуску.
• Мережі білок-білкових взаємодій: виявлення структурно центральних білків у біологічних графах.
• Markov Chain Monte Carlo (MCMC): той самий механізм стаціонарного розподілу лежить в основі семплування Метрополіса-Гастінгса.