PageRank — сімейство алгоритмів оцінки важливості вебсторінок за допомогою розв'язання систем лінійних рівнянь. Для кожної сторінки обчислює дійсне число, чим більше число — тим «важливіша» сторінка.

Замість прямого підрахунку кількості посилань PageRank інтерпретує посилання сторінки A на сторінку Б як голос сторінки A на користь сторінки Б. Після цього PageRank оцінює рейтинг сторінки відповідно до кількості отриманих голосів.

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

Найбільший пейджранк серед українських ресурсів має Українська Вікіпедія, у якої він дорівнює 8, а також Українська правда та Газета День — по 7.

За основу PageRank був обраний академічний підхід оцінки важливості публікації автора по числу її згадок в бібліографічних посиланнях інших авторів. Для адаптації до застосування в Інтернет в алгоритм були внесені наступні зміни: вага кожного посилання враховується індивідуально і нормується за кількістю посилань на сторінці. Крім того, PageRank може бути інтерпретовано в термінах випадкового блукання.

Історія

Ідея розв'язання проблеми аналізу зв'язних даних шляхом обчислення власного вектора була запропонована в 1976 році Габріелем Пінскі та Френсіс Нарина, які працювали над складанням наукометричних рейтингів наукових журналів. та в 1977 році Томасом Сааті в його концепції методу аналізу ієрархій, який зважував альтернативні варіанти.

PageRank був створений в Стенфордському університеті Ларрі Пейджем і Сергієм Бріном в 1996 році в рамках науково-дослідного проекту про новий вид інформаційно-пошукової системи.сторінку, Ларрі, Стенфордський проект електронної бібліотеки, говорити. 18 серпня 1997 (архів 2002) Сергій Брін висловив ідею, що інформацію в Інтернеті можна впорядкувати в ієрархію за «популярністю посилань»: чим більше посилань на сторінку, тим вищий у неї ранг187-сторінкове дослідження з університеті Граца, Австрія, включає в себе також увагу, що людський мозок використовуються при визначенні рангу сторінки в Google. У створення нового алгоритму також зробили внесок Раджив Мотвані і Террі Виноград. Перша стаття, в якій описано PageRank і початковий прототип інформаційно-пошукової системи Google, була надрукована в 1998 році: Трохи згодом Пейдж і Брін заснували Google Inc., компанію, що стоїть за інформаційно-пошуковою системою Google. Хоча PageRank є лише одним з чинників, що впливають на результати пошуку, цей алгоритм досі забезпечує основу для всіх інструментів вебпошуку компанії Google.

Назва «PageRank» поєднала прізвище одного з винахідників, Ларрі Пейджа (), а також концепцію вебсторінки. PageRank — зареєстрована торговельна марка компанії Google, а алгоритм було запатентовано . Однак, цей патент належить Стенфордському університету, а не компанії Google. Google має ексклюзивні права на ліцензійне використання патенту Стенфордського університету. Натомість, університет отримав 1,8 млн акцій Google за дозвіл використання патенту; акції були продані в 2005 році за $336 млн.

PageRank був створений під впливом алгоритму аналізу цитованості, роботу над яким Євген Гарфілд розпочав у 1950-ті в університеті Пенсільванії, та Hyper Search розроблений Массімо Мархіорі в університеті Падуї. Того ж року, коли був оприлюднений алгоритм PageRank (1998), Джон Клейнберг опублікував свою роботу про алгоритм HITS. Засновники компанії Google посилаються на роботи Гарфілда, Мархіорі та Клейнберга у власних публікаціях опублікованій в технічному звіті 29 січня 1998 у форматі PDF .

Порівняно невелика інформаційно-пошукова система розробки Робіна Лі, «RankDex», що належала компанії IDD Information Services, вже в 1996 році використовувала схожий алгоритм для ранжування сайтів та сторінок. Використаний в RankDex алгоритм був запатентований в 1999 році і згодом був використаний у заснованій в Китаї Лі пошуковій системі Baidu«About RankDex» , rankdex.com. Ларрі Пейдж посилався на роботу Лі в деяких патентах в СШАДив особливо Лоуренс Пейдж, патенти США (2004) «Метод для озвучування документів у пов'язаної бази даних», (2006) «Метод для вузла рейтингу в пов'язаної бази даних», і (2007) «Залікові документи у зв'язаному базі даних» +2011.

Обчислення PageRank

Огляд

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

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

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

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

Випадкове блукання

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

Розподіл ймовірностей знаходження випадкового мандрівника може бути описано вектор-стовпчиком, рядок j якого дорівнюватиме ймовірності перебування на сторінці j(Mining of Massive Datasets, стор. 167). Цей вектор відповідатиме найпростішому, ідеалізованому варіанту PageRank.

Припустімо, що мандрівник може розпочати блукання з будь-якої із n індексованих сторінок з однаковою ймовірністю. Тоді значення елементів початкового вектора дорівнюватимуть 1/n. Ймовірність знаходження на будь-якій зі сторінок на наступному кроці його блукання можна визначити обчисленням . Іще через крок — , і так далі. Таким чином, процес випадкового блукання є Марковським, а вектор розподілів v — власним для матриці M.

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

Проте, через те, що граф гіперпосилань реальної мережі Веб не завжди зв'язний та має тупикові вершини, у формулу випадкового блукання доводиться запровадити можливість випадкового «стрибка» на іншу вершину. Таким чином, формула обчислення розподілів знаходження матиме вигляд:(Mining of Massive Datasets, стор. 174)

,

де: β — константа, що зазвичай має значення в проміжку 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).

Тематика поєднаних сторінок

Застосування Page Rank в пошуковиках

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

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

В березні 2016 року Google заявила, що усуне останню публічно доступну можливість дізнаватись PageRank сторінок — буде припинена робота модулів для веббраузерів (Toolbar PageRank). Однак, алгоритм PageRank й надалі буде використаний в пошуковій системі для оцінки якості сторінок.

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