Мрежи vs. равенки¶

Една работа што малку можеби недостасува кај SIR моделите е што зимаат во предвид дека сите можни интеракции помеѓу индувидуи се можни. Ова малку не соодвестува на вистинскиот свет. Не се среќаваме на редовна база со сите луѓе во иста зграда, улица ниту пак град бидејќи генерално вака не функционираат социјални средини.

Меѓутоа ова некогаш е точно, некогаш има “комплетно мешање” во одредени социјални кругови. Градинки и старечки домови се можеби вакви сценарија. Во градинка или дневен престој каде децата заедно си играат во двор корелира со веројатнста дека сите они се поврзани и доколку едно дете се зарази и останатите деца ќе се заразат. Слично сценаријо е и кај старечки домови. Старите лица згрижени претежно појадуваат или се социјализираат во “заеднички простори” (common spaces) и контактот на едно лице со сите е доста веројатен. Ова е една од причините зошто заразни боелсти побрзо се шират и се ширеле кај вакви мрежи.

Овој феномен одредени популации го користат доста конструктивно. Се оддржуват така наречени “сипанични забави” [*] каде се носат сите деца во едно сосдество со цел додека играат да се заразат - и потоа секако да бидат поимуни на самата инфекција, бидејќи малите сипаници се помалку отпорни на посилен имунитет.

Но, во нашите случаеви претпоставката на комплетно мешање мора да се отфрли. Бидејќи во претходните поглавја се запознавме со колку малку треба за инфективноста да преоѓа од обична настинка до масивна епидемија потребно е класичните SIR модели да го прилагодие да ги отсликува социјалните реалности во кои има значително помалку врски помеѓу поединци што може да ги очекуваме.

Вовед во мрежи¶

Еден начин за да се реши маната (претпоставката) на SIR моделите, воедно и прашањето на помалку конекции е користејќи мрежи.

Мрежа е едноставно колекција на темиња поврзани со рабови. Географска карта е добар пример за мрежа: темињата се градовите, додека рабовите (кои ги поврзуваат крстосниците на градовите заедно) се сегменти на патишта. Ова е причината што понекогаш се повикуваме на патната карта: тоа е колекција на (парчиња) пат што се среќаваат на различни точки.

Друг добар пример за мрежа - и поблиску до нашата сегашна апликација - е социјална мрежа. Во социјалната мрежа јазлите се луѓе, а рабовите се „социјални врски“ или „социјални контакти“ меѓу нив. Додека ние обично мислиме дека социјалните мрежи се online, како Facebook или Twitter, идејата функционира и во реалниот свет: кога ќе се сретнете со вашето семејство, одите на пазар, одите на работа или ќе се занесете со која било од активностите од секојдневниот живот што ќе ги додадете рабови на вашата социјална мрежа помеѓу себе и луѓето што ги среќавате. Типично, бројот на луѓе со кои ќе имате социјален контакт ќе биде значително помал од целата популација. Социјалната мрежа ги евидентира луѓето со кои имате контакт, па така и во нашата апликација евидентираат луѓе од кои може да заразите или да бидете заразени.

Направете ја истата работа за сите во населението и имате социјална мрежа за таа популација. Темињата се поединци; рабовите се потенцијални социјални контакти што носат инфекција. Ова потоа го користиме за да симулираме напредок на епидемијата преку една ваква мрежа.

Комплетни мрежи¶

Да претпоставиме дека, на нашите патувања, навистина сме стапиле во контакт со сите во населението, така што на овој начин нашата социјална мрежа има рабови што не поврзуваат со сите други. И да претпоставиме дека сите други го прават истото, така што сите беа поврзани со секого. Ова е сепак социјална мрежа - многу густа за да бидете сигурни, можеби како она што се случува во дискотетки (сите се поздравуваат). Исто така, се совпаѓа со претпоставките што ги дадовме претходно за целосно мешање. Значи, ако извршевме симулација на ширење на болеста преку оваа мрежа, веројатно би очекувале да ги видиме истите резултати како и порано.

Во претходните симулации ја „туркавме“ почетната популација на јазли преку равенките за моделите. За мрежи можеме да направиме нешто малку поразлично: Секој јазол претставува индивидуа, па затоа имаме колектив од луѓе чија еволуција можеме да ја следиме преку SIR болеста (наместо едноставно да ги броиме). Тоа ќе биде корисно подоцна. Но, јасно е дека има уште пописи за да се следат сите. Потешко е, од програмска перспектива, да се моделира болеста на мрежа - но со тоа ќе добиеме голема флексибилност, како што ќе видиме подоцна.

