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

 

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

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

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

 

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

 

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

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

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

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

 

 

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

 

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

 

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

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

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

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

 

Применение HyperLogLog ‑счетчика для подсчета числа рукопожатий

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

Присваиваем хеш‑значение каждому пользователю. Запускаем счетчик HyperLogLog и просматриваем пользователей начиная с А. На каждом шаге HyperLogLog будет сообщать, сколько всего разных пользователей мы видели. Оказывается, это все, что нам нужно.

Начнем с пользователя А. Это один пользователь, на расстоянии ноль рукопожатий от самого себя. Теперь посмотрим на его друзей:

 

Б В Г Д Е,

 

HyperLogLog сообщит нам, что всего с момента запуска мы видели 6 пользователей. Минус А, получаем 5 пользователей на расстоянии одного рукопожатия. Теперь к А и его друзьям добавляем всех тех, кто дружит с друзьями А:

 

друзья Б: А, Ж,

друзья В: А, Г, Ж, З

друзья Г: А, В, И

друзья Д: А, Е

друзья Е: А, Д.

 

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

 

9 − 1 − 5 = 3

 

пользователя на расстоянии двух рукопожатий от А. Заметьте, что нам не нужно запоминать самих друзей А, а только их количество!

В данном случае больше пользователей у нас нет. В реальности процесс продолжается. На третьем шаге мы добавляем всех «друзей друзей друзей». После этого HyperLogLog опять сообщает, сколько разных пользователей мы видели до сих пор. Вычитаем из этого числа количество пользователей на расстоянии ноль, один и два и получаем число пользователей, которых от А отделяют ровно три рукопожатия. И так далее.

Процесс будет завершен, когда мы увидим всех пользователей сети. Как вы помните, HyperLogLog держит в памяти лишь максимальное число нулей в хеш‑значении. В дополнение к этому надо запомнить только число пользователей на расстоянии одного, двух, трех и так далее рукопожатий. Это тоже занимает очень скромный объем оперативной памяти.

 

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

Оказалось, что двух пользователей «Фейсбука» в среднем разделяет не шесть, а всего 4,74 рукопожатия! Статья Себастьяно Виньи и соавторов {25} быстро обрела известность в научном мире и за его пределами. О ней писали ВВС и New York Times. Результаты уже сейчас попали в популярную литературу и специальные учебники. Виртуальный мир оказался еще теснее, чем реальный – тот, в котором мы живем!

 

 

Филипп Флажоле

Филипп Флажоле умер в 2011 году, когда работа над внедрением HyperLogLog была в самом разгаре. Блог под названием «HyperLogLog – краеугольный камень инфраструктуры больших данных» {26} был написан в 2012 году. Статья {27} о 4,74 виртуальных рукопожатий в «Фейсбуке» вышла в том же 2012 году, а статья сотрудников Google {28} – в 2013‑м. Система Redis внедрила HyperLogLog в 2014 году. В честь Филиппа Флажоле команды HyperLogLog начинаются с его инициалов PF.

Нам неизвестно, успел ли Флажоле узнать, что его результаты уже стояли на пороге широкого внедрения. Мы закончим последними фразами из блога {29}, где автор подробно и с большим энтузиазмом объясняет HyperLogLog широкой технической публике:

…Мне очень жаль, что я не был знаком с ним лично. Я уверен, что его труды будут жить дальше, но наука и индустрия, безусловно, потеряли выдающийся интеллект. Продолжай считать, Филипп, мы на тебя рассчитываем!

 

Приложение для подготовленного читателя к главе 7

 

 

Глава 8

Миллион аукционов в минуту

 

Первая страница поисковика

 

Что бы мы ни собирались предпринять – от ремонта квартиры до поиска работы и планирования отпуска, – последние 10–15 лет практически любое дело мы начинаем с белой странички поисковой системы. Популярность и полезность поисковиков трудно переоценить. Один Google обрабатывает более 100 миллиардов запросов в месяц!

Мы вводим запрос, и буквально в считаные секунды на экране появляется первая страница результатов поиска. Ее содержание – тема особенно интересная, потому что большинство из нас дальше первой страницы не заходят, это широко известная статистика. Наверное, кое‑какие принципы заполнения первой страницы вы уже давно заметили. Например, если вы ищете что‑то связанное с товарами и услугами, то на самом видном месте – вверху первой страницы – появляется реклама. Рынок онлайн‑рекламы у поисковиков просто колоссальный. Реклама – это источник доходов «Яндекса» практически на сто процентов. Число рекламодателей Google уже давно превысило миллион, а доход Google от онлайн‑рекламы в 2015 году оценивался в 44 с лишним миллиарда долларов.

Почему почти у всех крупных поисковиков онлайн‑реклама выглядит именно так, как сегодня на нашем экране? Почему вы видите именно эти объявления и в этом порядке? За каждым объявлением скрываются глубокие математические идеи и не одна, а целых три Нобелевские премии. В этой главе мы расскажем о математике онлайн‑рекламы.

 

