28.03.2017 /
№ 225 /
с. 6–7 /
Михаил Гельфанд / Big Data /
No Comments
Михаил Гельфанд
Одна из ключевых проблем при изучении эпидемий — учет передвижений людей. Классические диффузионные модели хорошо описывают эпидемии прошлого, но ломаются с появлением быстрых и массовых путешествий на большие расстояния: автомобилем, поездом и тем более самолетом.
Красивый цикл работ в этой области был сделан в 2000-х годах Ларсом Хуфнагелем (Lars Hufnagel) из Института динамики и самоорганизации (Max-Planck-Institut für Strömungsforschung, Гёттинген) и Дирком Брокманном (Dirk Brockmann), также работавшим в Гёттингене, а затем переехавшим в США, в Северо-Западный университет (Northwestern University, Иллинойс). Для того чтобы оценить интенсивность путешествий людей, они использовали данные о перемещениях банкнот. Данные для этого были взяты с неофициального сайта по отслеживанию американских купюр «Где Джордж?» [1] (рис. 1).
Рис. 1. Джордж следит за тобой
Где Джордж?
Сайт сделал американец Хэнк Эскин, «потому что это прикольно и никто раньше такого не делал» [1, FAQs]. Идея очень проста: кто угодно может достать купюры разного достоинства из своего бумажника и занести в простую форму их номера и почтовый индекс места, где он находится.
Еще можно поставить на эти банкноты печать с адресом сайта. Легальность такого действия неочевидна — американский закон запрещает портить банкноты, но «портить» определяется как делать непригодными для использования; авторы сайта очень аккуратно воздерживаются от каких-либо рекомендаций, вместо этого приводя ссылку на соответствующую страницу американского Казначейства (мол, sapienti sat). Они не продают штампов (в первые годы — продавали, однако это вошло в противоречие с законом о запрете рекламы на деньгах), но намекают, что их легко заказать в Интернете или в писчебумажном магазине по соседству.
Сайт был открыт 23 декабря 1998 года, и за прошедшие почти двадцать лет на нем было зарегистрировано 270 млн банкнот на сумму 1,45 млрд долл. (это 0,13% от общей суммы долларов в обращении), из них 31 млн больше одного раза. На сайте зарегистрировалось более 8 млн пользователей, три четверти из которых занесли хотя бы по одной купюре; в среднем зарегистрированный пользователь занес номера 37 купюр; примерно четверть купюр занесли незарегистрированные пользователи.
Эта статистика показывает, что идея понравилась пользователям Интернета. Видимо, в значительной степени — как всегда — сказался эффект соревнования: на сайте ведется аккуратный подсчет активности всех «джорджеров», как они себя называют. Лидер (Девушка Игуана из города Пиджен-Фордж, штат Теннесси, — ник был взят в честь домашней игуаны, к сожалению уже покойной) за пятнадцать лет, с марта 2002 года, занесла номера более миллиона банкнот, из которых примерно 300 тыс. (26%) побывали на сайте не один раз.
В среднем получается чуть более 20 банкнот в день; можно предположить, что Девушка Игуана, как и другие лидеры, работает кассиром или еще как-то связана с оборотом наличности, поскольку для обычного человека такой поток представляется слишком большим. Кроме того, на сайте функционирует форум, на котором есть разделы и про распространение купюр, и про их куплю-продажу (никому не нужна банкнота с номером 88844448 или 90003000? А 19681967? А начинающиеся с 666? Или с четырех нулей? Тогда вам туда…).
Доллары и вирусы
Описав эпидемию атипичной пневмонии 2003 года с использованием карты маршрутов международных авиалиний [2], авторы осознали, что, хотя их модель хорошо работает в большом масштабе, но для описания распространения эпидемии на уровне одной страны, скажем, США, надо учитывать и другие виды транспорта, а доступных данных для этого нет.
И тогда они обратили внимание на сайт, на котором отслеживается перемещение бумажных денег. Ясно, что это было практически то что надо: передача купюры происходит при личном контакте, как и передача вируса. Авторы написали Хэнку Эскину и, так не дождавшись ответа, соорудили простой скрипт, который начал выкачивать данные с сайта [3]. Эскин заметил необычный всплеск активности и закрыл доступ, на всякий случай, для всего Гёттингена, однако данные о миллионе перемещений уже были скачаны, и этого оказалось достаточно для статистического анализа [4].
Как ожидалось, расстояния, на которые банкноты передвигаются за небольшое время, были распределены по степенному закону (рис. 2 слева). Такое распределение характерно, в частности, для популярной модели «полета Леви» со степенными интервалами между изменениями направления. Однако при более внимательном рассмотрении оказалось, что динамика распространения банкнот от исходной точки противоречит и этой модели, и простой двумерной диффузии (рис. 2 справа): они разбегаются слишком медленно.
Рис. 2. Путешествия Джорджа и его друзей [2]. Слева: Распределение расстояний, на которые банкноты перемещаются за 1–4 дня. На вкладке — то же распределение в зависимости от исходной точки. Справа: вероятность выйти за круг с радиусом 20 км за данное время. Типы точек: □— все города, ∆ — большие города, ◊ — средние города, ○ — малые города. Пунктир: синий — наблюдаемая экспонента t–η (с показателем η = 0,6), черный — экспонента, ожидаемая при двумерной диффузии (η = 1,0), красный — скорость распространения в модели полета Леви (η = 3,3)
Авторы предположили, что дело в том, что перемещения совершаются не непрерывно друг за другом и необходимо учитывать время, которое купюра проводит в бумажнике очередного владельца; оно также распределено по степенному закону. Модель, учитывающая оба параметра — длину перемещения и время между перемещениями, оказалась очень точной.
А теперь, раз мы знаем статистику контактов жителей США, мы можем подставить ее в стандартные эпидемиологические модели, учитывающие также инкубационный период болезни, среднюю плотность контактов, вероятность заражения при контакте, и получить, например, предсказание того, как будет развиваться эпидемия свиного гриппа 2009 года (по числу заболевших в разных географических точках) — не задним числом, а в реальном времени [5].
Карта путешествий
Рис. 3. Города и доллары [6]. Слева: горизонтальная ось — приток банкнот, вертикальная ось — отток банкнот. Справа: горизонтальная ось — население города, вертикальная ось — приток банкнот. Двойные логарифмические координаты; цвет точек — количество наблюдений. Пунктиром показана линейная зависимость
Но данные о перемещениях банкнот можно использовать и для того, чтобы понять, как вообще устроены взаимодействия между популяциями. Вот, например, простой факт: чем больше город, тем мощнее поток проходящих через него денег, причем приток равен оттоку (рис. 3) [6]. Можно посчитать суммарные потоки банкнот между штатами и нарисовать кластерное дерево, на котором ближе всего будут штаты, интенсивно обменивающиеся долларами, потом чуть дальше и так далее (рис. 4).
Рис. 4. Штаты и доллары [6]. Кластеризация штатов по величине суммарных потоков банкнот между ними. Слева: кластерное дерево; справа: то же дерево, спроецированное на карту СШАОднако кто сказал, что естественные границы общения совпадают с границами штатов? Правильнее было бы посмотреть, как страна сама разделяется на области, внутри которых люди взаимодействуют часто, а между которыми — редко.
Рассмотрим граф, в котором вершинами будут города, а весами на ребрах — частоты перемещений банкнот между этими городами. Разобьем этот граф на модули, т. е. такие плотные подграфы, в которых суммарный вес ребер велик, а между которыми, как правило, проходят ребра малого веса.
Ясно, что это зависит от конкретных определений плотности подграфа; проблема в том, что для любых содержательных определений задача вычислительно очень сложна и не может быть решена точно — мы не можем построить оптимальное разбиение графа на компоненты за разумное время. Поэтому используют различные эвристические и вероятностные алгоритмы, которые не гарантируют точного решения, но строят хорошее приближение к нему. Один из вероятностных алгоритмов использовал всё тот же Дирк Брокманн в своей следующей работе [7].
Первая хорошая новость: полученные модули хорошо проецируются на географическую карту. Алгоритм ничего не знает о географии, а учитывает только потоки банкнот; вполне могло бы получиться, что города кластеризовались бы, например, по экономическим показателям. Вторая: хотя при каждом запуске вероятностного алгоритма получаются, вообще говоря, разные модули, они похожи. Естественно считать, что те границы, которые устойчиво воспроизводятся при (почти) каждом разбиении, и являются правильными (рис. 5 слева).
Рис. 5. Разбиение США на компактные модули по потокам банкнот [7]. Сверху: границы модулей показаны синим, интенсивность цвета соответствует частоте, с которой граница воспроизводится при различных запусках алгоритма. Круговые диаграммы показывают, что 44% границ штатов являются также и границами модулей (слева), но 64% границ модулей не совпадают с границами штатов (справа). Внизу: примеры несовпадения границ штатов и модулей. Слева: разбиение штата Миссури на области Канзас-Сити (запад) и Сент-Луиса (восток); справа: разбиение по Аппалачам, разделяющее Пенсильванию на области Питтсбурга (к западу от гор) и Филадельфии (к востоку от гор)Сопоставление исходного графа и полученных модулей показывает, что у каждого модуля есть «центр» — вершина, через которую и идут основные потоки банкнот. Авторы предложили оригинальную формализацию этого соображения. Грубо говоря, ребро является важным, если его удаление разрушает кратчайшие пути ко многим вершинам; при этом расстоянием между парой вершин считается величина, обратная потоку банкнот между ними.
Теперь, если оставить только важные ребра, мы увидим, что структура графа — это сеть, состоящая из «звезд» с центрами, как правило, в больших городах; в каждом модуле есть один или несколько таких центров.
Рис. 6. Сеть потока банкнот в США [7]. Синим цветом показаны важные ребра, красным — границы модулей, желтые квадраты — большие города
Sic transit
В истории науки бывает так, что какой-то красивый прием оказывается полезным очень недолго, потому что его вытесняют новые методы. Так и с моделированием передвижений людей при помощи данных о перемещении банкнот — сейчас для этой цели проще всего использовать информацию от сотовых телефонов [8]. Это хорошо работает даже в бедных странах, где риск эпидемий особенно велик, и такой подход был успешно применен, например, для анализа эпидемии холеры на Гаити [9] и распространения малярии [10] и краснухи [11] в странах Африки.
6. Brockmann D., Theis F. Money circulation, trackable items, and the emergence of universal human mobility patterns // IEEE Pervasive Computing. 2008. 7: 26–35.
![Рис. 4. Штаты и доллары [6]. Кластеризация штатов по величине суммарных потоков банкнот между ними. Слева: кластерное дерево; справа: то же дерево, спроецированное на карту США](http://trv-science.ru/uploads/225-0027.jpg)
![Рис. 5. Разбиение США на компактные модули по потокам банкнот [7]. Сверху: границы модулей показаны синим, интенсивность цвета соответствует частоте, с которой граница воспроизводится при различных запусках алгоритма. Круговые диаграммы показывают, что 44% границ штатов являются также и границами модулей (слева), но 64% границ модулей не совпадают с границами штатов (справа). Внизу: примеры несовпадения границ штатов и модулей. Слева: разбиение штата Миссури на области Канзас-Сити (запад) и Сент-Луиса (восток); справа: разбиение по Аппалачам, разделяющее Пенсильванию на области Питтсбурга (к западу от гор) и Филадельфии (к востоку от гор)](http://trv-science.ru/uploads/225-0024.jpg)
![Рис. 6. Сеть потока банкнот в США [7]. Синим цветом показаны важные ребра, красным — границы модулей, желтые квадраты — большие города](http://trv-science.ru/uploads/225-0028.jpg)