Првобитно треба да се наместиме симулации со цел подобро да ги моделираме врските меѓу луѓето. За среќа постојат готови библиотеки[‘][‘’] кој ја олеснуваат работата со вакви мрежи.

import networkx
import epydemic

Бидејќи сме заинтересирани за напредокот на епидемијата, ќе создадеме SIR процес и потоа ќе додадеме мониторинг за да ги добиеме истите временски серии што ги добивме за континуиран случај.

class MonitoredSIR(epydemic.SIR, epydemic.Monitor):
 
    def __init__(self):
        super(MonitoredSIR, self).__init__()
        
    def build(self, params):
        super(MonitoredSIR, self).build(params)

        self.trackNodesInCompartment(epydemic.SIR.SUSCEPTIBLE)
        self.trackNodesInCompartment(epydemic.SIR.REMOVED)

Сега можеме да ги напишеме (повеќе надоградување на готовите) функции со цел да спроведеме симулација врз база на готови параметри. Оваа библиотека малку поразлично ги запишува параметрите во однос на првите симулации што ги пуштив:

pInfected: инфицирани од започнување на епидемијата
pInfect: во нашите равенки \(\beta\) - очекуваниот број на луѓе на кои заразена личност ја пренесува болеста
pRemove: во нашите равенки \(\gamma\) - бројот на заразени личности што заздравуваат на ден

За да го комплетираме влезот во функцијата, додаваме како влез мрежа користејќи ја библиотеката за мрежи (во ова сценарио сакаме комплетен граф/мрежа со цел да видиме колку добро/блиску двете техники моделираат заразна болест). Функцијата користи доста од архитектурата на библиотеката epydemic, која ни го извршува кодот и ги екстрахира резултатите.

def network_sir(T, g, pInfected, pInfect, pRemove):
    # креирај готов симулатор
    m = MonitoredSIR()
    m.setMaximumTime(T)
    e = epydemic.SynchronousDynamics(m, g)

    # намести ги параметрите за симулација
    param = dict()
    param[epydemic.SIR.P_INFECTED] = pInfected
    param[epydemic.SIR.P_INFECT] = pInfect
    param[epydemic.SIR.P_REMOVE] = pRemove
    param[epydemic.Monitor.DELTA] = T / 50 # 50 samples
    
    # пушти симулација
    rc = e.set(param).run()
    
    # извлеги ги бројките / резултатите
    results = e.experimentalResults()[MonitoredSIR.TIMESERIES]
    ts = results[MonitoredSIR.OBSERVATIONS]
    sss = results[epydemic.SIR.SUSCEPTIBLE]
    iss = results[epydemic.SIR.INFECTED]
    rss = results[epydemic.SIR.REMOVED]

    # врати ги 
    return(ts, sss, iss, rss)

За да ја тестираме нашата хипотеза, потребна ни е целосна „социјална мрежа“ (што во реален свет на постои) за да тестираме. Таквите мрежи честопати се нарекуваат комплетни графови, со секој јазол поврзан со работ на едни со други.

g = networkx.complete_graph(N)

Конечно, можеме да ги извршиме равенките и мрежната симулација и да ги нацртаме заедно. Доколку генерираат исти резултати, би очекувале двете групи на податоци да се поклопуваат едни со други.

import plotly.graph_objects as go
import plotly.tools as tls
from plotly.offline import plot, iplot, init_notebook_mode
from plotly.validators.scatter.marker import SymbolValidator
from IPython.core.display import display, HTML

# Иницијализација на Plotly 
init_notebook_mode(connected = True)
config={'showLink': False, 'displayModeBar': False}

raw_symbols = SymbolValidator().values
namestems = []
namevariants = []
symbols = []
for i in range(0,len(raw_symbols),3):
    name = raw_symbols[i+2]
    symbols.append(raw_symbols[i])
    namestems.append(name.replace("-open", "").replace("-dot", ""))
    namevariants.append(name[len(namestems[-1]):])


figb = go.Figure() 

# Дефинирање на параметри 
N = 2000            # Популација (бр. луѓе)
T = 5000            # Денови (бр. денови)
pInfected = 0.01    #  % инфицирани од започнување на епидемијата
pRemove = 0.001     #  % бројот на заразени личности што заздравуваат на ден
pInfect = 0.000005  # очекуваниот број на луѓе на кои заразена личност ја пренесува болеста / популација


(ts, sss, iss, rss) = epidemic_sir(T, N, pInfected, pInfect, pRemove)


