Понеділок, 31 липня 2017 Автор Опубліковано в Cтатті & Публікації

Ґуґл і теорема Банаха про нерухому точку

(4 голосів)
Перегляди: 15970 разів
Ґуґл і теорема Банаха про нерухому точку Ґуґл і теорема Банаха про нерухому точку

Один з найвидатніших математиків 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, …

дає швидке наближення до шуканого вектора (для практики цього достатньо).

Недавно алгоритм Бріна-Пейджа запропонували застосувати майже без змін до рангування наукових журналів. При цьому роль лінка відіграє перехід від журналу до журналу за цитуваннями. Не вдаючись у деталі, зауважу лише, що чомусь далеко не всі хочуть вірити у наукометричні показники для журналів, публікацій у них і, як наслідок, авторів, хоча всі (принаймні з тих, кого я знаю) беззастережно користуються ґуґлом, довіряючи йому всеможливі пошуки. 

На доступному з мережі матеріалі.

Рисунок автора.

 

М.М. Зарічний

доктор фізико-математичних наук, професор кафедри алгебри, топології та основ математики, заслужений професор Львівського національного університету імені Івана Франка

Додати коментар

Захисний код
Оновити

Наші контакти

Ідея, дизайн, верстка і т.д.:
Олег Романів