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

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

Жанры

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

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

Шрифт:

Значения 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. Это меланхолическая история любви двух затерянных в жизни людей, двух простых чисел, Маттиа и Аличе. В детстве им пришлось пережить трагедию, вследствие которой они практически перестали общаться с окружающими, но нашли друг в друге родственные души. Джордано пишет.

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

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

Я снова не князь! Книга XVII

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

На границе империй. Том 10. Часть 2

INDIGO
Вселенная EVE Online
Фантастика:
космическая фантастика
5.00
рейтинг книги
На границе империй. Том 10. Часть 2

Маяк надежды

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

Законы Рода. Том 3

Flow Ascold
3. Граф Берестьев
Фантастика:
фэнтези
аниме
5.00
рейтинг книги
Законы Рода. Том 3

Бастард Императора. Том 8

Орлов Андрей Юрьевич
8. Бастард Императора
Фантастика:
попаданцы
аниме
фэнтези
5.00
рейтинг книги
Бастард Императора. Том 8

Первый среди равных. Книга III

Бор Жорж
3. Первый среди Равных
Фантастика:
попаданцы
аниме
фэнтези
6.00
рейтинг книги
Первый среди равных. Книга III

Восход. Солнцев. Книга I

Скабер Артемий
1. Голос Бога
Фантастика:
фэнтези
попаданцы
аниме
5.00
рейтинг книги
Восход. Солнцев. Книга I

На границе империй. Том 7. Часть 5

INDIGO
11. Фортуна дама переменчивая
Фантастика:
боевая фантастика
космическая фантастика
попаданцы
5.00
рейтинг книги
На границе империй. Том 7. Часть 5

Real-Rpg. Еретик

Жгулёв Пётр Николаевич
2. Real-Rpg
Фантастика:
фэнтези
8.19
рейтинг книги
Real-Rpg. Еретик

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

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

Газлайтер. Том 3

Володин Григорий
3. История Телепата
Фантастика:
попаданцы
альтернативная история
аниме
5.00
рейтинг книги
Газлайтер. Том 3

СД. Том 13

Клеванский Кирилл Сергеевич
13. Сердце дракона
Фантастика:
фэнтези
6.55
рейтинг книги
СД. Том 13

Хорошая девочка

Кистяева Марина
Любовные романы:
современные любовные романы
эро литература
5.00
рейтинг книги
Хорошая девочка

Вторая жизнь майора. Цикл

Сухинин Владимир Александрович
Вторая жизнь майора
Фантастика:
героическая фантастика
боевая фантастика
попаданцы
5.00
рейтинг книги
Вторая жизнь майора. Цикл