Искусство мыслить рационально. Шорткаты в математике и в жизни - Маркус Дю Сотой

Иногда задача сводится к нахождению самого короткого пути от одной точки сети до другой. Можно ли воспользоваться для этого какими-нибудь хитрыми шорткатами? Возьмем, к примеру, сеть социальных связей между всеми жителями нашей планеты. Если выбрать случайным образом двух человек, какой длины будет кратчайшая цепочка дружеских отношений, по которой можно добраться от одного до другого? Такая цепочка оказывается на удивление короткой.

Впервые этот вопрос был сформулирован в рассказе «Звенья цепи», который написал в 1929 году венгерский писатель Фридьеш Каринти. Главный герой этого рассказа предполагает, что в цепочках такой сети существуют поразительные шорткаты:

До испытания этой вымышленной игры на практике прошло чуть более 30 лет. В знаменитом эксперименте, который провел в 1960-х годах американский психолог Стэнли Милгрэм, подопытным был выбран его друг, биржевой брокер, живший в Бостоне. Милгрэм решил взять два американских города, наиболее удаленных – как географически, так и социально – от бостонца: Омаху, штат Небраска, и Уичиту, штат Канзас. Случайно выбранным жителям этих городов были отправлены письма с просьбой переслать их брокеру, имя которого было указано в письмах. Однако в них не было его адреса. Если получатель не знал такого человека, его просили переслать письмо кому-нибудь из его сети знакомых – человеку, у которого, по мнению получателя письма, было больше возможностей переправить письмо адресату.

Из 296 отправленных писем 232 так и не пришли к бостонскому адресату. Но те, которые все же были получены, пересылались в среднем по шесть раз, считая от исходного получателя до конечного адресата. Между началом и концом цепочки действительно оказалось пять человек.

Этот эксперимент привел к появлению знаменитой концепции шести рукопожатий[121]. Это словосочетание популяризовала одноименная пьеса Джона Гуара. Ближе к концу пьесы одна из ее героинь говорит: «Я где-то читала, что всех на нашей планете отделяют друг от друга всего шесть человек. Шесть рукопожатий. Между нами и всеми остальными на планете. Президент Соединенных Штатов. Венецианский гондольер. Назови любого. Речь идет не только об известных людях. Это может быть кто угодно. Туземец из дождевых лесов. Житель Огненной Земли. Эскимос. С каждым обитателем нашей планеты меня связывает цепочка из шести человек».

В наш цифровой век мы стали более взаимосвязаны, чем когда-либо раньше, и сеть этих связей мы можем использовать гораздо легче, чем пересылая письма через почтовую службу Соединенных Штатов. В 2007 году было показано на наборе данных, извлеченных из 30 миллиардов сообщений, которыми обменялись 240 миллионов человек, что средняя длина цепочки между пользователями действительно равна 6. В работе, опубликованной в 2001 году, выяснилось, что любых двух пользователей Twitter можно связать цепочкой, в которую в среднем входят всего 3,43 пользователя.

Почему же в социальных сетях существуют такие шорткаты? Так, несомненно, бывает не в любых сетях. Если расположить 100 узлов по окружности и соединить друг с другом только соседние узлы, для перехода с одной стороны такой сети на другую потребуется 50 «рукопожатий». Сеть, в которой переход между двумя произвольными точками можно совершить через малое количество связей, называют тесным миром.

Оказывается, примеры тесного мира дает поразительно большое количество сетей. Речь идет не только о наших социальных или интернет-связях. Нейронные связи в любых организмах, от червя-нематоды C. elegans, имеющего всего 302 нервных узла, до человека, мозг которого содержит 86 миллиардов нейронов, по-видимому, образуют сети типа тесного мира. Это позволяет каждому нейрону такой системы быстро обмениваться сигналами с любым другим нейроном через небольшое количество синапсов. К категории тесного мира относятся и электроэнергетические сети, равно как и сети аэропортов и пищевые сети. Что же делает все эти сети тесными мирами?

Рис. 9.5. Пример сети тесного мира

Эту тайну раскрыли два математика, Дункан Ваттс и Стивен Строгац, написавшие о ней в статье, опубликованной в 1998 году в журнале Nature[122]. Если взять набор узлов и создать локальные связи между узлами, расположенными близко друг к другу, получится картина, похожая на нашу окружность, в которой соединение случайно выбранных узлов в разных частях сети требует длинных цепочек. Однако Ваттс и Строгац установили, что для появления шорткатов бывает достаточно всего нескольких глобальных связей, пересекающих всю сеть. Допустим, все жители Бостона знакомы друг с другом, но потом оказывается, что у кого-то из бостонцев есть тетка, живущая в Канзасе. Это дает возможность установить более глобальное соединение между этими двумя локальными сообществами. Такую же структуру мы находим в организме червя C. elegans. Нейроны расположены по окружности, но между далекими друг от друга нейронами есть связи, пересекающие эту окружность. По-видимому, и человеческий мозг имеет сходную архитектуру. В нем тоже есть множество локальных соединений и немногочисленные длинные синапсы, связывающие друг с другом разные части мозга.

Подобным же образом устроены сети аэропортов: несколько узловых аэропортов соединяют разные точки мира дальними рейсами. В дополнение к ним в каждом регионе есть много ближних рейсов, которые обеспечивают перевозки из узловых аэропортов в местные пункты.

При помощи своей математической модели Ваттс и Строгац смогли показать, что в сети с такой локально-глобальной конфигурацией и N узлами, в которой каждый из узлов связан с K другими, средняя длина пути между двумя произвольными точками определяется формулой

где log – логарифмическая функция, которую Джон Непер придумал в качестве вычислительного шортката. Если взять N равное 6,6 миллиарда и предположить, что у каждого человека есть 30 знакомых, число рукопожатий получается равным… 6,6.