Modeller för de processer genom vilka idéer och inflytande sprids genom ett socialt nätverk har studerats på ett antal områden, bland annat spridningen av medicinska och tekniska innovationer, det plötsliga och utbredda antagandet av olika strategier i spelteoretiska miljöer, och effekterna av "munnord" i främjandet av nya produkter. Nyligen, motiverat av utformningen av virala marknadsföringsstrategier, Domingos och Richardson utgjorde ett grundläggande algoritmiskt problem för sådana sociala nätverksprocesser: om vi kan försöka övertyga en del av individer att anta en ny produkt eller innovation, och målet är att utlösa en stor kaskad av ytterligare adoptioner, vilken uppsättning individer bör vi rikta? Vi betraktar detta problem i flera av de mest studerade modellerna inom analys av sociala nätverk. Optimeringsproblemet med att välja de mest inflytelserika noderna är NP-hård här, och vi ger de första bevisbara approximationsgarantier för effektiva algoritmer. Med hjälp av en analysram baserad på submodulära funktioner, visar vi att en naturlig girig strategi får en lösning som är bevisligen inom 63 % av optimal för flera klasser av modeller; vårt ramverk föreslår en allmän strategi för resonemang om prestandagarantier för algoritmer för dessa typer av påverkansproblem i sociala nätverk. Vi tillhandahåller också beräkningsexperiment på stora samarbetsnätverk, som visar att våra approximationsalgoritmer, förutom sina bevisbara garantier, är betydligt ogenomförbara nodervalheuristiker baserade på de välstuderade begreppen examenscentralitet och distanscentralitet från området sociala nätverk.
Eftersom problemet med att hitta de mest inflytelserika hörnen är NPhard, används approximationsalgoritmer i REF-utförande grundläggande heuristik baserad på grad centralitet och avstånd centralitet som tillämpas traditionellt i sociala nätverk.
Maximizing the spread of influence through a social network
{'venue': "KDD '03", 'journal': None, 'mag_field_of_study': ['Computer Science']}