PageRank аналіз потоків

Євген Трофименко

У першій частині статті було встановлено, що ітераційні методи не має сенсу застосовувати для розрахунків PageRank, що враховують оточення сайту та "вхідний" PR. Тому ми будемо розраховувати PageRank сторінок не в чисельному вигляді, а вигляді функцій від вхідного PR. Це дозволить виділити ту компоненту PageRank, яка збільшується в міру розкручування, і відокремити "залишки" у вигляді констант, величина яких порядку одиниці.

Повторення: функціональний метод розрахунку PageRank

Завдання: розрахувати стабільні значення PageRank, не застосовуючи ітераційних методів. Розглянемо рівняння (1) уважніше - в ньому немає ніяких особливостей, які вимагають застосування ітерацій. Навпаки, PR кожної сторінки визначається як функція PR інших сторінок. Припустимо, що ми досягли стаціонарного стану, і PageRank сторінок не змінюється. Залишається тільки записати рівняння для PR кожної з сторінок і вирішити систему.

{1}

Отже, будемо розраховувати PageRank сторінок сайту як функцію від зовнішнього, "вхідного" PageRank. Для цього потрібні: рівняння (1) і уявлення про еквівалентність сторінок одного типу. Приклад-

На сайті, який наведено нижче, 3 нижніх сторінки еквівалентні між собою в усіх сенсах. Відповідно, всі вони будуть мати однаковий PageRank (P2). Головний сторінка відрізняється від них і має PR = P1.

Запишемо рівняння для сторінок виду 1 і виду 2:

P1 = 0.15 +0.85 * (P0 +3 P2) - на сторінку виду 1 посилаються 3 сторінки виду 2, на кожній з яких є одне посилання.

P2 = 0.15 +0.85 * (P1 / 3) - на сторінку виду 2 посилається сторінка виду 1, на якій є 3 посилання.

Вирішуючи цю систему, одержуємо-

P1 = 0.15 * (1 +3 * 0.85) / (1-0.85 ^ 2) +0.85 / (1-0.85 ^ 2) * P0 = 1.92 +3.06 * P0 P2 = 0.69 +0.87 * P0

Цим методом хоча і складніше користуватися, але він володіє однією гарною якістю, якого немає в ітераційних методів - спільністю.

Різні випадки: два типи сторінок

Отже, почнемо розгляд самого простого випадку - сайт складається з однієї головної сторінки і деякої кількості підлеглих сторінок. Посилання ззовні спрямовані на головний сторінку.

Випадок 1: "мітла"

З головної сторінки (PageRank = P1) є посилання на N еквівалентних підлеглих сторінок (PageRank = P2). Підлеглі сторінки не пов'язані між собою, на кожній з них є одне посилання на головний сторінку.

Вирішуючи систему, знаходимо залежності P1, 2 від P0, N.

Рішення системи: P1 = 0.15 / (1-0.85 ^ 2) +0.85 * 0.15 / (1-0.85 ^ 2) * N +0.85 ^ 2 / (1-0.85 ^ 2) * P0 =>

P1 = 0.541 +0.459 * N +3.063 * P0 P2 = 0.541 +0.459 / N +2.604 * P0 / N

Отже, ми бачимо, що:

PageRank головної сторінки (P1) збільшився не на P0, але на 3P0. Тобто, ми отримуємо реальний виграш за рахунок взаємного впливу сторінок

P2 обернено пропорційний числу сторінок. Очевидний висновок.

P1 прямо пропорційний числу сторінок. Отже, збільшуючи кількість сторінок на сайті, можна сконцентрувати великий PageRank на головній сторінці. При цьому P2 в міру збільшення кількості сторінок прагне до 0.541, а не до 1; і віддає частину PageRank головній сторінці

Середній PR

Розрахуємо сумарне значення PageRank по нашому сайту-

PR = P1 + N * P2 = 0.541 + N +5.667 * P0

Це показує, що:

Середній PageRank при великій кількості сторінок близький до 1.

PageRank на сайті збільшився не на P0, а на 5.667 = 0.85/0.15 P0. Це сталося через існування зворотного зв'язку між головною і другорядними сторінками, тобто, хвиля PR як би "відкотилася назад".

Однак, при зверненні в нуль P0 = 0 середній PR не стає рівним 1. Це відбувається через те, що ми відмовилися від умови нормування, але за "відриві" сайту від зовнішнього середовища повинні його знову застосувати. Відмова від нормування дозволяє зберегти зв'язок із зовнішнім PageRank, при цьому ми пам'ятаємо про необхідність перенормування через "стягування ковдри на себе".

Чи можна отримати великий PageRank тільки за рахунок маси сайту?

Судячи з формулою, можна отримати будь-яке значення PageRank головної сторінки лише за рахунок збільшення кількості сторінок, адже P1 лінійно збільшується при збільшенні N. При цьому всі сторінки сайту повинні бути проіндексовані Google. Проте, згадаймо про те, що існує мінімальне значення PR, досягти якого необхідно для індексації документа Google. Але ж PageRank другорядних сторінок (P2) зменшується з N! Подивимося на графік:

Якщо кількість сторінок на сайті виявиться занадто великим, то другорядні сторінки просто не проиндексируется! І ніякого надвисокої PR досягти не вдасться. Можна спробувати:

