UK 
EnglishТипова
Polski🔗 PageRank
Оригінальний рейтинговий алгоритм Google: оцінка сторінки = (1−d)/N плюс d · сума внесків від вхідних посилань. Дивіться, як збігається степенева ітерація — або симулюйте випадкового серфера, що приходить до того ж стаціонарного розподілу.
Про цю симуляцію
Ця симуляція візуалізує PageRank — алгоритм, який засновники Google використовували для ранжування вебсторінок за важливістю. Ви будуєте орієнтований граф сторінок і посилань, а потім спостерігаєте, як оцінки рангу збігаються або через степеневу ітерацію (повторне застосування формули PageRank до всього вектора одразу), або через випадкового серфера, який переходить за посиланнями та іноді телепортується. Коефіцієнт затухання d (за замовчуванням 0,85) визначає, скільки рангу передається через посилання, а скільки «витікає» через випадкову телепортацію, а «висячі» вузли (сторінки без вихідних посилань) рівномірно перерозподіляють свій ранг так, щоб сума завжди дорівнювала 1.
🔬 Що показано
Кожен вузол — це сторінка, чий ранг p повторно оновлюється за формулою p ← (1−d)/N + d·Mp, де M кодує структуру посилань, а N — кількість сторінок. Радіус вузла зростає разом із його рангом, «висячі» вузли позначені червоним, а вставка збіжності показує логарифм L1-зміни за ітерацію, щоб було видно, як процес наближається до стаціонарного розподілу.
🎮 Як користуватись
Оберіть готовий приклад (Підручниковий, Пастка рангу, Приклад Бріна-Пейджа, Зіркоподібний граф) або створіть власний за допомогою інструментів «Додати вузол», «Намалювати ребро» та «Видалити»; перетягуйте вузли, щоб змінити розташування. Перемикайтеся між режимами «Степенева ітерація» та «Випадковий серфер», налаштовуйте повзунок затухання (0,5–0,95) та швидкість, потім натисніть «Крок» для однієї ітерації або «Авто» для перегляду повної збіжності. Панель статистики показує кількість вузлів/ребер, поточне затухання, кількість ітерацій, L1-зміну, суму рангів, сторінку з найвищим рангом і кількість «висячих» вузлів.
💡 Чи знали ви?
PageRank математично є ланцюгом Маркова: довгострокова частота відвідування кожної сторінки випадковим серфером точно дорівнює її оцінці PageRank. Саме тому два режими цієї симуляції — степенева ітерація над вектором рангу та симуляція реального випадкового мандрівника — збігаються до однакових чисел.
Часті питання
Що таке PageRank і чому він був важливим?
PageRank — це алгоритм, розроблений Ларрі Пейджем і Сергієм Бріном, який оцінював вебсторінки, розглядаючи посилання зі сторінки A на сторінку B як «голос» за B, зважений за власною важливістю A. Він дав змогу Google ранжувати результати пошуку за позицією сторінки в загальній структурі посилань вебу, а не лише за збігом ключових слів, що було головною причиною, чому його результати здавалися доречнішими за попередні пошукові системи.
Як працює коефіцієнт затухання d?
Коефіцієнт затухання, зазвичай встановлений на рівні 0,85, — це ймовірність того, що випадковий серфер продовжує переходити за посиланнями, а не стрибає на випадкову сторінку. У формулі оновлення p ← (1−d)/N + d·Mp член (1−d)/N розподіляє невеликий базовий ранг на кожну сторінку («телепортацію»), тоді як член d·Mp переносить ранг вздовж реальних посилань. Без затухання ранг міг би назавжди застрягти в циклах або пастках; із затуханням процес гарантовано збігається.
Що таке степенева ітерація і чому вона збігається?
Степенева ітерація повторно множить вектор рангу на матрицю посилань (із домішкою затухання й телепортації), поки вектор не перестане суттєво змінюватися. Це працює, тому що оновлення є лінійним оператором з єдиним домінантним власним вектором — стаціонарним розподілом PageRank, — тож повторне застосування наближає будь-який початковий вектор до нього. Показник L1-зміни та графік збіжності в симуляції демонструють це зменшення різниці між послідовними ітераціями.
Що відбувається з «висячими» вузлами або пастками рангу?
«Висячий» вузол — це сторінка без вихідних посилань, тому вона б інакше «захоплювала» будь-який ранг, що надходить у неї. Симуляція вирішує це, беручи весь ранг, утримуваний усіма «висячими» вузлами, і перерозподіляючи його рівномірно між усіма сторінками на кожній ітерації, що зберігає загальний ранг рівним 1 і запобігає непомітному зникненню рангу. Готовий приклад «Пастка рангу» демонструє невеликий кластер сторінок, які інакше поглинали б ранг без затухання.
Як випадковий серфер пов'язаний зі степеневою ітерацією?
Модель випадкового серфера симулює реального мандрівника, який на кожному кроці переходить за випадковим вихідним посиланням з імовірністю d або телепортується на рівномірно випадкову сторінку з імовірністю 1−d. Протягом багатьох кроків частка часу, проведеного на кожній сторінці, збігається до того ж розподілу, який степенева ітерація обчислює аналітично, оскільки обидва підходи описують той самий базовий ланцюг Маркова. Ця симуляція дозволяє порівняти обидва методи: степенева ітерація збігається за кілька кроків, тоді як випадковому серферу потрібно набагато більше відвідувань, перш ніж його емпіричні частоти стабілізуються.