PageRank початки аналізу

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

Введення в PageRank

Як відомо, кількість інформації в мережі Інтернет зростає дуже швидко, чого не можна сказати про її якість. Користувач в пошуках потрібної інформації може провести все життя, якщо тільки випадково не наткнеться на шуканий матеріал; єдиний вихід для нього - скористатися пошуковими системами, які зберігають інформацію про адреси та вмісті веб-сторінок. Пошукові машини, які допомагають користувачеві, намагаються вирішити проблему - як серед сотень однотипних документів вибрати кращий?

В даний час використовуються текстові та посилальні критерії ранжирування сторінок при пошуку. Перші визначають доречність ("релевантність") документа виходячи з наявності слів запиту в тексті і заголовках сторінки. Однак, наявність великої кількості документів може знецінити витончені механізми розрахунку релевантності, побудовані лише на вмісті сторінки. Це і відбулося, коли люди зрозуміли, яку вигоду вони отримують від цільових відвідувачів, яких безкоштовно надають пошуковики. Якість пошуку зіпсувалося, кількість документів зросла - "релевантний" документ стало дуже легко створити.

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

Посилальні критерії ранжирування допомогли декілька виправити положення. Такий критерій досить важко підробити - на це потрібно добра воля інших веб-майстрів, які дбають про якість своїх ресурсів і не будуть "просувати" негідні сайти. Таким чином, ставка була зроблена на саморегуляцію інтернету, але новачків такий порядок не влаштовував - їх просто так ніхто не пускав до "клубу відомих сайтів". І коли нові правила гри були усвідомлені, пошуковики поступово почали програвати.

Однак, як врахувати цитованість ресурсу? Посилання ж теж бувають різні. Кількість зовнішніх посилань на сайт не годиться для уявлення цитованості - з появою безкоштовних хостингів кількість посилань дуже легко збільшити. Але важливість таких посилань нікчемна в порівнянні з посиланнями з відомих ресурсів. PageRank і є такий параметр важливості, він висловлює цитованість сторінки.

Що таке PageRank і навіщо він потрібний?

Слово PageRank буквально можна перекласти як "ранг сторінки". Сама назва визначає алгоритм розрахунку цитованості, розроблений і використовуваний by Sergey Brin & Larry Page, розробниками пошукової системи Google. Російські аналоги - Зважений Індекс Цитування (ВІЦ у Яндекса), є аналог і у Апорт, Рамблер планує ввести облік цитованості восени 2002 року. Надалі будемо вживати позначення цитованість та PR нарівні з PageRank.

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

У чому основна ідея? Потрібно знайти життєвий критерій, що виражає важливість сторінки. В якості такого критерію була вибрана теоретична відвідуваність сторінки. Була побудована модель подорожі користувача по мережі шляхом переходу по посиланнях. При цьому є вірогідність того, що відвідувачеві сайт набридне і він закриє броузер і почне з випадкової сторінки (припустимо, ймовірність цього дорівнює 0.15 на кожному кроці). Відповідно, з вірогідністю 0.85 він продовжить подорож, клікнувши на одну з доступних на сторінці посилань (всі посилання при цьому рівноправні). Продовжуючи подорож до безкінечності, він побуває на цитованих сторінках багато разів, а на нецітіруемих - менше.

Таким чином, PageRank веб-сторінки було визначено як вірогідність знаходження користувача на цій веб-сторінці; при цьому, звичайно, сума вірогідності по всіх веб-сторінках мережі дорівнює одиниці - десь він повинен обов'язково бути!

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

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

По-третє, кожна сторінка спочатку має ненульовою PR, але дуже маленький.

Ставтеся з обережністю до розрахунків PageRank, якщо-

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

Виявляються закономірності про "збереження середнього PR" або проводяться нормировки по обмеженому набору сторінок. PageRank визначений і діє в глобальному масштабі.

Аналогія

Уявіть собі озеро (сайт), в яке впадають струмки та річки (потоки відвідувачів, нехай "теоретичних"). Кількість потоків може бути будь-яким, але річка приносить багато води, а струмок мало. Тому в своє озеро потрібно направляти потужні потоки. Якась частина води "йде у пісок", решта випливає з вашого озера і впадає в інші озера. Частина води випаровується.

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