Поступово додавати сторінки Поставивши кілька посилань на іншій сторінці з хорошим PR, дочекатися індексації частині сторінок. Потім додати ще кілька сторінок. І так далі. Але: на повне додавання буде потрібно дуже багато часу!

Збільшити зовнішній PR Як видно, P2 ~ P0 / N. Тобто, збільшуючи P0, можна домогтися індексації другорядних сторінок. Але чим більше число сторінок, тим більше доведеться працювати на збільшення зовнішнього PR! На це теж потрібно багато часу!

Використовувати обидва методи відразу

Ставити посилання з другорядних сторінок один на одного. Це ми розглянемо далі: випадок 2.

Отже, незважаючи на явну залежність P1 від N, немає можливості швидко збільшити свій PageRank - а це означає відносну стійкість у розподілі сил. До того ж, якщо сайт дійсно дуже хороший, і на нього посилаються "добровільно" - він завжди обжене "поганий сайт" (за рахунок більш повної індексації сторінок в тому числі). Алгоритм PageRank як би підштовхує до поступового розвитку сайту та поступового додаванню сторінок.

Випадок 2: "кільце на паличці"

Додамо до попереднього нагоди одне посилання на "сусіда":

З головної сторінки (PageRank = P1) є посилання на N еквівалентних підлеглих сторінок (PageRank = P2). Підлеглі сторінки пов'язані між собою: є одне посилання на сусідню підпорядковану сторінку, на кожній з них є одне посилання на головний сторінку.

Рішення системи: P1 = 0.403 +0.298 * N +2.287 * P0 P2 = 0.702 +0.596 / N +3.380 * P0 / N

Видно, що ситуація приблизно така ж, як і у випадку 1, однак тепер PageRank другорядних сторінок збільшився, а головної сторінки - зменшився. Це стосується як залежності від N, так і залежності від P0.

У даному випадку ми трохи виграємо в PR другорядних сторінок - це допоможе їх проіндексувати швидше, але знизить PageRank головної сторінки, заради якого все й затівалося. А що буде в граничному випадку - коли всі сторінки щільно пов'язані?

Випадок 3: "камінчик"

З головної сторінки (PageRank = P1) є посилання на N еквівалентних підлеглих сторінок (PageRank = P2). Підлеглі сторінки попарно зв'язані між собою: на кожній з них є посилання на всіх N-1 сусідів. На кожній з них є одне посилання на головний сторінку.

Рішення системи: P1 = (0.85 * P0 +1) / (1 - (0.85 ^ 2 / (0.15N +0.85))) -0.85 / (0.15N +0.85-0.85 ^ 2)

Для простоти розглянемо граничні значення P1, 2 при прагненні N до нескінченності: P1-> 1 +0.85 * P0-x / N P2-> 1 + y * P0 / N, де x, y порядку одиниці.

Видно, що фактично, зовнішній P0 впливає тільки на головну сторінку сайту, але слабкіше, ніж у попередніх випадках. Зате збільшується до одиниці PageRank другорядної сторінок.

Випадок 4 (загальний)

З головної сторінки (PageRank = P1) є посилання на N еквівалентних підлеглих сторінок (PageRank = P2). Підлеглі сторінки пов'язані між собою: на кожній з них є посилання на M сусідніх підлеглих сторінок (M <= N). На кожній з них є одне посилання на головний сторінку.

Рішення системи: P1 = (0.15 +0.85 P0) / (1 - (0.85 ^ 2 / (0.15M +1))) +0.15 * 0.85 * N / (0.15M +1-0.85 ^ 2)

З цієї залежності видно, що при збільшенні числа посилань (M) між другорядними сторінками PageRank головної сторінки все слабкішим залежить від N і від P0. Це відбувається через передачу великої частини PageRank в область другорядних сторінок, звідки "повертається назад" мала його частина.

Для наочності розглянемо залежно PagaRank від кількості сторінок (N) і кількості посилань на сусідні другорядні сторінки (M) при вхідному P0 = 1 (завантажити графіки в Excel):

PageRank головної сторінки (P1)

Видно, що найшвидше зростання P1 відбувається при збільшенні кількості сторінок відбувається за відсутності посилань між другорядними сторінками (M = 0). За наявності декількох посилань зростання P1 стає повільним. Якщо розглядати зміну P1 при фіксованій кількості сторінок N (наприклад, N = 20), видно, що при збільшенні кількості посилань M відбувається різке зменшення PageRank головної сторінки.

PageRank другорядних сторінок (P2)

Другорядні сторінки мають високий PageRank тільки при невеликій їх числі. При відсутності посилань на сусідів (M = 0) P2 зменшується трохи швидше, ніж у випадку M = N, і досягає менших граничних значень. При фіксованому числі сторінок (N = 20) і збільшенні числа посилань (M) P2 трохи зростає.

Проміжні висновки

Підходи до розвитку сайту для повної індексації Google і виграшу в PageRank головної сторінки:

Поступово додавати сторінки

Збільшувати зовнішній PageRank

Поставити посилання з другорядних сторінок один на одного, а після індексації прибрати їх.

Зауваження. Багато пошукачі враховують PageRank-подібні критерії при ранжируванні, але не обов'язково існування нижньої межі PageRank для індексації.