PageRank — сімействоалгоритмів оцінки важливостівебсторінок за допомогою розв'язання систем лінійних рівнянь. Для кожної сторінки обчислюєдійсне число, чим більше число — тим «важливіша» сторінка[1].
Замість прямого підрахунку кількостіпосилань PageRank інтерпретує посилання сторінки A на сторінку Б як голос сторінки A на користь сторінки Б. Після цього PageRank оцінює рейтинг сторінки відповідно до кількості отриманих голосів.
PageRank також враховує значимість кожної сторінки, що отримала голос, адже голоси деяких сторінок є важливішими, і відповідно до цього підвищується значущість сторінки, посилання на яку вони містять. Важливі сторінки отримують більш високу оцінку PageRank і відображаються на перших позиціях результатів пошуку. Для визначення значущості сторінки технологія Google використовує колективний інтелект всесвітньої мережі. Людина не бере участі в обробці результатів. Пошукова система Google не спотворює інформацію про позиції платою за результати пошуку.
Найбільший пейджранк серед українських ресурсів маєУкраїнська Вікіпедія, у якої він дорівнює 8, а такожУкраїнська правда таГазета День — по 7.[джерело?]
За основу PageRank був обраний академічний підхід оцінки важливості публікації автора по числу її згадок в бібліографічних посиланнях інших авторів. Для адаптації до застосування в Інтернет в алгоритм були внесені наступні зміни: вага кожного посилання враховується індивідуально і нормується за кількістю посилань на сторінці. Крім того, PageRank може бути інтерпретовано в термінах випадкового блукання.
Ідея розв'язання проблеми аналізу зв'язних даних шляхом обчисленнявласного вектора була запропонована в 1976 році Габріелем Пінскі та Френсіс Нарина, які працювали над складаннямнаукометричних рейтингів наукових журналів[2].та в 1977 роціТомасом Сааті в його концепціїметоду аналізу ієрархій, який зважував альтернативні варіанти.[3]
PageRank був створений вСтенфордському університетіЛаррі Пейджем іСергієм Бріном в 1996 році[4] в рамках науково-дослідного проекту про новий видінформаційно-пошукової системи.[5] Сергій Брін висловив ідею, що інформацію в Інтернеті можна впорядкувати в ієрархію за «популярністю посилань»: чим більше посилань на сторінку, тим вищий у неї ранг[6]. У створення нового алгоритму також зробили внесокРаджив Мотвані іТеррі Виноград. Перша стаття, в якій описано PageRank і початковий прототип інформаційно-пошукової системи Google, була надрукована в 1998 році:[7] Трохи згодом Пейдж і Брін заснувалиGoogle Inc., компанію, що стоїть за інформаційно-пошуковою системою Google. Хоча PageRank є лише одним з чинників, що впливають на результати пошуку, цей алгоритм досі забезпечує основу для всіх інструментів вебпошуку компанії Google[8].
Назва «PageRank» поєднала прізвище одного з винахідників, Ларрі Пейджа (англ.Page), а також концепціювебсторінки[9]. PageRank — зареєстрованаторговельна марка компанії Google, а алгоритм було запатентованоU.S. Patent 6 285 999. Однак, цей патент належитьСтенфордському університету, а не компанії Google. Google має ексклюзивні права на ліцензійне використання патенту Стенфордського університету. Натомість, університет отримав 1,8 млн акцій Google за дозвіл використання патенту; акції були продані в 2005 році за$336 млн[10][11].
PageRank був створений під впливом алгоритму аналізу цитованості, роботу над якимЄвген Гарфілд розпочав у 1950-ті вуніверситеті Пенсільванії, таHyper Search розробленийМассімо Мархіорі вуніверситеті Падуї. Того ж року, коли був оприлюднений алгоритм PageRank (1998),Джон Клейнберг опублікував свою роботу про алгоритмHITS. Засновники компанії Google посилаються на роботи Гарфілда, Мархіорі та Клейнберга у власних публікаціях[7][12].
Порівняно невелика інформаційно-пошукова система розробки Робіна Лі,«RankDex», що належала компанії IDD Information Services, вже в 1996 році використовувала схожий алгоритм для ранжування сайтів та сторінок[13]. Використаний в RankDex алгоритм був запатентований в 1999 роціU.S. Patent 5 920 859 і згодом був використаний у заснованій в Китаї Лі пошуковій системіBaidu[14][15]. Ларрі Пейдж посилався на роботу Лі в деяких патентах в США[16].
Основною метою нового алгоритму було поліпшитиякість відповідей на пошукові запити. Пошукові системи того часу значною мірою покладались на індексування сторінок за ключовими словами. Цим скористались зловмисники для маніпуляції результатами пошуку методомпошукового спаму. Розробники PageRank зазначили, що станом на листопад 1997 року, лише одна із найпоширеніших пошукових систем була здатна вказати власну сторінку в перших 10 результатах при запиті на власну назву (була здатна знайти сама себе)[7].
Запропонований алгоритм, натомість, брав до уваги структуру і текст гіперпосилань. При цьому:[1]
Значення PageRank для сторінкиA обчислюється за такими правилами: нехай — сторінки, що посилаються (цитують) сторінкуA. Алгоритм також використовує коефіцієнт демпінгуd, значенням якого знаходяться в проміжку між 0 та 1, та зазвичай має значення 0.85. ФункціяC(T) дорівнює кількості посилань, що виходять зі сторінкиT. Тоді значення PageRank сторінкиA,PR(A), дорівнює:[7]
При цьому, значення PageRank — це випадкові величини сума яких для всіх сторінок дорівнюватиме 1.
Для обчислення PageRank Веб представляється у виглядіорієнтованого графу, вершини якого відповідають сторінкам, а ребра —гіперпосиланням між ними. Нехай до пошукового індексу внесеноn сторінок. Тоді для моделювання випадкової подорожі створюється матриця переходівM розміру. Елемент цієї матриці, що знаходиться в рядкуi та стовпчикуj має значення якщо сторінка з номеромj маєk вихідних посилань, серед яких є одне на сторінку з номеромi. Якщо такого посилання нема, то елемент має значення 0[1].
Розподіл ймовірностей знаходження випадкового мандрівника може бути описано вектор-стовпчиком, рядокj якого дорівнюватиме ймовірності перебування на сторінціj[17]. Цей вектор відповідатиме найпростішому, ідеалізованому варіанту PageRank.
Припустімо, що мандрівник може розпочати блукання з будь-якої ізn індексованих сторінок з однаковою ймовірністю. Тоді значення елементів початкового вектора дорівнюватимуть 1/n. Ймовірність знаходження на будь-якій зі сторінок на наступному кроці його блукання можна визначити обчисленням. Іще через крок —, і так далі. Таким чином, процес випадкового блукання єМарковським, а вектор розподілівv —власним для матриціM.
За умови, якщо:
Проте, через те, що граф гіперпосилань реальної мережі Веб не завжди зв'язний та має тупикові вершини, у формулу випадкового блукання доводиться запровадити можливість випадкового «стрибка» на іншу вершину. Таким чином, формула обчислення розподілів знаходження матиме вигляд:[18]
де:
Уявіть собі ідеального вебсерфера, який переміщається по всесвітній павутині. Нехай серфер відвідує сторінку 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, як мінімум спірних, а часто просто невірних.
Традиційні способи знаходження релевантних сторінок, у разі односкладових запитів не дають задовільних результатів, тому що попопулярних тем (наприклад «реферати», «робота») завжди знайдеться велика кількість сторінок з однаковою релевантністю. Для того, щоб якось впорядкувати такі сторінки, пошуковики вдаються до застосування різних інструментів[19].
Наприклад, видають першими ті сторінки, які мають велику відвідуваність (Rambler) або які присутні в каталозі (Yandex,Aport). В Google для цих цілей застосовують, зокрема, PageRank, що дає приголомшливі результати, і за короткий час Google став займати лідируючі позиції не тільки за обсягом бази, але і за якістю пошуку.
В березні 2016 року Google заявила, що усуне останню публічно доступну можливість дізнаватись PageRank сторінок — буде припинена робота модулів для веббраузерів (Toolbar PageRank). Однак, алгоритм PageRank й надалі буде використаний в пошуковій системі для оцінки якості сторінок[20].
Публічний доступ до оцінок PageRank було піддано критиці, оскільки це начебто сприяло поширеннюпошукової оптимізації з їїнегативними наслідками[21].
 | Цей розділпотребуєдоповнення.(вересень 2015) |
{{cite news}}:Пропущений або порожній|title= (довідка){{cite web}}: Обслуговування CS1: Сторінки з текстом «archived copy» як значення параметру title (посилання)[Архівовано 2002-05-06 уWayback Machine.] Стенфордський проект електронної бібліотеки, говорити. 18 серпня 1997 (архів 2002){{cite web}}: Обслуговування CS1: Сторінки з текстом «archived copy» як значення параметру title (посилання)[Архівовано 2013-12-02 уWayback Machine.] | |
|---|---|
| Нормативний контроль |
