PageRank

Основною метою нового алгоритму було поліпшити якість відповідей на пошукові запити. Пошукові системи того часу значною мірою покладались на індексування сторінок за ключовими словами. Цим скористались зловмисники для маніпуляції результатами пошуку методом пошукового спаму. Розробники PageRank зазначили, що станом на листопад 1997 року, лише одна із найпоширеніших пошукових систем була здатна вказати власну сторінку в перших 10 результатах при запиті на власну назву (була здатна знайти сама себе)[7].

Запропонований алгоритм, натомість, брав до уваги структуру і текст гіперпосилань. При цьому:[1]

1. Алгоритм PageRank моделював випадкову подорож користувача інтернет починаючи з випадкової сторінки. Чим більше випадкових відвідувачів діставались сторінки, тим вище її рейтинг. Розробники припустили, що в такий спосіб вдасться уникнути проблем зі спамом за ключовими словами.
2. Вміст сторінки оцінювали не лише за ключовими словами в ній, а й в сторінках, що на неї посилаються. Розробники припустили, що зловмисникові буде важче спотворити вміст сторінок, що посилаються на його сторінку, тільки якщо він не контролює інші сторінки.

Значення PageRank для сторінки A обчислюється за такими правилами: нехай ${\displaystyle T_{1},\dots ,T_{n}}$ — сторінки, що посилаються (цитують) сторінку A. Алгоритм також використовує коефіцієнт демпінгу d, значенням якого знаходяться в проміжку між 0 та 1, та зазвичай має значення 0.85. Функція C(T) дорівнює кількості посилань, що виходять зі сторінки T. Тоді значення PageRank сторінки A, PR(A), дорівнює:[7]

${\displaystyle PR(A)=(1-d)+d\sum _{i=1}^{n}{\frac {PR(T_{i})}{C(T_{i})}}}$

При цьому, значення PageRank — це випадкові величини сума яких для всіх сторінок дорівнюватиме 1.

Для обчислення PageRank Веб представляється у вигляді орієнтованого графу, вершини якого відповідають сторінкам, а ребра — гіперпосиланням між ними. Нехай до пошукового індексу внесено n сторінок. Тоді для моделювання випадкової подорожі створюється матриця переходів M розміру ${\displaystyle n\times n}$. Елемент цієї матриці ${\displaystyle m_{ij}}$, що знаходиться в рядку i та стовпчику j має значення ${\displaystyle 1/k}$ якщо сторінка з номером j має k вихідних посилань, серед яких є одне на сторінку з номером i. Якщо такого посилання нема, то елемент має значення 0[1].

Розподіл ймовірностей знаходження випадкового мандрівника може бути описано вектор-стовпчиком, рядок j якого дорівнюватиме ймовірності перебування на сторінці j[17]. Цей вектор відповідатиме найпростішому, ідеалізованому варіанту PageRank.

Припустімо, що мандрівник може розпочати блукання з будь-якої із n індексованих сторінок з однаковою ймовірністю. Тоді значення елементів початкового вектора дорівнюватимуть 1/n. Ймовірність знаходження на будь-якій зі сторінок на наступному кроці його блукання можна визначити обчисленням ${\displaystyle M\mathbf {v} _{0}}$. Іще через крок — ${\displaystyle M(M\mathbf {v} _{0})=M^{2}\mathbf {v} _{0}}$, і так далі. Таким чином, процес випадкового блукання є Марковським, а вектор розподілів v — власним для матриці M.

За умови, якщо:

1. граф гіперпосилань зв'язний — тобто, з кожної вершини існує шлях до будь-якої іншої;
2. в графі відсутні тупикові вершини — тобто, з кожної вершини є бодай одне вихідне гіперпосилання, то з часом розподіл ймовірностей знаходження мандрівника сягне границі: ${\displaystyle \mathbf {v} =M\mathbf {v} }$.

Проте, через те, що граф гіперпосилань реальної мережі Веб не завжди зв'язний та має тупикові вершини, у формулу випадкового блукання доводиться запровадити можливість випадкового «стрибка» на іншу вершину. Таким чином, формула обчислення розподілів знаходження ${\displaystyle \mathbf {v} '}$ матиме вигляд:[18]

