Problemet med att identifiera viktiga aktörer i ett visst nätverk är av avgörande betydelse för viral marknadsföring, folkhälsoförvaltning, nätsäkerhet och olika andra områden för analys av sociala nätverk. I detta arbete finner vi de viktigaste hörnen i en graf G = (V, E) att immunisera så att chanserna för en epidemi utbrott minimeras. Detta problem är direkt relevant för att minimera effekterna av en spridning av smitta (t.ex. influensavirus, datavirus och rykten) i ett diagram (t.ex. Sociala nätverk, datornät) med begränsad budget (t.ex. antalet tillgängliga vacciner, antivirusprogram, filter). Det är väl känt att detta problem är beräkningsmässigt intractable (det är NP-hård). I detta arbete omformulerar vi problemet som ett budgeterat kombinationsoptimeringsproblem och använder tekniker från spektral grafteori för att utforma en effektiv girig algoritm för att hitta en delmängd av hörn som ska immuniseras. Vi visar att vår algoritm tar mindre tid jämfört med toppmodern algoritm. Därför är vår algoritm skalbar till nätverk av mycket större storlekar än de mest kända lösningar som föreslagits tidigare. Vi ger också analytiska gränser för kvaliteten på vår algoritm. Dessutom utvärderar vi effektiviteten hos vår algoritm på ett antal verkliga nätverk och visar att algoritmens empiriska prestanda kompletterar de teoretiska gränser vi presenterar, både i form av approximativa garantier och beräkningseffektivitet.
Tillnärmning av antalet stängda promenader av längd 6 som innehåller en nod med hjälp av en slumpmässigt konstruerad sammanfattning av en graf ges i REF.
Scalable Approximation Algorithm for Network Immunization
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}