Относительное сравнение Нэнси с Уорреном позволяет разрешить и другой вопрос. Давайте условимся, что центральность каждого из них пропорциональна сумме центральностей их друзей. Этот подсчет будет подобен тому, что уже проделан нами ранее. Тем самым Нэнси получит некоторую долю очков Эллы и Майлса — из-за того, что будет учтена некоторая доля очков их друзей, и так далее. Эти повторные операции будут подобными, потому что Элла и Майлс получают очки от своих друзей, которые приходятся друзьями второй степени Нэнси, а те очки получены от их друзей, которые приходятся Нэнси друзьями третьей степени, и так далее{26}.
По счастью, система уравнений такого типа — когда центральность каждого человека пропорциональна сумме центральностей его друзей — вполне естественная и легкорешаемая математическая задача. Она появилась благодаря ряду научных работ известнейших математиков, живших с XVIII по ХХ век: это Эйлер, Лагранж, Коши, Фурье, Лаплас, Вейерштрасс, Шварц, Пуанкаре, фон Мизес и Гилберт. Гилберт назвал решения подобных задач «айген-векторами», или «собственными векторами», и это общепринятое современное название. Неудивительно, что собственные вектора фигурируют во всевозможных областях, от квантовой механики (уравнение Шрёдингера) до алгоритма eigenface, содержащего основные строительные блоки для программ распознавания лиц. Решая задачу собственного вектора в нашем примере, мы приходим к ответу: количество баллов у Нэнси приблизительно в 3 раза больше, чем у Уоррена, что мы и видим на рисунке 2.6{27}.
Рис. 2.6. Центральности по собственному вектору для каждого узла (человека). У Нэнси почти в 3 раза больше баллов, чем у Уоррена, хотя у обоих имеется одинаковое количество связей. Больше всего баллов у Майлса, хотя у Эллы наибольшая центральность по степени.
Инновация Брина и Пейджа заключалась в том, чтобы выстраивать веб-страницы согласно алгоритму, который они назвали PageRank. Он имеет прямое отношение к тому, что мы описали выше, и к вычислению собственного вектора. Правда, Брин и Пейдж не собирались распространять слухи по сети, но перед ними стояла сходная итеративная задача — так называемая задача случайного пользователя. Интернет-пользователь начинает с какой-то одной страницы, а затем случайным образом переходит оттуда по ссылке на другую страницу, причем он может с одинаковой вероятностью выбрать любую из ссылок. Затем все повторяется — пользователь таким же случайным образом блуждает по Сети{28}. Со временем, если мы вычислим относительное количество раз, которое пользователь посещает каждую страницу, мы получим собственный вектор. В этом случае баллы, которые присваиваются на каждом этапе, пропорциональны количеству ссылок, имеющихся на каждой странице.
Перед Брином и Пейджем стояли две трудности. Умозрительная задача — найти наиболее значимые страницы — решалась уже известным нам путем: следовало не смотреть на популярность страниц, а просчитывать, насколько хорошо они обеспечены связями в этом итеративном, айген-векторном смысле. Более практическая задача заключалась в том, чтобы внедрить этот принцип в колоссальном масштабе всей Паутины, а это значило, что нужно облазить всю сеть и проиндексировать страницы, накопить данные о содержании каждой страницы и об имеющихся на ней ссылках, а затем произвести итеративные вычисления, чтобы определить их сетевое положение. Одно дело — производить подобные расчеты для Нэнси и Уоррена в нашей маленькой сети, показанной выше, и совсем другое — проделывать то же самое для миллиардов страниц, тем более что они постоянно меняют содержание и ссылки.
Брин с Пейджем разработали алгоритм, основанный на такого рода вычислениях и хорошо подходивший для огромных сетей, назвали его BackRub и запустили в работу на стэнфордских серверах. Название BackRub (буквально backrub значит «массаж спины») происходит от backlink — «обратной ссылки», то есть такой ссылки, которая приводит пользователя на ту или иную страницу. BackRub быстро перерос студенческие аккаунты, которые Брин и Пейдж завели на стэнфордских серверах, и в 1997 году они уже перенесли поисковую машину в другое место и назвали ее Google. Это было чуть видоизмененное название числа гугол (googol) — 10100, что говорило об огромном размере Всемирной сети, которую удалось-таки покорить их алгоритму. Всех, кому доводилось искать что-либо в интернете в ранние годы его существования, поражала способность Google находить полезные страницы. К тому времени имелось уже немало поисковых машин, конкурировавших между собой, и, как правило, пользователям приходилось перепробовать их все, чтобы найти в сети нужную страницу — часто безрезультатно. В 1998 году PC Magazine сообщил, что Google «на удивление ловко и удачно находит полезные страницы», и поместил его в сотню самых важных веб-страниц{29}. Остальное — уже история{30}.
26
Есть и легкое различие — в том, что теперь мы иногда ведем двойной счет: ведь одним из семи друзей Эллы является Нэнси, а значит, мы и саму Нэнси причисляем к друзьям второй степени. На самом деле, такой двойной счет немного облегчает арифметику, так как на каждом этапе нам нужно лишь установить количество связей, но не нужно вспоминать, кого мы уже считали, а кого нет. Влияние двойного счета обсуждается в работе Banerjee, Chandrasekhar, Duflo, and Jackson (2013, 2015).
27
Если вам интересны подробности показателей на рисунке 2.6, то квадраты показателей центральности в сумме дают единицу, так что вектор показателей центральности нормализован в обычном математическом смысле (в соответствии с L2 или с евклидовой нормой).
28
Их алгоритм учитывал и некоторые случайные перескоки к новым узлам, откуда весь процесс начинался заново, — чтобы была уверенность, что все не зациклится на ограниченном наборе страниц, которые просто ведут одна к другой.
29
Поисковые машины, включая Google, быстро развивались по мере того, как компьютеры становились все более мощными, а наш опыт обращения с Сетью — более богатым. Сейчас подобные машины содержат более полную информацию и о пользователях, и о разных веб-страницах, и более индивидуальную сетевую информацию о том, как люди перемещаются по Сети и что же они на самом деле ищут. Кроме того, Сеть в наши дни — своего рода подвижная мишень, ее содержание постоянно изменяется. Тем не менее, в принципе идея PageRank ознаменовала важный прорыв, точно отобразивший характер сетевой информации.
30
Отслеживание связей дальше первого уровня важно во многих средах, не только для работы поисковых машин и распространения информации. Вариации подобных итеративных вычислений центральности, причем с использованием собственных векторов, появлялись в литературе, посвященной социальным сетям, за несколько десятилетий до появления Google; стоит отметить новаторскую работу Лео Каца (Leo Katz) 1950-х годов и более позднюю, 1970-х годов работу Фила Боначича (Phil Bonacich), формализовавшую подобные методы. Вариации определения собственного вектора использовались для нахождения «важнейших фигур» в сетях, занятых нелегальной деятельностью, так как преступность имеет социальную составляющую: люди узнают друг от друга о возможности заняться чем-то незаконным и втягивают друг друга в преступную деятельность, а самые центральные фигуры в подобных сетях оказывают наибольшее влияние на других участников (см., напр., Lindquist and Zenou [2014]). Подобные критерии определения центральности применялись и для изучения общения между инвесторами, чтобы можно было предсказывать, у кого из инвесторов окажется наиболее высокая прибыль на фондовой бирже (см. Ozsoylev, Walden, Yavuz, and Bildik [2014]).