Один з найвидатніших математиків 20-го століття Стефан Банах народився 125 років тому і у вересні у Львові відбудеться міжнародна конференція, присвячена цій даті. Результати Банаха в основному належали до функціонального аналізу та суміжних областей математики. Їх значення з роками лише зростає, що можна продемонструвати на прикладі теореми про нерухому точку для стискуючих відображень.
Нагадаю формулювання цієї теореми. Відображення f метричного простору (X,d) у себе називають стискуючим, якщо існує число c, 0 < c < 1, таке що d(f(x),f(y)) ≤ d(x,y) для всіх точок x,y простору X.
Теорема (С. Банах). Для кожного стискуючого відображення f повного метричного простору X у себе існує нерухома точка, тобто така точка x*, що f(x*)=x*.
У математиці теорему Банаха застосовують, наприклад, до доведення існування і єдиності розв'язку звичайних диференціальних рівнянь. Одним з найважливіших застосувань є доведення існування локально самоподібних множин (фракталів), які в свою чергу використовуються для компресії зображень.
Тут ми розглянемо, як теорему Банаха можна застосувати до задачі рангування веб-сторінок. Саме таке рангування нам пропонує відомий пошуковик Google. Авторами створенного біля 20 років тому алгоритму є С. Брін та Л. Пейдж. Отже, всю мережу зобразимо як орієнтований граф, у якому веб-сторінки є вершинами, а стрілка з вершини i у вершину j веде лише якщо існує лінк з i в j. У свою чергу, цей граф можна зобразити як матрицю H (гіперлінкову матрицю): її елементи Hij задаються умовою:
Hij = 0, якщо нема стрілки з вершини i у вершину j,
Hij = 1/Oi, де Oi - число стрілок, що виходять з вершини i (це число відмінне від нуля).
Модель телепортації основана на припущенні, що мандрівник по мережі йде за структурою мережі, але в якийсь момент робить випадковий стрибок на іншу сторінку, не пов’язану з попередніми. Гіперлінкова матриця H при цьому заміняється на матрицю G (Ґуґл-матрицю), що задається рівнянням (PageRank рівняння):
(тут n – число всіх веб-сторінок, а m – параметр, що відповідає за випадкове перескакування зі сторінки на сторінку, 0 < m < 1; усі елементи (n x n)-матриці рівні одиниці).
Тепер побудуємо метричний простір, де все відбуватиметься. Нехай X – множина всіх n-векторів (точніше, вектор-стовпчиків) з невід’ємними координатами, а метрика на X породжена l1-нормою. Іншими словами, це метрика таксиста (або, ще інакше, метрика Мангетена):
Тепер нескладно перевірити, що відображення, яке ставить у відповідність кожному елементові x простору X елемент Gx, коректно означене (тобто знову одержуємо елемент простору X) і стискуюче. За теоремою Банаха про нерухому точку існує вектор x* простору X, для якого x*=Gx*. Цей вектор і задає рангування веб-сторінок (за величинами координат).
Перевага теореми Банаха над алгебраїчними методами (можна застосувати теорему Перрона-Фробеніуса для знаходження x*) полягає в тому, що застосування ітерацій
x, Gx, GGx, GGGx, …
дає швидке наближення до шуканого вектора (для практики цього достатньо).
Недавно алгоритм Бріна-Пейджа запропонували застосувати майже без змін до рангування наукових журналів. При цьому роль лінка відіграє перехід від журналу до журналу за цитуваннями. Не вдаючись у деталі, зауважу лише, що чомусь далеко не всі хочуть вірити у наукометричні показники для журналів, публікацій у них і, як наслідок, авторів, хоча всі (принаймні з тих, кого я знаю) беззастережно користуються ґуґлом, довіряючи йому всеможливі пошуки.
На доступному з мережі матеріалі.
Рисунок автора.