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

Ответ получим в результате многократно повторяющегося следующего процесса. Алгоритм начинается с некоего предположения, затем обновляет все значения PageRank, распределяя жидкость в равных частях по исходящим ссылкам, после этого она проходит несколько кругов, пока не установится определенное состояние, при котором страницы получат причитающуюся им долю.

Изначально алгоритм задает равные доли, что позволяет каждой странице получить одинаковое количество PageRank. В нашем примере три страницы, и каждая из них начинает движение по алгоритму со счетом 1/3.

Начальные значения PageRank

Затем счет обновляется, отображая реальное значение каждой страницы. Правило состоит в том, что каждая страница берет свой PageRank с последнего круга и равномерно распределяет его по всем страницам, на которые ссылается. Следовательно, обновленное значение страницы X после прохождения первого круга по-прежнему равно 1/3, поскольку именно столько PageRank она получает от Z, единственной страницы, которая на нее ссылается. При этом счет страницы Y уменьшается до 1/6, так как она получает только половину PageRank от X после предыдущего круга. Вторая половина переходит к странице Z, что делает ее победителем на данном этапе, поскольку она добавляет себе еще 1/6 от страницы X, а также 1/3 от Y, и всего получается 1/2. Таким образом, после первого круга мы имеем следующие значения PageRank:

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

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

х' = z

y' = ½ x

z' = ½ 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 = ½ x

z = ½ x + y ,

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

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

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

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

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

Как поется в знаменитой песне 1960-х годов, один — самое одинокое число [141] Гарри Нилссон написал песню One, получившую известность под названием Three Dog Night. Она стала хитом, заняв пятое место в горячей сотне хитов Billboard Hot 100, а Эйми Манн создала ее великолепную версию для фильма «Магнолия». , хотя, вдвоем порой бывает еще хуже, чем одному. Возможно, так и есть, но и с простыми числами тоже все непросто.

Паоло Джордано объясняет почему в своем бестселлере The Solitude of Prime Numbers («Одиночество простых чисел») [142] См. P. Giordano, The Solitude of Prime Numbers (Pamela Dorman Books/Viking Penguin, 2010). . Это меланхолическая история любви двух затерянных в жизни людей, двух простых чисел, Маттиа и Аличе. В детстве им пришлось пережить трагедию, вследствие которой они практически перестали общаться с окружающими, но нашли друг в друге родственные души. Джордано пишет.

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