Vi studerar problemet med att uppskatta ursprunget till ett epidemiskt utbrott: med tanke på ett kontaktnätverk och en ögonblicksbild av epidemin som sprids vid en viss tidpunkt, bestämma infektionskällan. Detta problem är viktigt i olika sammanhang av datorer eller sociala nätverk. Förutsatt att epidemispridningen följer den vanliga mottagliga-infekterade modellen, introducerar vi en inferensalgoritm baserad på dynamiska ekvationer för meddelandepassering och vi visar att det leder till betydande förbättringar av prestanda jämfört med befintliga metoder. Viktigt är att denna algoritm förblir effektiv i det fall ögonblicksbilden endast ser en del av nätverket.  Att förstå och kontrollera spridningen av epidemier på kontaktnät är en viktig uppgift för dagens vetenskap. Den har långtgående tillämpningar för att mildra resultaten av epidemier orsakade av infektionssjukdomar, datorvirus, rykten sprider sig i sociala medier och andra. I den här artikeln tar vi upp problemet med uppskattning av ursprunget till epidemiutbrottet (den så kallade patienten noll, eller infektionskällan - i vad som följer, dessa termer används växelvis): med tanke på ett kontaktnätverk och en ögonblicksbild av epidemin sprids vid en viss tidpunkt, bestämma infektionskällan. Information om ursprunget kan vara mycket användbar för att minska eller förhindra framtida utbrott. Medan dynamiken och förutsägelsen om epidemispridning i nätverk har lockat ett stort antal verk, för en översyn se [1] [2] [3], problemet med att uppskatta epidemins ursprung har matematiskt formulerats först nyligen [4], följt av en explosion av forskning om detta praktiskt taget viktiga problem [5] [6] [7] [7] [8] [9] [10] [11]. För att uppskatta ursprunget till att sprida ett väldefinierat problem måste vi ha viss kunskap om spridningsmekanismen. Vi kommer att anta samma ram som i befintliga verk, nämligen att epidemispridningen följer den allmänt använda modellen för mottagligt smittade återvunna (SIR) eller några av dess specialfall [12]. Infektionsutbredningens stokastiska natur gör att uppskattningen av epidemins ursprung i sig är svår: i själva verket kan olika ursprungliga förhållanden leda till samma konfiguration vid observationstidpunkten. Att hitta en estimator som maximerar sannolikheten för den observerade konfigurationen är i allmänhet beräkningsmässigt intractable, utom i mycket speciella fall som fallet där kontaktnätet är en linje eller ett vanligt träd [4, 6, 11]. De metoder som har studerats i de befintliga verken är främst baserade på olika typer av grafcentralitetsmått. Exempel är avståndets centralitet eller Jordaniens centrum för en graf [4] [5] [6] [7]. Problemet generaliserades för att uppskatta en uppsättning epidemiska ursprung med hjälp av spektralmetoder i [8, 9]. En annan metod använder mer detaljerad information om epidemin än bara en ögonblicksbild vid en given tidpunkt [10]. Observera dock att alla nuvarande metoder är begränsade, till exempel ingen av dem använder effektivt informationen om de noder till vilka epidemin inte spreds. I detta dokument introducerar vi en ny algoritm för uppskattning av ursprunget till en SIR-epidemi från kunskap om nätverket och ögonblicksbild av vissa noder vid en viss tidpunkt. Vår algoritm uppskattar sannolikheten för att den observerade ögonblicksbilden är ett resultat av en given patient noll på ett sätt som är avgörande skiljer sig från befintliga metoder. För varje möjligt ursprung epidemin, använder vi en snabb dynamisk meddelande-passing metod för att uppskatta sannolikheten för att en given nod i nätverket var i det observerade tillståndet (S, I eller R). Vi använder sedan en genomsnittlig fältliknande approximation för att beräkna sannolikheten för den observerade ögonblicksbilden som en produkt av de marginella sannolikheterna. Vi rankar slutligen det möjliga ursprunget enligt den sannolikheten. Den dynamiska meddelande-passing algoritmen (DMP) som vi använder för att uppskatta sannolikheten för en given nod att vara i ett givet tillstånd är intressant i sig. En prekursor dök upp [13] i en form som i genomsnitt över initiala förhållanden, som inte lämpar sig för algoritmisk användning. Här kan vi härleda och använda DMP på ett givet nätverk för givna initiala villkor. Om medelvärdet också ligger över grafensemblen kan den användas för att få de asymptotiskt exakta dynamiska ekvationerna [14, 15] för SIR, eller de för [16] för laviner i det slumpmässiga fältet Ising-modellen. Observera att även om DMP uppvisar viss likhet med standard tro förökning (BP) metod [17, 18], är det avgörande skiljer sig från BP i flera aspekter: det är inte härledd från en Boltzmann-liknande sannolikhetsfördelning, och det behöver inte itereras till konvergens, istället iterationstiden motsvarar direkt den realtid i den tillhörande SIR dynamik. En trevlig egenskap som DMP delar med BP är att det är exakt om kontaktnätverket är ett träd. Vi använder det här som en approximation för loopy-but-sparse kontaktnätverk på samma sätt som BP används med framgång i jämviktsstudier av sådana nätverk. Vi testar vår algoritm på syntetiska spridningsdata och visar att den presterar bättre än befintliga metoder (utom för en särskild region av parametrar där Jordan centrum i genomsnitt är bättre). Algoritmen är mycket robust, till exempel är den fortfarande effektiv även i det fall tillstånd av endast en bråkdel av noder i nätverket observeras. Från våra tester identifierar vi också en rad parametrar för vilka uppskattningen av epidemins ursprung är relativt enkel, och en region där detta problem är svårt. Därför kan vår datauppsättning också fungera som en testbädd för nya metoder. Låt G (V, E) vara en ansluten oriktad graf som innehåller N noder som definieras av uppsättningen hörn V och uppsättningen av kanter E. SIR-modellen definieras enligt följande: Varje nod i vid diskret tidpunkt t kan vara i ett av tre tillstånd q i (t): mottaglig, q i (t) = S, infekterad, q i (t) = I, eller återhämtad, q i (t) = R. Vid varje steg, en infekterad nod kommer att återhämta sig med sannolikhet μ i, och en känslig nod i kommer att bli infekterad med sannolikhet 1 − k på 1 − λ ki λ q k (t), I ), där ∂i är uppsättningen av grannar node i, och λ ki mäter effektiviteten av spridning från k till i. De återvunna noderna ändrar aldrig sitt tillstånd. Vi antar att grafen G och parametrar λ ij, μ i är kända (eller redan har härletts). De allmänna egenskaperna och fasdiagrammet för denna modell på slumpmässiga nätverk studerades i många verk, se t.ex. [3] och hänvisningar i detta. För att definiera problemet med uppskattning av epidemins ursprung, anser vi att det är fallet där, vid första tidpunkten t = 0, endast en nod är infekterad (den "patient noll", i 0 ), och alla andra noder är mottagliga. Efter t 0 > 0 tidssteg (t 0 är i allmänhet okänt), observerar vi tillståndet för en uppsättning noder O  på V, och uppgiften är att uppskatta platsen för patienten noll baserat på denna ögonblicksbild. Låt oss kortfattat förklara två befintliga algoritmer [4, 6, 7] som vi kommer att använda som riktmärken. Författarna till [4, 6, 7] övervägde endast fallet när alla noder observerades, O = V. I bilaga B föreslår vi en generalisering av dessa algoritmer till ett mer allmänt fall. Det mest grundläggande måttet för node i att vara epidemiskt ursprung är den avståndscentralitet D(i) som vi definierar som D(i)  och j.G d(i, j) δ qj,I + δ qj,R /μ j, där grafen G är en ansluten komponent i den ursprungliga grafen G som innehåller alla infekterade och återvunna noder och endast dem, och d(i, j) är den kortaste vägen mellan nod i och nod j på grafen G. Ad-hoc faktor 1/μ j introduceras för att skilja återvunna noder som för små μ j tenderar att vara närmare epidemins ursprung. I de befintliga arbetena var denna faktor inte närvarande, eftersom [4, 6] endast behandlade SI-modellen, och [7] ansåg att mottagliga och återvunna noder är oskiljaktiga. Författarna till [4, 6] föreslog en "rumor centrality" estimator och visade att, för träd grafer, rykte centralitet och avstånd centralitet sammanfaller. En annan enkel men välfungerande estimator, Jordan centrality J(i), föreslogs i [7] och motsvarar en nod som minimerar det maximala avståndet till andra infekterade och återvunna noder: En nod i där J(i) är minimal kallas för "Jordan center" av G i grafteori litteratur. Observera att i [7] Jordan centrum för endast infekterade anteckningar användes, därav vårt genomförande använder mer information. Kärnan i den algoritm som föreslås i detta arbete är DMP, förklaras i nästa avsnitt, som ger en uppskattning av sannolikheterna P j S (t, i 0 ) (respektive P j I (t, i 0 ), P j R (t, i 0 )) att en node j är i var och en av de tre staterna S, I, R, vid tiden t, för en given patient noll i 0. Låt oss först anta att tiden t 0 är känd. Med användning av Bayes regel, sannolikheten för att node i är patienten noll med tanke på de observerade tillstånden är proportionell mot den gemensamma sannolikheten för observerade tillstånd med tanke på patienten noll, P (i-O) P (O-i). Vi definierar också en energiliknande funktion hos varje nod E(i)  och - log P (O på), så att noder med lägre energi är mer benägna att vara infektionskällan. Om man kunde beräkna P (O) exakt, att hitta i som minimerar E(i) skulle vara en optimal inference schema för patienten noll. Eftersom det inte finns något dragbart sätt att beräkna exakt den gemensamma sannolikheten för observationer, vi approximerar det med ett medelvärde-fält-typ metod som en produkt av marginal sannolikheter som tillhandahålls av den dynamiska meddelande-passing För att uppskatta värdet av t 0, beräknar vi energi E(i, t) för olika möjliga värden t, och väljer det värde som maximerar "partition funktion" Z(t)  på e −E(i,t). Låt oss förklara de dynamiska meddelandepasserande ekvationerna för SIR-modellen. Beviset för att dessa ekvationer är exakta på träd, och kopplingarna till vissa relaterade befintliga resultat [13] [14] [15] [16] [19] [21] [22], diskuteras i bilaga A. Vi definierar först meddelandet P i→j S (t) som sannolikheten för nod i att vara i tillstånd S vid tidpunkten t i den hålighet diagram där nod j har tagits bort. Mängden k→i (t) är sannolikheten för att nod k inte ska passera infektionssignalen till nod i upp till tid t, och k→i (t) är sannolikheten för att nod k ska vara i det tillstånd jag och inte att passera infektionen till nod i upp till tid t. Det ursprungliga tillståndet är  en k→i (0) = 1, och en k→i (0) = δ q k (0),I. För mer information se 3 bilaga A. Dessa meddelanden uppfyller rekursionsreglerna: Här ∂i\j betyder uppsättningen av noder som gränsar till nod i, exklusive j. De marginella sannolikheter som node i är i ett givet tillstånd vid tidpunkten t anges sedan som Därför algoritmisk komplexitet för att beräkna energi E(i) av en given vertex i (och därmed sannolikheten att det är epidemiskt ursprung) är O(t 0 N c), där c är den genomsnittliga graden av grafen. Vi testar först vår algoritm på slumpmässiga regelbundna grafer, d.v.s. Slumpmässiga grafer hämtade på samma sätt från uppsättningen grafer där varje nod har grad c. I alla simuleringar anser vi att sannolikheten för enhetlig överföring och återhämtning är λ ij = λ och μ i = μ. I det första exemplet, infälld bild. 1, Vi rita energi E(i) till följd av den dynamiska meddelande-passing av noderna för vilka sannolikheten för att vara epidemisk ursprung är ändlig enligt vår algoritm, vi beställer noderna enligt energivärdet. Det verkliga epidemiska ursprunget är markerat med ett rött kors. Vi definierar rangen av kandidater för epidemin ursprung att vara dess position i denna rankning (den lägsta energinod som har rang 0). Huvuddiagrammet i bild. 1 visar histogrammet för normaliserade led (dvs. rankningen dividerad med det totala antalet noder som observerades som återvunna eller infekterade) av det verkliga epidemiska ursprunget som erhållits från vår DMP inference algoritm, jämfört med de rankningar som erhållits genom avstånd, rykte och Jordan centraliteter. DMP:s slutsatsalgoritm överträffar avsevärt de tre centralitetsmåtten, med en jämförbar beräkningskostnad. På bild. 2 Vi presenterar den genomsnittliga normaliserade rankningen av den sanna epidemin ursprung för slumpmässiga regelbundna grafer för hela intervallet av överföringsannolikheten λ, för olika värden av återhämtningsannolikheten μ, och ögonblicksbild gånger t 0. Som en uppskattning för spridningstiden t 0, vi tar den som maximerar " partition funktion" Z(t) = i e −E(i,t). Fördelningen av den beräknade tiden är koncentrerad vid den verkliga spridningstiden t 0. Vi finner att för olika värden av μ, DMP inference överträffar centralitet åtgärder (se, t.ex., fall (a)), utom Inset: En epidemi genereras med återhämtningsannolikhet μ = 1, överföringsannolikhet λ = 0,6, en ögonblicksbild av alla noder tas vid tiden t0 = 8 (i denna siffra antar vi att vi vet värdet av t0), 242 noder observeras vara i I eller R-tillståndet. Den dynamiska meddelande-passing används för att beräkna energin i varje nod. Denna energi är ändlig för 43 noder; den ritas som en funktion av deras rank r. Den sanna patienten noll markeras med ett rött kors, och dess rang är r(i0) = 2 i detta fall. Huvudtal: en epidemi som alstras med μ = 1, λ = 0,5, t0 = 5. Den normaliserade rangens histogram (över 1000 slumpmässiga fall) (dvs. rangen dividerad med antalet R eller I noder i ögonblicksbilden) för den sanna patienten noll ritas för den dynamiska meddelande-passing (DMP) slutsats, liksom för avstånd, rykte och Jordanien centralitet åtgärder. I ett specialfall (b) (μ = 1, vilket motsvarar den deterministiska återhämtningen), i ett intervall på 0,3 < λ < 0,58 där Jordaniens centrum är en bättre uppskattning. I andra fall är emellertid Jordaniens centralitet mindre framträdande. Observera att för μ < 1 Jordan centralitet inte skiljer mellan återvunna och infekterade noder, vilket delvis förklarar dess ganska dåliga prestanda i det fallet. Fikonen. 2 c visar beroendet av spridningstiden t 0 för fasta värden på λ och μ. Observera att DMP förblir effektiv även för relativt stora t 0, när centralitet algoritmer misslyckas med att göra en förutsägelse. Viktigt, i vissa intervall av parametrar, den genomsnittliga normaliserade rank av den sanna epidemin ursprung är inte så nära noll (observera att värdet 1/2 av den normaliserade rank motsvarar en slumpmässig gissning av patient noll bland alla infekterade eller återvunna noder). Problemet med att uppskatta epidemins ursprung med god precision är mycket svårt i dessa regioner. I vissa fall gick informationen om epidemins ursprung förlorad under spridningsprocessen. Till exempel för λ > λ c = μ/(c − 2 + μ) [23] perkolerar epidemin vid stora tider t 0 log c N; sedan försvinner informationen om epidemins ursprung. Å andra sidan för t 0 < log c N, epidemin är begränsad till ett träd nätverk och i detta fall slutsatsen om ursprunget är lättare, jfr. Bilda. 2 c............................................................................. På bild. 2, a) och ( Varje datapunkt är i genomsnitt över 1000 fall. Tomterna a och b representerar beroendet av den genomsnittliga rangen på infektionsfrekvensen λ, för ögonblicksbildstiden t0 = 10 och återhämtningsannolikheten μ: a) μ = 0,5 och b) μ = 1. I denna siffra t0 härleds från algoritmen. DMP-skattningen jämförs med Jordans centralitet och avståndsskattningsvärdena. Den streckade linjen visar den genomsnittliga fraktionen av noder som smittades eller återfanns i snapshot,  och/eller N, vi använder detta nummer för att normalisera leden av epidemiskt ursprung. Plot (c) visar beroendet av ögonblicksbildstiden t0 för λ = 0,7 och μ = 0,5. Den streckade linjen är den genomsnittliga fraktionen av noder som var infekterade och den streck-streckade linjen är den genomsnittliga fraktionen av noder som återfanns i ögonblicksbilden; båda normaliseras till N. vår uppfattning den systematiska jämförelsen presenteras här är en bra test-bädd för att jämföra och förbättra algoritmer. Vi visar nu prestandan för vår algoritm i fallet där ögonblicksbilden är ofullständig: en bråkdel av noder inte observeras. Vi jämför det med de generaliseringar av Jordanien och avståndscentraliteter som vi föreslår i bilaga B. Bilda. 3 a) anger den genomsnittliga rangen för det verkliga epidemiska ursprunget. Det visar att DMP:s inferencealgoritm, med ofullständiga ögonblicksbilder, överträffar båda centraliseringarna även i det fall där Jordans centralitet var bättre för fullständiga ögonblicksbilder. Denna observerade robusthet hos DMP är en mycket användbar egenskap. I exemplet avbildat på bild. 3 (b), Vi studerade prestanda DMP på en icke-regelbunden nätverk av US East-Coast elnät som innehåller N = 4941 noder med en maximal grad 19 [24]. Vi ser att DMP estimator ger bättre förutsägelse för alla områden av λ. Resultaten för slumpmässiga skala-fria och Erdös-Rényi nätverk ges i bilaga C. Vår algoritm bygger på en approximation till Bayes optimal inference, det finns två möjliga källor till sub-optimalitet på verkliga nätverk. Den första är det faktum att meddelande-passing ekvationer kan leda till fel på loopy grafer. Den andra är den genomsnittliga fältliknande approximationen (1) av den gemensamma sannolikhetsfördelningen. Vi har konstaterat att med hänsyn till tvåpunktsförhållandet i denna approximation leder det inte till någon förbättring av våra resultat. Det skulle vara intressant att söka efter bättre approximationer av sannolikheten för en allmän graf. Den ungefärliga lösningen av dynamik av SIR-modellen i termer av meddelandepasserande ekvationer gjorde det möjligt för oss att utveckla en effektiv probabilistisk algoritm för att upptäcka patient noll. Jämfört med befintliga algoritmer, det generiskt (utom för ett smalt utbud av parametrar). Återhämtningsannolikheten μ = 1, överföringsannolikheten λ = 0,5 och λ = 0,7, endast tillståndet för ett bråk 1 −  på noderna observeras vid tiden t0 = 10, antas vara känt. Den rankning (i genomsnitt över 1000 fall) av det verkliga epidemiska ursprunget som erhålls med vår DMP inference algoritm jämförs med avståndet och Jordan centraliteter. Höger: b) Normaliserad rankning (i genomsnitt över 1000 fall) av det verkliga epidemiska ursprunget för epidemispridning med μ = 0,5, och alla noder observerade vid tiden t0 = 10, på nätverken i US East-Coast elnätet. DMP-slutsatsen är betydligt bättre än slutsatsen baserad på avstånd och jordanska centraliteter. ger en förbättrad uppskattning av källan till infektiöst utbrott. Det fungerar också bra när ögonblicksbilden bara ser en del av nätverket. En överlägsenhet i vårt tillvägagångssätt jämfört med tidigare är att det effektivt använder informationen om var epidemin inte spreds. Som vanligt för Bayes inference metoder, är vår algoritm mångsidig och lätt amenable till gener-5 alizations: det kan enkelt behandla fallet med dynamiskt föränderliga nätverk, fallet med flera källor och även fallet där kontaktnätverket inte är fullt känt. ERKÄNNANDEN
När t.ex. en fraktion x noder väljs slumpmässigt föreslår REF en metod som bygger på kunskap om tillståndet (S, I eller R) för en fraktion av noderna i grafen vid en given tidpunkt och där epidemins starttid, om den är okänd, kan härledas från tillgängliga data.
Inferring the origin of an epidemic with a dynamic message-passing algorithm
{'venue': 'Phys. Rev. E 90, 012801 (2014)', 'journal': None, 'mag_field_of_study': ['Physics', 'Computer Science', 'Medicine', 'Biology']}