Страница 7 из 10
Относительное сравнение Нэнси с Уорреном позволяет разрешить и другой вопрос. Давайте условимся, что центральность каждого из них пропорциональна сумме центральностей их друзей. Этот подсчет будет подобен тому, что уже проделан нами ранее. Тем самым Нэнси получит некоторую долю очков Эллы и Майлса – из-за того, что будет учтена некоторая доля очков их друзей, и так далее. Эти повторные операции будут подобными, потому что Элла и Майлс получают очки от своих друзей, которые приходятся друзьями второй степени Нэнси, а те очки получены от их друзей, которые приходятся Нэнси друзьями третьей степени, и так далее{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}.
Распространение микрофинансирования
Хотя история с Google наводит на мысль о том, что алгоритм, основанный на вычислении собственного вектора, превосходит все прочие альтернативы, алгоритмы для поисковых машин весьма сложны, так что успех Google вполне может объясняться и другими различиями в алгоритмах. Было бы прекрасно увидеть более полную картину того, какое именно значение имеет положение чьих-то друзей. А еще BackRub распознавал страницы по тому, насколько легко их найти, тогда как во многих ситуациях нам интересно совсем другое: насколько влиятелен тот или иной человек с точки зрения установления контакта с другими людьми.
Именно об этом я думал, когда приехал в 2006 году в Массачусетский технологический институт (MIT) и, общаясь с профессором Абхиджитом Банерджи, моим другом, говорил о том, как было бы прекрасно испытать подобные различия в действии. По счастливому стечению обстоятельств (как уже нередко бывало), Абхиджит оказался именно тем человеком, с которым мне и следовало об этом поговорить. Оказалось, что Эстер Дюфло, еще одна преподавательница MIT, через свою сестру Анни поддерживает связь с одним банком в Южной Индии, а именно с банком BSS (Baratha Swamukti Samsthe), который планирует запустить новую программу микрофинансирования как раз посредством “сарафанного радио”. (Сейчас можно увидеть эту сеть в действии, и связанный с ней исследовательский проект успешно стартовал.) Программа “сарафанного радио” предоставила нам идеальную возможность проследить за тем, какую роль играет сетевая структура в распространении информации, а еще она позволила нам проверить, какой именно критерий центральности лучше всего может предсказать способность того или иного человека распространять информацию. Вместе с Абхиджитом, Эстер, а также Аруном Чандрасекаром, который был тогда аспирантом MIT (а еще, так совпало, его семья была родом из Карнатаки – индийского штата, о котором шла речь), мы начали исследование, которому суждено было стать длительным.
Зачинателем революции в микрофинансировании был Мухаммад Юнус. В 1970-е годы он основал в Бангладеш Grameen Bank, а в 1980-е начал выдавать множеству людей совсем маленькие денежные кредиты. За это новшество в 2006 году Юнус и его Grameen Bank были удостоены Нобелевской премии мира. Новшество было простым, но очень разумным. Во всем мире многие кредиты привязаны к покупке недвижимости или автомобиля, которые служат залоговым поручительством, или помогают дотянуть до следующей получки людям с трудовым стажем, или выдаются вместе с кредитной карточкой людям с проверенной кредитной историей, а потом из неплательщиков жестко выколачивают деньги специальные коллекторские агентства. А микрозаймы же были рассчитаны на крайне бедных людей, которые периодически сидели без работы, из имущества им заложить было почти нечего, и в таких условиях попытки коллекторов стрясти с них долг оказались бы неоправданно дорогостоящими. Так в чем же состояло новшество?
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]).