Зауваження

PageRank - не єдиний платіжний критерій ранжирування. Він враховує тільки наявність посилання, але не враховує текст на засланні, і текст посилається документа.

Алгоритм "видавлює" вгору в пошуку ті документи, які і без пошукача найбільш популярні. Однак введення такого алгоритму при пошуку істотно посилює конкуренцію, якщо це пошуковик масштабу Google.

Розрахунок PageRank

Отже, будемо розглядати PageRank сторінки як ймовірність потрапляння користувача на сторінку, виражену у відносних одиницях.

PageRank (Pi) сторінки i виражається як {1}

де: d -т.н. "Damping factor", параметр загасання. Приймається рівним 0.85-0.9. Висловлює ймовірність того, що користувач, що зайшов на сторінку, буде продовжувати подорож і переходити за посиланнями. Pi - PageRank цікавить нас сторінки ij - позначення сторінок, на яких є посилання на i-у Pj - PageRank сторінки j, що посилається на i-ю. Сj - Кількість посилань на сторінці j. 1/Сj - Імовірність того, що користувач, що знаходиться на сторінці j, з Сj доступних йому посилань вибере саме посилання на нашу сторінку i. d * Pj / Сj - потік "теоретичної відвідуваності", який дійде до сторінки i зі сторінки j. Підсумовування йде по всіх сторінках, що посилаються, на i-ю. (1-d) - мінімальний PageRank сторінки. Він не дорівнює нулю за рахунок того, що користувач регулярно обирає новий сайт в якості стартової точки.

Однак, на PageRank накладено обмеження:

де N - загальна кількість веб-сторінок в Інтернет.

Тобто, середній PageRank дорівнює одиниці. Обмеження це випливає з нормування ймовірності перебування користувача по всій мережі - сума ймовірностей по всіх сторінках дорівнює одиниці. Таким чином, Вероятностьi = PageRanki / кількість сторінок у мережі

Відзначимо, що значення PageRank, рівне одиниці, тільки здається великим. Кількість сторінок у мережі (N) дуже велика, і ймовірність 1 / N - надзвичайно мала.

Вирішуючи систему рівнянь, можна знайти PageRank всіх сторінок в Інтернет. Розрахунок можна вести різними методами:

Ітераційний метод

Матричний метод

Функціональний метод

Ітераційний метод розрахунку PageRank

Метод найбільш часто використовується. Він полягає в чисельному рішенні системи рівнянь:

Вибираємо геометрію сайту, розстановку посилань, систему рівнянь

Задаємося початковими значеннями PageRank для кожної сторінки. Вони можуть бути будь-якими.

Розраховуємо новий набір значень PageRank по рівнянню (1) виходячи з наявного набору значень

Розраховуємо середній PageRank по всьому набору сторінок, і ділимо PR кожної сторінки на отриману величину. У результаті середній PR стає рівним одиниці.

Якщо набір значень PageRank змінився в порівнянні з вихідним набором кроку 3, повертаємося до кроку 3. Якщо ні, то розрахунок закінчуємо.

При дослідженні впливу геометрії сайту на розподіл PageRank зручно представити структуру посилань у вигляді матриці:

У таблиці вище представлений сайт з чотирьох сторінок, на якому посилання замкнуті в "кільце". Сторінка 1 посилається на 2 (1 - є посилання, 0-посилання немає), 2 на 3, 3 на 4, 4 назад на 1. Представлення структури сайту в такому вигляді зручно, зокрема для розрахунків.

Для того, щоб поекспериментувати з різними структурами сайтів, можна завантажити заготовки в MS Excel для 10 сторінок (30 ітерацій) і 30 сторінок (90 ітерацій). Розподіл PageRank по сторінках розраховується відразу і представлене в жовтій рядку.

Матричний метод розрахунку PageRank

По рівнянню 1:

Нижченаведену "матрицю зв'язків" можна помножити на вектор значень PageRank m-го кроку ітерації, отриманий вектор помножити на d, додати одиничний вектор, помножений на (1-d) і отримати таке наближення вектора PageRank з номером m +1, який потрібно пронормувати ( щоб сума проекцій вектора PR дорівнювала N). При навичках роботи з математичними програмами (наприклад, Mathcad) цей спосіб може бути більш зручним.