Стоимость за один клик

 

Поисковики в их современном виде появились сравнительно недавно – в конце 1990‑х годов. Реклама – гораздо раньше: газеты, щиты, телевизионные ролики. Мы расскажем о развитии и особенностях онлайн‑рекламы примерно так, как это сделал Сергей Измалков – профессор Российской экономической школы, признанный эксперт в этой области.

Все мы настолько привыкли к рекламе в поисковиках, что первый тезис Сергея застает нас врасплох: «Изначально, когда поисковые системы только‑только появились, выгода такой рекламы для рекламодателей была совершенно неочевидна!»

Самый первый вопрос: кто увидит эту рекламу? С журналами, например, все понятно. Сноуборд надо рекламировать в спортивном журнале, а косметику – в женском. Но интересы пользователя за экраном компьютера могут быть абсолютно любыми. Показывать рекламу косметики человеку, который зашел искать байдарочные маршруты Кировской области, практически бесполезно.

Так возникла идея рекламы по ключевой фразе. Вместо «журнала» рекламодатель выбирает в поисковом запросе интересующие его слова. Скажем, если компания устанавливает пластиковые окна, то они могут выбрать запросы пластиковые окна, окна, ремонт квартиры и тому подобные. А на другие запросы, например пластиковые тарелки, их реклама не появится. Поисковик точно знает, что интересует пользователя в данный момент. На запрос жираф можно предложить туры в Африку, а на запрос рецепт пиццы – мастер‑класс по ее приготовлению (а не рекламу пиццерий!).

Такой «контекстной» рекламой пользуются все поисковые системы и все крупные сайты, включая «Фейсбук» и «Ютуб». Это был первый шаг к успеху онлайн‑рекламы.

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

Пришлось задуматься, зачем в принципе нужна онлайн‑реклама? Самый разумный и прагматичный ответ абсолютно очевиден: чтобы привести потенциальных покупателей на сайт. Именно за это готовы платить рекламодатели. И это прекрасно, потому что чисто технически зарегистрировать, перешел пользователь с поисковика на сайт рекламодателя или нет, очень легко!

Так возникла еще одна ключевая идея онлайн‑рекламы: стоимость за 1 клик. Когда вы видите рекламу, «Яндекс» ничего на этом не зарабатывает. Счетчик поворачивается, только если вы кликнете на рекламный линк.

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

 

Аукцион – специально для вас!

 

Остается еще один существенный вопрос: сколько, собственно, стоит один клик? Логично, что ключевая фраза ипотека должна стоить гораздо дороже, чем детский велосипед б/у. Но сколько именно и насколько дороже?

Современные поисковые системы назначают цены за клик через аукцион. Все рекламодатели заранее предлагают свою цену за клик по той или иной ключевой фразе, и в момент поискового запроса рекламные места уходят тем, кто предложил больше. Настоящая рыночная цена! Для полноты информации сообщим, что цена за клик, например в Google, обычно 1–2 доллара, но доходит и до 50 долларов и выше, особенно в финансовом секторе.

Рекламу нужно подстраивать под пользователя, поэтому аукционы проводятся в реальном времени, для каждого поискового запроса в отдельности. Учитываются не только ставки, но и качество объявления, качество продавца, интересы пользователя, исходя из предыдущих запросов и кликов, и сотни других факторов. Существенно влияет местонахождение пользователя. Например, если вы в «Яндексе» в настройках измените город с Москвы на Нью‑Йорк, то рекламы московских компаний вы не увидите.

Каждый раз, когда вы вводите запрос типа пластиковые окна, поисковая система проводит по нему аукцион и представляет вам победителей! Это делают все поисковые системы. И поскольку один только Google обрабатывает примерно 40 тысяч запросов в секунду, то миллион аукционов в минуту – далеко не преувеличение.

Естественно, процесс полностью автоматизирован. Ставки делаются онлайн, победители и цены вычисляются автоматически по заранее заданной формуле. Какая формула сработает лучше всего?

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

Этими вопросами занимается очень интересная область современной математики под названием «Дизайн механизмов». В 2007 году ее основатели Леонид Гурвич, Эрик Маскин и Роджер Майерсон получили Нобелевскую премию по экономике. «Механизм» в данном случае – не машина, а механизм управления. Теория дизайна механизмов изучает, как создать оптимальные правила игры в условиях конкуренции: аукционы, голосование, распределение ресурсов. Онлайн‑реклама – всего лишь одно из многочисленных приложений.

 

Аукцион второй цены

 

При слове «аукцион» мы обычно представляем комнату, полную хорошо одетых людей, и человека с молотком на трибуне. Участники поднимают ставки. Раз, два, три – продано! Это открытый аукцион, все слышат ставки друг друга.

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

