Hur kan vi lokalisera källan till diffusion i ett komplext nätverk? På grund av den enorma storleken på många verkliga nätverk-såsom Internet eller den mänskliga sociala grafen-det är vanligtvis omöjligt att observera tillståndet för alla noder i ett nätverk. Vi visar att det i grunden är möjligt att uppskatta källans läge från mätningar som samlats in av glest placerade observatörer. Vi presenterar en strategi som är optimal för godtyckliga träd, uppnå maximal sannolikhet för korrekt lokalisering. Vi beskriver effektiva implementeringar med komplexitet O(N α ), där α = 1 för godtyckliga träd, och α = 3 för godtyckliga grafer. I samband med flera fallstudier bestämmer vi hur lokaliseringsnoggrannheten påverkas av olika systemparametrar, inklusive nätverkets struktur, observatörernas densitet och antalet observerade kaskader. Att lokalisera källan till ett smittämne eller ett virus är en mycket önskvärd men utmanande uppgift. I naturen är många djur i sig kapabla att utföra källlokalisering. Genom cytostatika, till exempel, vissa bakterier kan analysera koncentrationsgradienter runt dem för att snabbt gå mot källan till ett näringsämne, eller snabbt undvika källan till ett gift [1, 2]. Djur som Stillahavslaxen och de gröna havssköldpaddorna kan använda olfaction för att navigera i luktplymer, för födosök eller fortplantning [3, 4]. I vissa system måste emellertid uppgiften att lokalisera källan utföras i ett nätverk snarare än i det kontinuerliga utrymmet. Så är till exempel fallet när en infektionssjukdom sprids genom människor över en stor region, vilket konstaterades i samband med den världsomspännande H1N1-viruspandemin 2009. Här är systemet mer bekvämt modellerat som ett nätverk av sammankopplade människor, och källlokalisering minskar till att identifiera vilken person i nätverket först smittades. Under de senaste åren har det gjorts betydande ansträngningar för att studera dynamiken i epidemiutbrott på nätverk [5] [6] [7] [7] [8] [9] [10] [11]. I synnerhet har fokus legat på det framtida problemet med epidemier: att förstå spridningsprocessen och dess beroende av antalet infektioner och botemedel samt nätverkets struktur. I detta brev fokuserar vi på det omvända problemet med att härleda den ursprungliga källan till diffusion, med tanke på infektionsdata som samlats in vid några av noderna i nätverket. Förmågan att uppskatta källan är ovärderlig när det gäller att hjälpa myndigheterna att begränsa epidemin eller kontaminationen. I detta sammanhang studerades slutsatsen av det underliggande förökningsnätverket i [12], medan slutsatsen av den okända källan analyserades i [13], i båda fallen förutsatt att vi vet tillståndet för alla noder i nätverket. På senare tid har kontrollmöjligheterna för komplexa nätverk beaktats i [14], med hjälp av lämpligt utvalda förarnoder. Här är vårt mål att lokalisera källan till diffusion under den praktiska begränsningen att endast en liten del av noderna kan observeras. Så är till exempel fallet när man lokaliserar en spammare som skickar oönskade e-postmeddelanden över Internet, där det helt klart är omöjligt att övervaka alla noder. Därför är den största svårigheten att utveckla dragbara skattningar som kan genomföras effektivt (dvs. med subexponentiell komplexitet), och att källuppskattning på en godtycklig graf G. Vid den okända tiden t = t *, informationskällan s * initierar diffusionen. De blå kanterna betecknar de över vilka informationen redan har spridit sig. I detta exempel finns det tre observatörer, som mäter från vilka grannar och vid vilken tidpunkt de fick informationen. Målet är att utifrån dessa observationer uppskatta vilken nod i G som är informationskällan. prestera bra på flera topologier. Vi introducerar först vår nätverksmodell. Det underliggande nätverket på vilket diffusion äger rum är modellerat av en ändlig, oriktad graf G = {V, E}, där vertex uppsättning V har N noder, och kanten uppsättning E har L kanter (Fig. 1).................................................................. Grafen G antas vara känd, åtminstone ungefärligt, vilket ofta bekräftas i praktiken, t.ex. rykten som sprider sig i ett socialt nätverk, eller elektriska störningar som sprider sig på elnätet. Informationskällan, s *  på G, är den vertex som ger upphov till informationen och initierar diffusionen. Vi modellerar s * som en slumpmässig variabel (RV) vars tidigare distribution är enhetlig över den inställda V, dvs., någon nod i nätverket är lika sannolikt att vara källan a priori. Spridningsprocessen är modellerad enligt följande. Vid tidpunkten t, varje vertex u  på G har en av två möjliga stater: i) informerade, om den redan har fått informationen från någon granne, eller ii) okunniga, om den inte har informerats hittills. Låt V(u) betecknar uppsättningen hörn direkt ansluten till u, dvs, grannskapet eller närheten av u. Antag att u är i okunnigt tillstånd och, vid tiden t u, får informationen för första gången från en granne-säga, s-därmed bli informerad. Och sen...
Detta beslut träder i kraft dagen efter det att det har offentliggjorts i Europeiska unionens officiella tidning. också formulerat ett liknande problem med att lokalisera källan till spridning i nätverk från glesa platser observatörer REF.
Locating the Source of Diffusion in Large-Scale Networks
{'venue': 'Physical review letters', 'journal': 'Physical review letters', 'mag_field_of_study': ['Physics', 'Medicine', 'Computer Science']}