Abstract-Information spridning i nätverk kan användas för att modellera många verkliga fenomen, inklusive rykte sprider sig på nätet sociala nätverk, epidemier i människor, och malware på Internet. Informellt sett är problemet med lokalisering av källan att identifiera en nod i nätverket som ger den bästa förklaringen till den observerade diffusionen. Trots betydande ansträngningar och framgångar under de senaste åren, teoretiska garantier för källlokalisering algoritmer etablerades endast för trädnätverk på grund av komplexiteten i problemet. Detta papper presenterar en ny källa localization algoritm, som kallas Short-Fat Tree (SFT) algoritm. Löst taget, algoritmen väljer noden sådan att bredd-första sökningen (BFS) träd från noden har det minsta djupet men det maximala antalet blad noder. Prestandagarantier för SFT enligt den oberoende kaskadmodellen (IC) fastställs för både trädnäten och slumpdiagrammet Erdos-Renyi (ER). På trädnätverk är SFT den maximala efterhandsskattaren (MAP). På ER slumpmässiga grafen, följande grundläggande gränser har erhållits: (i) när infektionens varaktighet < 2 3 t u, SFT identifierar källan med sannolikhet en asymptotiskt, där t u = log n log μ + 2 och μ är den genomsnittliga nodgraden, (ii) när infektionens varaktighet > t u, sannolikheten för att identifiera källan närmar sig noll asymptotiskt under någon algoritm; och (iii) när infektionens varaktighet < t u, BFS träd från källan är ett fett träd. Numeriska experiment på trädnätverk, ER slumpmässiga grafer och verkliga nätverk med olika utvärderingsmått visar att SFT-algoritmen överträffar befintliga algoritmer.
Nyligen övervägde REF den alternativa Independent Cascade (IC)-modellen för infektionsspridning och föreslog algoritmen Short-Fat Tree (SFT) för källidentifiering enligt IC-modellen.
Source Localization in Networks: Trees and Beyond
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}