Чтение онлайн

на главную - закладки

Жанры

Удовольствие от Х.Увлекательная экскурсия в мир математики от одного из лучших преподавателей в мир

Строгац Стивен

Шрифт:

Значения PageRank после одного обновления

В последующих кругах правило обновления остается прежним. Если обозначить через x, y, z текущий счет страниц X, Y и Z, то в результате обновления получим такой счет:

х' = z

y' = 1/2 x

z' = 1/2 x + y,

где

штрихи говорят о том, что произошло обновление. Подобные многократно повторяющиеся вычисления удобно выполнять в электронной таблице (или вручную, если сеть маленькая, как в нашем случае).

После десяти повторений обнаружим, что от обновления к обновлению цифры практически не меняются. К этому моменту доля X составит 40,6% от всего PageRank, доля Y — 19,8%, а Z — 39,6%. Эти значения подозрительно близки к числам 40, 20 и 40%, что говорит о том, что алгоритм должен к ним сходиться.

Так и есть. Эти предельные значения алгоритм Google и определяет для сети как PageRank.

Предельные значения PageRank

Вывод для данной маленькой сети такой: страницы X и Z одинаково важны, несмотря на то что у Z в два раза больше входящих ссылок. Это и понятно: страница X равна Z по значимости, поскольку она получает от нее полное одобрение, однако взамен дает ей лишь половину своего одобрения. Вторая половина отправляется Y. Это также объясняет, почему Y достается только половина от долей X и Z.

Интересно, что эти значения можно получить, не прибегая к многократным итерациям. Надо просто подумать над условиями, определяющими стационарное состояние. Если после очередного обновления ничего не меняется, то x' = x, y' = y и z' = z. Поэтому, заменив переменные со штрихом в уравнениях обновлений на их эквиваленты без штрихов, получим систему уравнений

х = z

y = 1/2 x

z = 1/2 x + y,

при решении которой x = 2y = z. Поскольку сумма значений x, y и z должна равняться 1, отсюда следует, что x = 2/5, y = 1/5 и z = 2/5, что соответствует ранее найденным значениям.

Давайте на мгновение вернемся назад и посмотрим, как все это вписывается в широкий

контекст линейной алгебры. Приведенное выше уравнение стационарного состояния, так же как и уравнения обновления, содержащие штрихи, — типичные примеры линейных уравнений. Они называются линейными, поскольку описывают прямые линии: переменные x, y, z в этих уравнениях в первой степени, так же как и в знакомом нам из курса алгебры средней школы уравнении прямой y = mx + b.

Линейные уравнения, в противоположность уравнениям, содержащим нелинейные члены, например x2 или yz, либо sin x, решаются относительно просто. Сложности начинаются там, где в уравнениях присутствует огромное количество переменных, как это происходит в реальной сети. Поэтому одной из центральных задач линейной алгебры является разработка более быстрых алгоритмов для решения больших систем уравнений. Даже незначительные усовершенствования этих алгоритмов ощущаются практически во всех сферах жизни — от расписания авиарейсов до сжатия изображения.

Однако самой существенной победой линейной алгебры, с точки зрения ее роли в повседневной жизни, безусловно, стало решение парадокса дзен-буддизма для ранжирования страниц. «Страница хороша в той мере, в какой хорошие страницы ссылаются на нее». Переведенный в математические символы, этот критерий становится алгоритмом PageRank.

Поисковик Google стал тем, чем он есть сегодня, после решения уравнения, которое и мы с вами только что решили, но с миллиардами переменных — и, соответственно, с миллиардными прибылями.

25. Самые одинокие числа

Как поется в знаменитой песне 1960-х годов, один — самое одинокое число111, хотя, вдвоем порой бывает еще хуже, чем одному. Возможно, так и есть, но и с простыми числами тоже все непросто.

Паоло Джордано объясняет почему в своем бестселлере The Solitude of Prime Numbers («Одиночество простых чисел»)112. Это меланхолическая история любви двух затерянных в жизни людей, двух простых чисел, Маттиа и Аличе. В детстве им пришлось пережить трагедию, вследствие которой они практически перестали общаться с окружающими, но нашли друг в друге родственные души. Джордано пишет.

Простые числа делятся только на единицу и самих себя. Они занимают свое место в бесконечном ряду простых чисел, которые, как и остальные числа, зажаты между двумя другими, но на один шаг дальше, чем предыдущие. Эти числа подозрительны и одиноки, и Маттиа казалось, что они волшебные. Иногда он думал, что они очутились в этом ряду по ошибке, как жемчужины, нанизанные на нитку ожерелья. А порой ловил себя на мысли, что они тоже предпочли бы быть обычными числами, однако по какой-то причине не сложилось. [...]

Поделиться:
Популярные книги

Вперед в прошлое 2

Ратманов Денис
2. Вперед в прошлое
Фантастика:
попаданцы
альтернативная история
5.00
рейтинг книги
Вперед в прошлое 2

Главная роль 4

Смолин Павел
4. Главная роль
Фантастика:
попаданцы
альтернативная история
5.00
рейтинг книги
Главная роль 4

Крестоносец

Ланцов Михаил Алексеевич
7. Помещик
Фантастика:
героическая фантастика
попаданцы
альтернативная история
5.00
рейтинг книги
Крестоносец

Отмороженный 3.0

Гарцевич Евгений Александрович
3. Отмороженный
Фантастика:
боевая фантастика
рпг
5.00
рейтинг книги
Отмороженный 3.0

Я еще не князь. Книга XIV

Дрейк Сириус
14. Дорогой барон!
Фантастика:
юмористическое фэнтези
попаданцы
аниме
5.00
рейтинг книги
Я еще не князь. Книга XIV

Идеальный мир для Лекаря 26

Сапфир Олег
26. Лекарь
Фантастика:
аниме
фэнтези
5.00
рейтинг книги
Идеальный мир для Лекаря 26

Кодекс Крови. Книга IV

Борзых М.
4. РОС: Кодекс Крови
Фантастика:
фэнтези
попаданцы
аниме
5.00
рейтинг книги
Кодекс Крови. Книга IV

Снегурка для опера Морозова

Бигси Анна
4. Опасная работа
Любовные романы:
современные любовные романы
5.00
рейтинг книги
Снегурка для опера Морозова

Шериф

Астахов Евгений Евгеньевич
2. Сопряжение
Фантастика:
боевая фантастика
постапокалипсис
рпг
6.25
рейтинг книги
Шериф

Измена. Он все еще любит!

Скай Рин
Любовные романы:
современные любовные романы
6.00
рейтинг книги
Измена. Он все еще любит!

Неудержимый. Книга III

Боярский Андрей
3. Неудержимый
Фантастика:
фэнтези
попаданцы
аниме
5.00
рейтинг книги
Неудержимый. Книга III

Чужая семья генерала драконов

Лунёва Мария
6. Генералы драконов
Фантастика:
фэнтези
5.00
рейтинг книги
Чужая семья генерала драконов

Адвокат вольного города

Парсиев Дмитрий
1. Адвокат
Фантастика:
городское фэнтези
альтернативная история
аниме
5.00
рейтинг книги
Адвокат вольного города

Изгой Проклятого Клана. Том 2

Пламенев Владимир
2. Изгой
Фантастика:
попаданцы
аниме
фэнтези
фантастика: прочее
5.00
рейтинг книги
Изгой Проклятого Клана. Том 2