Представьте себе наиболее простую ситуацию, так называемый аукцион первой цены. Конверты вскрыты, и товар уходит по самой высокой ставке тому, кто ее предложил. Допустим, Анна и Борис участвуют в таком аукционе. Анна готова заплатить за товар 500, а Борис 300. Оба честно написали ставки 500 и 300. Товар ушел к Анне за 500. Все справедливо, но все ли довольны? На самом деле нет. Если бы Анна написала 400 или даже 301, то получила бы товар гораздо дешевле! Получается, что правдивую ставку делать невыгодно. Самое лучшее для Анны – это разузнать или угадать ставку Бориса и поставить чуть‑чуть больше.

Теперь представим, что правила изменились. Товар получает тот, кто сделал самую большую ставку, но по цене второй по величине ставки. Это называется аукционом второй цены. Анна и Борис честно пишут 500 и 300. Анна получает товар за 300.

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

Чудо аукциона второй цены заключается в том, что теперь делать правдивые ставки становится выгодно и безопасно. Анна может спокойно писать 500 и не волноваться, потому что больше 300 с нее не возьмут. А 300 и Борис готов заплатить, поэтому меньше 300 никак не получится.

Создать правила, при которых выгодно делать правдивые ставки, – один из основных принципов теории дизайна механизмов, он называется совместимость по стимулам. Аукцион второй цены – классический пример этого принципа. Математический анализ аукциона второй цены и доказательство совместимости по стимулам впервые предложил американский экономист Уильям Викри. Его статья, которая заложила основы теории аукционов, вышла в 1961 году {30}. В 1996‑м за эти исследования Викри получил Нобелевскую премию по экономике.

Именно аукционами второй цены, в разных вариантах, пользуются все поисковые системы. По словам Сергея Измалкова, это была «четвертая революция» в онлайн‑рекламе[23]. Ниже на рис. 8.1 перечислены все четыре ключевые идеи, приведшие к современной онлайн‑рекламе, какой мы ее видим каждый день.

 

Рис. 8.1. Четыре ключевые идеи современной рекламы в поисковых системах

 

 

Результат Викри

 

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

Вернемся к примеру, в котором Анна, Борис и еще несколько человек участвуют в аукционе второй цены. Каждый пишет свою ставку и кладет в конверт. Допустим, для Анны ценность товара 500, и ставок других участников она не знает.

Что произойдет, если Анна поставит 600? На рис. 8.2 мы представили три возможных сценария. Ставки участников обозначены жирными точками. В рамке вторая по величине ставка, это окончательная стоимость товара в аукционе второй цены. Если все остальные участники поставили меньше 500, как на рис. 8.2 вверху, то ничего не изменилось, Анна по‑прежнему получает товар за вторую цену (в данном примере 300). Повышать ставку смысла не было. Если кто‑то поставил больше 600, как на рис. 8.2 в середине, Анна не получает товар в любом случае. Победитель платит больше, но для самой Анны ничего не меняется. Опять же повышать ставку смысла не было (разве что из вредности, но модель этого не учитывает). Теперь представьте, что кто‑то поставил 550, как на рис. 8.2 внизу. Тогда Анна получает товар за 550, а это для нее слишком дорого. В контексте онлайн‑рекламы она может даже потерять на рекламе, вместо того чтобы заработать. Вывод: ставить выше 500 невыгодно.

.

Рис. 8.2. Три сценария, в которых Анна вместо правдивой ставки (500) делает более высокую ставку (600)

 

Но, может, выгодно сделать более низкую ставку? Оказывается, нет! Допустим, Анна решила попробовать поставить поменьше, скажем 400. На рис. 8.3 изображены те же три сценария. Если все остальные участники поставили меньше 400, как на рис. 8.3 вверху, то ничего не изменилось, Анна по‑прежнему получает товар за вторую цену (в данном случае снова 300). Если кто‑то поставил больше 500, как на рис. 8.3 в середине, то Анна не получит товар в любом случае. Но если кто‑то поставил 450, как на рис. 8.3 внизу, то Анна товар опять же не получает, хотя цена ее устраивала и она была готова платить больше, чем победитель. Возможность хорошей онлайн‑рекламы упущена. Ставить ниже 500 тоже невыгодно!

.

Рис. 8.3. Три сценария, в которых Анна вместо правдивой ставки (500) делает более низкую ставку (400)

 

Получается, что при аукционе второй цены ни одному из участников нет никакого смысла делать ставку, которая отличается от их честной оценки товара[24].

Это очень простой и глубокий математический результат, в котором сходятся сразу две фундаментальные концепции. Одну из них мы уже обсудили, это совместимость по стимулам, при которой честные ставки самые выгодные. Вторая – это так называемое равновесие по Нэшу. Речь идет о том самом Джоне Нэше из фильма «Игры разума».

Равновесие по Нэшу представляет собой ситуацию, когда ни одному из участников не выгодно в одиночку отклоняться от выбранной стратегии. Данная концепция лежит в основе теории игр, за разработку которой Джон Нэш получил Нобелевскую премию по экономике 1994 года. «Игрой» можно назвать любую ситуацию, когда исход зависит от действий всех участников и у каждого из них свои интересы. Очевидно, что аукцион – это тоже игра. Участники выбирают ставки с целью получить товар по самой выгодной цене[25].