Тут сторінка 1 посилається на 2, 3, 4; сторінка 2 - на 3 і 4; сторінка 3 на 4, а 4 на 1. Представлена ​​матриця містить значення Mij = 1/Cj-> i, тобто значення в кожному осередку розділене на загальну кількість посилань Cj на сторінці j.

Недоліки чисельних і ітераційних методів

Фактично, обидва наведені вище методу є різними формулюваннями ітераційного методу розрахунку значень PageRank. Вони вимагають роботи з конкретними чисельними значеннями PageRank. Методи використані для розрахунків в роботах [3,4].

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

З цього міркування випливає, що:

Розрахунки PR "у відриві" від оточення сайту неточні для кожної сторінки вашого сайту - вони виконані для нульового входить PageRank

Правило нормировки не працює в межах вашого сайту (але працює в межах глобального набору проіндексованих сторінок, тобто в рамках Інтернет за версією Google)

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

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

Подивимося, що відбувається при збільшенні вхідного PageRank.

Ось простий сайт з чотирьох сторінок, посилань ззовні ні-

А тут що входить PageRank дорівнює одиниці-

Але нам скоро стане лінь розраховувати PageRank при кожному "уявному" зміні зовнішнього PageRank (P0). Тому розглянемо загальний випадок і висловимо PR сторінок як функції від P0-

Надалі будемо розраховувати 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

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

Звідки береться PageRank?

Поль Дірак висував припущення, що існує оптимальна відстань, з якого найкраще спостерігати жіноче обличчя. Справді: на нульовому відстані, так само як і на нескінченному, задоволення від споглядання прагне до нуля. У той же час, на проміжному відстані воно явно не нульове. Значить, між нульовим і нескінченною відстанню існує максимум функції Задоволення = f (Відстань)

Давайте розглянемо, хоча б за допомогою ітераційного методу, два граничних випадку зв'язності сайтів.

Випадок 1: Всі сторінки в Інтернеті замкнуті в "кільце" - на кожній є тільки одне посилання на сусіда, і тільки одна вхідне посилання. Результат: PageRank дорівнює одиниці для всіх сторінок.

Випадок 2: Усі сторінки в Інтернеті облінкований один з одним - на кожній з N сторінок є посилання на всіх N-1 сусідів, і стільки ж вхідних посилань (N-1). Результат: PageRank дорівнює одиниці для всіх сторінок.

Звідки ж береться великий PageRank?

Відповідь: з неоднорідності розподілу посилань по сторінках. Справа в тому, що всі сторінки мережі були еквівалентні, що призвело до однакового значенням PageRank. Але якщо в однорідному Інтернеті дві сторінки "обміняються посиланнями", їх PageRank збільшиться. А у решти Інтернету - трохи-трохи, але зменшиться. Таким чином, ті, хто обмінюються посиланнями, "стягують ковдру на себе".

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

PRinew = PRiold * (Середній PR в інтернеті без вашого сайту) / (Середній PR в інтернеті, включаючи ваш сайт)

Але, оскільки сумарний PR по Інтернету ніхто не знає, робити цього ми не будемо. У будь-якому випадку ці зміни мізерні, але саме вони і є тим самим "стяганням ковдри на себе".

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

Мало сенсу в розрахунку PageRank сторінок без урахування "зовнішнього" PageRank

Нормировка PageRank на одиницю працює тільки в глобальному масштабі, але не в межах одного сайту

Значення PageRank порядку одиниці дуже малі й нецікаві для аналізу. Основний інтерес представляє передача потоку PageRank від однієї сторінки до іншої

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

Список літератури

Larry Page PageRank: Bringing Order to the Web

Олександр Садовський розтлумаченою PageRank, переклад старого варіанту статті [4]

Ian Rogers The Google Page Rank Algorithm and How It Works Огляд помилок старого варіанту статті [4]

Chris Ridings PageRank Explained, новий варіант статті

Артем Шкондін PageRank: Більше посилань хороших і важливих

Для підготовки даної роботи були використані матеріали з сайту http://promosite.ru/