Кому нужна математика? Понятная книга о том, как устроен цифровой мир

Четыре виртуальных рукопожатия

Помимо того что задача подсчета важна сама по себе, она находит и другие, совершенно неожиданные применения.

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

Вопросы подобного рода имеют длинную историю. В конце 1960-х годов социолог Стэнли Милграм провел свой знаменитый эксперимент. Он раздал случайным людям в штатах Небраска и Канзас письма, адресованные брокеру из Бостона. Географически и по роду занятий эти люди были достаточно далеки от адресата. По правилам эксперимента, участники могли переслать письма только своим знакомым, которые должны были передать их дальше, своим знакомым, и так далее, пока они в конце концов не достигнут адресата. Из 296 писем большинство затерялось в дороге, но 64 письма дошли-таки по назначению. При этом оказалось, что цепочка, связывающая совершенно незнакомых людей, на удивление короткая. В среднем отправителя и адресата разделяло всего 5 человек! На рис. 7.1 мы схематически изобразили, как письмо пересылалось всего шесть раз, через пять промежуточных человек.

Рис. 7.1. Схематическое изображение эксперимента Стэнли Милграма. Участники могли переслать письмо только своим знакомым. Письмо от отправителя до адресата пересылалось 6 раз, через 5 разных человек

Так родилось понятие «шести рукопожатий». Если вы пожмете руку всем своим знакомым, ваши знакомые пожмут руку своим знакомым и так далее, то понадобится всего шесть рукопожатий, чтобы соединить вас с любым человеком на Земле!

Эксперимент Милграма не идеален, неслучайно столько писем затерялось в дороге. Но в то время просто не было другого способа выяснить, кто, с кем и через кого знаком. Зато сейчас таких данных сколько угодно.

Чтобы провести подобный эксперимент в «Фейсбуке», не нужно даже беспокоить участников. На сервере сети хранится полная информация, кто с кем дружит. Остается только вычислить количество «виртуальных рукопожатий», отделяющих одного пользователя от другого. Можем ли мы это сделать? Именно такой вопрос задали научные сотрудники «Фейсбука» профессору Миланского университета Себастьяно Винье.

И Себастьяно, и сотрудники социальной сети понимали, что это колоссальная задача. Неслучайно она не была решена раньше. У «Фейсбука» свыше 700 миллионов активных пользователей, то есть более

пар пользователей. И нужно вычислить длину цепочки для каждой пары! Но дело не только в этом. Ключевая проблема – опять же в количестве оперативной памяти, и возникает она потому, что между двумя пользователями не одна, а несколько цепочек разной длины. Для примера посмотрим на маленькую социальную сеть на рис. 7.2. А отделяет от В одно рукопожатие или два – через Г. Разных цепочек очень много, потому что друзья друзей зачастую наши друзья. В социальных сетях это известный, проверенный и доказанный феномен. При этом нас интересует самая короткая цепочка.

Рис. 7.2. Социальная мини-сеть. Кружками с буквами обозначены пользователи, линия между двумя пользователями означает, что они друзья. Мы обозначили пользователя А светло-серым цветом, а его друзей – серым. Темно-серым цветом обозначены пользователи, которых от А отделяют два рукопожатия

Компьютеру совсем нетрудно считать с диска всех «друзей друзей» пользователя А. Но только некоторых из них отделяет от А одно рукопожатие, а некоторых – два. Например, на рис. 7.2 и В, и Ж – это друзья друзей А. Но В друг А, а Ж – нет. Как определить, что Ж на расстоянии двух рукопожатий? Только одним способом – запомнить всех друзей А. Именно так работает самый распространенный метод под названием поиск в ширину.

Если теперь добавить всех «друзей друзей друзей», а потом их друзей и так далее, то нужно запоминать всех, кого мы видели на расстоянии один, два, три… После пяти-шести шагов мы уже видели практически всех пользователей сети. Держать в оперативной памяти 700 миллионов имен, или разных чисел, – ну просто абсолютно нереально!

Сотрудники «Фейсбука» поверили в успех, потому что Себастьяно Винья и его коллеги придумали абсолютно иной способ подсчета числа рукопожатий. Они заметили, что самая главная проблема – необходимость запоминать увиденных пользователей – совершенно аналогична задаче о подсчете. А последнюю можно решить методом HyperLogLog.

Для интересующихся читателей ниже во врезках мы объясняем основные идеи с помощью примера на рис. 7.2. Этот текст не требует математической подготовки, но, если вы не хотите вдаваться в подробности, можете его пропустить.