# Додавање на вредности од SIR модел
figb.add_trace(go.Scatter(x=ts, 
                          y=sss, 
                          mode='lines',
                          visible=True,
                          showlegend = True, 
                          hovertemplate = '<i> %{y:.0f} </i> луѓе', 
                          name='подлежни (равенки); S(t)',
                          marker_color='blue'))

figb.add_trace(go.Scatter(x=ts, 
                          y=iss, 
                          mode='lines',
                          visible=True,
                          showlegend = True, 
                          hovertemplate = '<i> %{y:.0f} </i> луѓе', 
                          name='заразени (равенки); I(t)',
                          marker_color='red'))
               
figb.add_trace(go.Scatter(x=ts, 
                          y=rss, 
                          mode='lines',
                          visible=True,
                          showlegend = True, 
                          hovertemplate = '<i> %{y:.0f} </i> луѓе', 
                          name='оздравени (равенки); R(t)',
                          marker_color='green'))


# Истата симулација над мрежи 
(sim_ts, sim_sss, sim_iss, sim_rss) = network_sir(T, g, pInfected, pInfect, pRemove)

# Додавање на маркери за мрежи 
figb.add_trace(go.Scatter(x=sim_ts, 
                          y=sim_sss, 
                          mode='markers',
                          visible=True,
                          showlegend = True, 
                          hovertemplate = '<i> %{y:.0f} </i> луѓе', 
                          name='подлежни (симулирана мрежа)',
                          marker_symbol=symbols[5],
                          marker_color='blue'))
               
figb.add_trace(go.Scatter(x=sim_ts, 
                          y=sim_iss, 
                          mode='markers',
                          visible=True,
                          showlegend = True, 
                          hovertemplate = '<i> %{y:.0f} </i> луѓе', 
                          marker_symbol=symbols[5],
                          name='заразени (симулирана мрежа)',
                          marker_color='red'))
               
figb.add_trace(go.Scatter(x=sim_ts, 
                          y=sim_rss, 
                          mode='markers',
                          visible=True,
                          showlegend = True, 
                          hovertemplate = '<i> %{y:.0f} </i> луѓе', 
                          marker_symbol=symbols[5],
                          name='оздравени (симулирана мрежа)',
                          marker_color='green'))

# Изглед на график
figb.update_layout(title = 'Равенки vs. Мрежа',
                   title_x = 0.38, 
                  legend=dict(orientation = 'v',
                              bordercolor="Gray",
                              borderwidth=1),
                  hovermode='x unified',
                  xaxis_title='<i>t</i>',
                  xaxis=dict(range=[0, 5000], 
                             mirror=True,
                             ticks='outside',
                             showline=True,
                             linecolor='#000',
                             tickvals = [0, 1000, 2000, 3000, 4000, 5000],
                             tickfont = dict(size=12)),
                  yaxis_title='Број на луѓе (<i>N</i>)',
                  yaxis=dict(range=[0,2000], 
                             mirror=True,
                             ticks='outside', 
                             showline=True, 
                             linecolor='#000',
                             tickfont = dict(size=12)),
                  plot_bgcolor='#fff', 
                  width = 760, 
                  height = 480,
                  font = dict(size = 11),
                  margin=go.layout.Margin(l=50,
                                         r=50,
                                         b=60,
                                        t=35))
# Приказ на фигура
# jupyter-book rendering --=-- jupyter-lab
plot(figb, filename = 'new-fig.html', config = config)
display(HTML('new-fig.html'))
# local jupyter notebook --== binder session
# iplot(figb,config=config)

Горната симулација ја потврдува нашата хипотеза: маркерите на мрежната симулацијата лежат над горниот дел на цврстите линии на SIR равенките. Не се поклопуваат баш до крај, од причини до кои ќе дојдеме подоцна.

До сега, го дефиниравме SIR како процес и истражувавме што се случи во сценарио за целосно мешање. Потоа ги репродуциравме овие резултати во различна средина (комплетен граф), со ист процес што се одвива преку мрежа, исто така, со целосно мешање. Но, јасно комплетното мешање не е добар модел на социјална мрежа: не ги исполнувате сите цело време и затоа не се изложувате на сите можни заразени лица.

Вистинските социјални мрежи се многу различни: повеќе „тромави“, порамномерни, некои луѓе со повеќе контакти од другите. Секој го доживува ова, и некој би помислил дека разликите (во структурата на социјалниот контакт) ќе направат разлика во епидемијата (во начинот на ширење). Ова е навистина така, и ќе се обидеме да го покажеме во друг пример.

Симулацијата што ја извршивме погоре има два дела:

SIR процес
комплетна мрежа

Ние се разбира, можеме (и треба) да ја смениме мрежата и слично како сега да истражиме како се однесува болеста за различни видови мрежи (Barabasi-Albert network (BA), Erdos-Renyi network (ER)).