${\displaystyle \mathbf {v} '=\beta M\mathbf {v} +(1-\beta )\mathbf {e} /n}$,

де:

• β — константа, що зазвичай має значення в проміжку 0.8…0.9;
• e — одиничний вектор (розміром n, всі елементи якого дорівнюють 1);
• n — кількість індексованих сторінок, відповідно — кількість вершин графу;
• βM v — моделює випадок, коли з ймовірністю β мандрівник вирішує обрати вихідне посилання з поточної сторінки;
• (1 − β)e/n — вектор, кожен елемент якого дорівнює (1 − β)/n і який моделює появу мандрівника на будь-якій сторінці з ймовірністю (1 − β).

Уявіть собі ідеального веб-серфера, який переміщається по всесвітній павутині. Нехай серфер відвідує сторінку p, випадкове блукання при цьому знаходиться в стані p. На кожному кроці, веб-серфер або перестрибує на іншу сторінку в мережі, обрану псевдо-випадковим чином, або він слід за посиланням на поточній сторінці, при цьому не повертаючись і не відвідуючи одну і ту ж сторінку двічі. Імовірність випадкового стрибка позначимо як d тоді ймовірність переходу за посиланням буде 1-d. Таким чином, вірогідність знаходження користувача на сторінці p можна обчислити за такою формулою: де R (p) — PageRank сторінки, С (p) — число посилань на сторінці, к — число посилаються на p сторінок, d-коефіцієнт загасання (damping factor), зазвичай 0.1.

Якщо масштабувати PageRank таким чином, що де N — число всіх сторінок, для яких проводиться розрахунок PageRank, то R (p) можна розглядати як розподіл ймовірності по всіх сторінках. Для обчислення PageRank складається матриця M розміром NxN, де кожному елементу mij матриці присвоюється значення R0 (p) = 1 / C (p) в тому випадку, якщо з i-ї сторінки є посилання на j-ую, що все залишилися елементи матриці заповнюються нулями . Таким чином, обчислення PageRank зводиться до відшукання власного вектора матриці M що досягається множенням матриці M на вектор Rj на кожному кроці ітерації. Введення коефіцієнта загасання гарантує, що процес сходиться. Підвищуємо значимість сайту Усвідомивши переможну ходу PageRank, не можна не задуматися про його збільшення для своєї сторінки. Інтуїтивно зрозуміло, що чим авторитетніший ресурс, на якому розміщено посилання тим більше вона збільшує PageRank сторінки, на яку посилається. І навпаки, чим більше посилань на сторінці, тим менше буде її внесок у підвищення PageRank вашої сторінки — ще один доказ марності участі в FFA (Free For All — сайти, що містять набір посилань з вільним додаванням). Менш очевидна оптимальна топологія взаємно ссилающихся сторінок. Наприклад, сторінки організовані в «кільце» (коли кожна сторінка посилається на сусіда зліва і справа, остання посилається на першу, а перша на останню) будуть мати один і той же PageRank не залежно від кількості сторінок в кільці (якщо не проводити масштабування по сумі, то PageRank у всіх буде дорівнює 1).

Те ж справедливо для «зірок» або випадку, коли всі посилаються на всіх, і, ймовірно, це твердження справедливо взагалі для всіх симетричних топологій. Набагато більш перспективні з точки зору збільшення PageRank асиметричні топології. Твердження про марність створення «порожніх» (але посилаються один на одного) сайтів у безкоштовних хостерів не настільки очевидно. Наприклад, можна організувати обмін посиланнями на 5 сайтах таким чином, що в одного з них PageRank буде в 15 разів більше, ніж мінімальний не нульовий PageRank. У цьому нескладно переконатися, написавши невелику програмку. Деякі поширені помилки пов'язані з PageRank. Проаналізувавши повідомлення в форумах, присвячених позиціонуванню в пошукових системах, можна виділити цілий ряд тверджень про PageRank, як мінімум спірних, а часто просто невірних.