Очевидно, що факт розвитку соціальних мереж нівелює відстань між агентами, а також збільшує ймовірність випадкового виникнення зв'язку між двома агентами - таким чином, заразити агентів інформацією все простіше і простіше. А значить, актуальним стає питання здатності передбачити, як саме пошириться інфекція.
І хоча спочатку потреба передбачення поширення інфекцій в мережах виникла в біології, дана проблема присутня в тому числі і в економіці. Адже якщо, скажімо, компанія хоче поширити якусь новинку через соціальну мережу (даний спосіб дифузії інформації є одним з найпопулярніших з моменту початку активного розвитку соціальних мереж), то їй потрібно розуміти, як буде йти інфекція по мережі з часом, щоб правильно вибрати амбасадорів для мінімальних витрат на поширення інформації про товар. Таким чином, мережеве передбачувальне моделювання виявляється затребуваним і стосовно мереж економічних агентів.
Далі я покажу практичне застосування моделей поширення інфекції на прикладі мережі 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