Некомплетни графови¶

Ако комплетниот граф соодветвува за целосно мешање, како претставуваме „нецелосно“ мешање? Со некомплетен граф, очигледно.

Се разбира, иако може да има само еден целосен граф со даден број на јазли, откако ќе започнеме да зборуваме за нецелосни графови, имаме огромен број опции. Може да имаме мрежа без рабови. (Како би се проширила епидемија преку оваа мрежа?) Или би можеле да имаме мрежа што има многу нееднаква дистрибуција на рабовите. Можеби би можеле дури и да извлечеме „вистинска“ социјална мрежа од податоците на Facebook или Twitter.

Структурата на мрежата математички се нарекува нејзина топологија. Може да го сфаќаме ова како „начинот на кој е поврзано“. Значи ни преостанува истражување на тоа како се шири SIR процесот преку мрежи со вакви различни топологии.

Топологии на мрежи¶

Бидејќи имаме низа различни топологии, ќе ни треба некаков начин да ги опишеме нивните својства за да можеме да ги разликуваме. Развиени се огромен број на такви графички мерки и повеќето ќе ги спомнеме во текот на примерите. Засега, ќе започнеме со најважниот број, степенот на јазол, што е едноставно бројот на рабовите што го пресекуваат секој јазол. Секој јазол има свој степен. Во вашата социјална мрежа, степенот на јазолот што ве претставува е едноставно бројот на луѓе со кои сте поврзани. Степенот на јазол обично се означува \(k\). Во мрежите ќе разгледуваме за сега степенот на јазол е фиксиран кога мрежата е создаден. Но во литератури претежно се користат адаптивни мрежи, каде самиот степен станува процес што се менува со времето.

За дадена мрежа можеме да ги наброиме степените на секој јазол, но тоа очигледно нема да биде многу корисно за голема мрежа: не би можеле да извлечете корисни информации од големиот список на броеви. Но, можеме да извлечеме статистика од такви списоци. Најважен е просечниот степен на јазол (mean degree), означен како \(\langle k \rangle\). Додека степенот на секој јазол треба да биде цел број (не можете да имате половина пријател), просечниот степен на населението во целина обично ќе биде реален број. Оваа бројка често ја викаат “k mean”.

За комплетен граф, секој јазол има точно ист степен, што е еден помалку од бројот на јазли во мрежата, бидејќи има раб помеѓу секој јазол и секој друг (освен самиот себе). Ова значи дека \(k\) е секогаш \((N − 1)\) за секој јазол, па затоа е и \(\langle k \rangle\).

Генерално, моделите на ваквите мрежи се посложени. Степените на јазли во мрежата формираат дистрибуција на степени (degree distribution), што можеме да го прикажеме како хистограм за да го прикажеме бројот на јазли со секој степен (ова го правиме подолу). Ако користиме \(N\) за да го претставиме бројот на јазли во мрежата, ќе користиме \(N_k\) за да претставиме број на јазли со степен \(k\). Тогаш можеме многу лесно да го пресметаме \(\langle k \rangle\) од оваа дистрибуција, со сумирање на броевите на јазлите со секој степен и потоа делење со бројот на јазли.

\[\begin{equation*} \langle k \rangle = \frac{\sum_k N_k}{N} \end{equation*}\]

Ако оваа употреба на зборот дистрибуција звучи како да е поврзана со теоријата на веројатност - тоа е. Хистограмот на степенот ги покажува релативните броеви на јазли со секој различен степен и така ја дефинира веројатноста за случаен избор на јазол со степен \(k\). \(\langle k \rangle\) е тогаш очекуваната вредност на степенот.

Постојат многу други метрики што би можеле да ги разгледаме, но дистрибуцијата на степенот е најважна и добро проучена. Сепак, тоа не е целата приказна, бидејќи ќе има многу различни мрежи со иста дистрибуција на степен и просечен степен, во зависност од тоа точно како рабовите што го пресекуваат секој јазол се поврзуваат со други јазли. Значи, додека едната страна од мрежната топологија е зафатена со статистички податоци, има друга страна што се однесува на деталите за кои јазли се соседни (adjacent) едни со други, имајќи раб помеѓу нив: важно е кои се вашите пријатели, не само колку имате. Ние понекогаш го нарекуваме множеството јазли во непосредна близина на јазолот како множество од соседи (neighbours).

Имунитет на стадо

Мрежи vs. равенки¶

Вовед во мрежи¶

Комплетни мрежи¶

Некомплетни графови¶

Топологии на мрежи¶