Очевидно, что факт развития социальных сетей нивелирует расстояние между агентами, а также увеличивает вероятность случайного возникновения связи между двумя агентами – таким образом, заразить агентов информацией все проще и проще. А значит, актуальным становится вопрос способности предсказать, как именно распространится инфекция.
И хотя изначально потребность предсказания распространения инфекций в сетях возникла в биологии, данная проблема присутствует в том числе и в экономике. Ведь если, скажем, компания хочет распространить какую-то новинку через социальную сеть (данный способ диффузии информации является одним из самых популярных с момента начала активного развития социальных сетей), то ей нужно понимать, как будет идти инфекция по сети со временем, чтобы правильно выбрать амбассадоров для минимальных затрат на распространение информации о товаре. Таким образом, сетевое предсказательное моделирование оказывается востребованным и применительно к сетям экономических агентов.
Далее я покажу практическое применение моделей распространение инфекции на примере сети Flickr. Для этого будут реализованы две самые популярные и применимые на практике модели – SI (suspectible – infected) и SIR (suspectible – infected – recovered) [1], [5].
Реализация модели SI в сети Flickr
Допустим, что мы производим какой-то товар, который хотим разрекламировать при помощи фотохостинга Flickr. Для этого мы «заражаем» какое-то количество пользователей, покупая право опубликовать через их профили фотографии нашего товара с соответствующим хэштегом. Передачей инфекцией от одного агента к другому будем называть передачу хэштега.
Учитывая то, что у нас есть «здоровые» участники сети (susceptible), а также изначально «инфицированные» нашим товаром (infected), то модель распространения нашего вируса по сети может быть описана моделью распространения эпидемии SI (с определенной вероятностью заражения, т.е. мерой того, насколько человек восприимчив к рекламе)[3], а также моделью SIR (когда человек «переболел» идеей приобрести наш товар и больше не восприимчив к рекламе)[4].
Рассмотрим случай модели SI. Для простоты будем предполагать, что мы первоначально можем заразить одного участника сети. Тогда, задачу менеджера можно свести к наблюдению за итеративным изменением сети (т.е. шаг за шагом с выбранным временным интервалом происходит предсказание состояния сети в следующий момент времени, основываясь на текущей информации). Таким образом, заразив пользователя в гигантской связной компоненте, можно шаг за шагом наблюдать, как будет идти распространение инфекции. И в силу особенности модели SI, любая вершина, которая на — ом шаге присоединится к гигантской связной компоненте, рано или поздно окажется инфицированной.
Построим для примера гигантскую компоненту графа сети Flickr спустя несколько месяцев после начала работы сети (Рис.1.).
Рис.1. Гигантская связная компонента сети Flickr
Очевидно, что итоговым показателем рекламной кампании должна стать доля «зараженных» агентов сети. Для случая модели SI это будет просто доля вершин гигантской связной компоненты во всем графе. Возьмем несколько срезов сети Flickr и посмотрим, как будет меняться доля зараженной популяции при использовании модели SI с течением времени (Рис.2.).
Рис.2. Итоговый размер эпидемии (доля зараженных) с ростом графа
Получаем закономерный результат: чем больше граф, тем больше его связная компонента, а значит и больше итоговая доля зараженных участников сети. Теперь рассмотрим более сложную модель распространения инфекции в сети, а именно модель SIR.
Реализация модели SIR в сети Flickr
Для того, чтобы представить распространение инфекции в сети Flickr по типу модели SIR, воспользуемся таким способом распространения информации как перколяцией [2].
Понятие перколяции пришло из физики, где оно означает протекание или не протекание электрического тока через смеси материалов. Применительно к теории распространения инфекции перколяцией называют передачу или не передачу инфекции по связи между двумя агентами.
Для того, чтобы объяснить суть перколяции в теории эпидемий, предположим, что некая вершина u из графа G только что стала инфицированной. У этой вершиной есть связь с вершиной v, а значит существует некая вероятность p, что вершина v окажется заражена в следующий момент времени. Узнать исход события мы можем, к примеру, бросив монетку, у который «орел» выпадает с вероятностью p. Но с точки зрения определения исхода, совершенно неважно, бросили мы монетку в начале эпидемии, или в тот момент, когда вершина u стала зараженной и возникла угроза заражения вершины v. Тогда, нам ничто не мешает в самом начале эпидемии провести процедуру подбрасывания монетки и определить, «пропустит» ли ребро между конкретными двумя вершинами инфекцию или нет. Назовем ребро активным, если оно по результатам подбрасывания монетки перешло в категорию пропускающих инфекцию, и пассивным в противном случае. Для случая одной изначально зараженной вершины становится возможным сформулировать следующую теорему.
Теорема 1. Вершина v станет зараженной в результате эпидемии тогда и только тогда, когда ее соединяет с изначально зараженной вершиной u путь из активных ребер.
К модели SIR эта теория имеет непосредственное отношение. Определим через T (probability of transmission) пороговое значение вероятности ребра стать активным (фиксируется единое число для проверки всех ребер в графе). Заразим некую первоначальную вершину в момент времени t = 1. В следующий момент времени посмотрим, какие из ребер, ведущих от данной вершины, активны, и передадим инфекцию по ним, а саму вершину переведем в класс recovered (выбывшие из популяции – это будет означать для нашего примера, что вершина подверглась воздействию рекламы, и на следующем шаге успела передать рекламную идею каким-то своим друзьям, после чего утратила интерес к распространении информации о товаре).
Проделывая описанную процедуру итеративно до полного исчерпания зараженных вершин, мы придем к тому, что итоговой долей зараженных участников сети будет множество вершин класса recovered по отношению к числу вершин во всем графе.
По умолчанию будем считать, что когда речь идет об одной единственной первоначально зараженной вершине, то она выбирается из числа вершин в гигантской связной компоненте; также отметим, что для каждой дальнейшей симуляции делалось 500 итераций и результат усреднялся по всем.
Посмотрим на распределение получаемых долей зараженных в результате эпидемии (в 500 симуляциях) при различных комбинациях числа изначально зараженных (inf) и T (probability of transmission). На Рис.3. представлены 9 комбинаций (T=0.25, 0.55 и 0.85; inf = 1, 50 и 100).
Рис.3. Зависимость итогового охвата эпидемии от порога T и изначального числа зараженных
Получаем, что увеличение числа изначально зараженных приводит к тому, что распределение становится все более похожим на нормальное (видимо работает закон больших чисел). А увеличение параметра T способствует тому, что «хвосты» становятся «легче»(потому что при малых T даже большое число изначально зараженных не гарантирует «хорошее» распространение инфекции).
Отдельно для случая, когда изначально заражается только 1 узел, посмотрим на то, как меняется корреляция «центральности» изначально зараженного узла и итоговой доли зараженных в зависимости от параметра T (Рис.4.).
Рис.4. Корреляция между итоговым охватом и «центральностью» исходного узла при разных T
Отметим, что, начиная с какого-то момента, устанавливается тренд с обратной зависимостью (для degree centrality, closeness centrality и betweenness centrality). Это объясняется тем, что когда T небольшой и инфекция плохо распространяется сама по себе, крайне важным становится то, какую вершину мы выберем для начала заражения сети (т.е. есть сильная положительная корреляция между «центральностью» и итоговой долей зараженных); а с увеличением значения параметра T инфекция распространяется все лучше, и важность «центральности» изначального узла становится все меньше (таким образом, корреляция уменьшается, т.е. вне зависимости от «центральности» изначально зараженного узла инфекция все равно хорошо распространится сама по себе).
Таким образом, мы можем моделировать распространение нашего товара, имея предсказанные графы и информацию о том, каков порог T (относительного всего этого и имеющегося бюджета становится возможным выстроить стратегию того, сколько агентов «заразить» в изначальный момент времени в зависимости от целевых показателей итоговой доли «зараженных»).
Основные выводы заключаются в том, что для случая использования модели распространения эпидемии SI можно утверждать, что любая вершина графа сети, попадающая в гигантскую связную компоненту, рано или поздно окажется заражена.
Итоговая доля зараженных агентов при использовании модели SIR всегда оказывается меньше, чем в случае модели SI. Однако, концепция SIR предоставляет больше возможностей для варьирования таких показателей, как изначальное число зараженных вершин, пороговое значение вероятности ребра стать активным и т.д., в зависимости от того, каковы целевые значения доли зараженных и каков бюджет компании на проведение рекламной акции. Таким образом, имея два указанных входных параметра и выявленные в работе взаимосвязи, задача менеджера сводится к оптимизационной.
Список литературы
1. Bailey, N. T. J. (1975), The Mathematical Theory of Infectious Diseases and its Applications, 2nd ed. (Charlin Grin & Company, London)
2. David Easley and Jon Kleinberg «Networks, Crowds, and Markets: Reasoning about a Highly Connected World», Cambridge University Press, 2010., p. 655
3. Diekmann, O., H. Heesterbeek, and T. Britton (2012), Mathematical Tools for Understanding Infectious Disease Dynamics (Princeton University Press, Princeton, USA)
4. Jan Medlock, Mathematical modeling of epidemics. University of Washington, 22&24 Vaf 2002
5. Romualdo Pastor-Satorras, Claudio Castellano, Piet Van Mieghem and Alessandro Vespignani « Epidemic processes in complex networks», April 22 2015
Автор: CrocodeInc
