Різниця між PageRank та PageRank_NS

Всі пам'ятають https://hexdocs.pm/google_api_content_warehouse/api-reference.html

з якого наче классичний PageRank був скасований на користь Pagerank_NS. Я спробував розібрати патент Producing a ranking for pages using distances in a web-link graph який схоже на все описує саме принцип роботи Pagerank_NS.

Щоб зрозуміти суть цього патенту, треба згадати, з чого все починалося:

Класичний PageRank: Це система "голосування". Кожне посилання - це голос. Чим більше голосів у сторінки, тим вона важливіша. Проблема: цю систему легко обдурити, створивши мільйон штучних сайтів ("ферми посилань, link-loops"), які голосують один за одного.
PageRank_NS (на основі Seed Sites): Тут Google вибирає невелику групу "Seed Sites", яким він довіряє на 100% (наприклад, The New York Times). Вагу отримують лише ті сторінки, на які прямо чи опосередковано посилаються ці довірені ресурси. Проблема: це дуже складно рахувати. Щоразу, коли додається новий довірений сайт, системі доводиться перераховувати весь інтернет заново, що дуже повільно і дорого.

Рішення: Замість того, щоб передавати "вагу", система вимірює "відстань". Чим менше кліків відділяє вас від Nearest Seed, тим вищий ваш рейтинг.

Ключові концепції системи ранжування

Для архітектурного розуміння методу необхідно виділити наступні фундаментальні елементи:

seed pages: Спеціально підібраний набір сторінок, які слугують довіреними точками відліку. Ключовою особливістю є те, що вони містять outgoing links до набору сторінок, які підлягають ранжуванню.
web-link graph: Графова структура, вузлами якої є вебсторінки, а ребрами - гіперпосилання, що забезпечують взаємозв'язок між ними.
link lengths: Числове значення, що присвоюється кожному посиланню в графі. Важливо розуміти, що довжина визначається на основі властивостей самого посилання (link properties) та властивостей сторінок, приєднаних до цих посилань (page properties).
shortest paths: Найкоротша сумарна відстань від масиву seed pages до кожної цільової сторінки в графі, де відстань є сумою значень link lengths на шляху кліку.

Покроковий алгоритм розрахунку рейтингу

Відповідно до логіки, зображеної на Фіг. 2 ("Flowchart"), процес розрахунку виконується за наступним алгоритмом:

Точка входу: Отримання набору сторінок для ранжування та ідентифікація відповідних seed pages.
Зважування силок: Призначення значень lengths для кожного посилання. Розрахунок базується на аналізі технічних характеристик посилань та якості пов'язаних з ними сторінок.
Графові обчислення: Розрахунок shortest distances від множини seed pages до кожного вузла (сторінки) у цільовому наборі.
Скоринг: Визначення ranking score для кожної сторінки як прямої функції від обчислених найкоротших відстаней. Чим менша сумарна відстань до сід сайтів, тим вищим є бал.
Кінцева точка: Генерація впорядкованого ранжування для всього набору сторінок на основі отриманих балів.

Фактори впливу на довжину посилань та якість ранжування

У патенті значення lengths не є статичним. Воно змінюється низкою факторів, що дозволяє ефективно виявляти маніпуляції.

Технічний аспект

Вплив на результат

out-degree

Велика кількість вихідних посилань з однієї сторінки збільшує link lengths, що призводить збільшення відстані.

damping factor

Діє як модифікатор, що адитивно збільшує "вартість" або відстань кожного наступного переходу, моделюючи згасання довіри.

link farms

Спроби штучного накопичення маси посилань не дозволяють зменшити відстань до seed pages, оскільки алгоритм ігнорує об'єм на користь близькості до трастових донорів.

spam pages

Ресурси з низькою якістю отримують високі значення lengths, що відсуває їх на периферію графа і забезпечує низький ranking score.

Властивості сторінок

Висока якість контенту або високий рівень довіри до сторінки, до якої веде посилання, може знижувати link lengths, скорочуючи шлях до цілі.

Роль у загальній архітектурі пошукової системи

Згідно з Фіг. 3, патент інтегрує систему ранжування у глобальний цикл обробки даних:

Web crawler (304): Здійснює безперервне сканування інтернету та передає зібрані дані до центрального вузла.
Data center (308): Виступає ядром системи, де відбуваються процеси стискання (compressing), індексування (indexing) та безпосереднього ранжування (305) за методом найкоротших відстаней.
Search engine (311): Слугує посередником, який приймає query від користувача через browser, звертається до обчислених у Data center рейтингів і повертає структурований response.

Порівняння з традиційним PageRank

Основна архітектурна відмінність між PageRankNS та традиційним PageRank полягає в природі передачі авторитету. Якщо PageRank базується на імовірнісній моделі "потоку" (probability flow), де авторитет розподіляється між усіма вихідними посиланнями вузла, то система PageRankNSвикористовує модель "доданої вартості" (additive cost). У цій моделі кожне посилання додає певну дистанцію до загального шляху від довіреного джерела.

Такий підхід є значно стійкішим до маніпуляцій з боку link farms. У класичних ітераційних алгоритмах спамери можуть підвищувати рейтинг сторінки шляхом накопичення величезного обсягу вхідних посилань. Однак у системі PageRankNS спам-структури стають неефективними: оскільки вони не мають прямих або коротких зв'язків із seed pages, кожне додаткове посилання всередині спам-мережі лише збільшує сумарну відстань або залишає її незмінно великою. Таким чином, замість оцінки "популярності" через об'єм посилань, система фокусується на геометричній близькості вузла до еталонних зон довіри в web-link graph.