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. Motiverad 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. De två konferensdokument som denna artikel bygger på (KDD 2003 och ICALP 2005) ger de första bevisbara approximationsgarantierna för effektiva algoritmer. Med hjälp av en Den här artikeln är en utökad version av två konferensbidrag [51, 52], som publicerades i KDD 2003 respektive ICALP 2005, respektive. * 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 bättre än perform nodeval-heuristik baserad på de välstuderade begreppen examenscentralitet och distanscentralitet från området sociala nätverk. Ett socialt nätverk-grafen över relationer och interaktioner inom en grupp av individer-spelar en grundläggande roll som ett medium för spridning av information, idéer, och inflytande bland sina medlemmar. En idé eller innovation kommer att framträda-till exempel, användningen av mobiltelefoner bland college studenter, antagandet av en ny drog inom läkaryrket, eller uppkomsten av en politisk rörelse i ett instabilt samhälle-och det kan antingen dö ut snabbt eller göra betydande intrång i befolkningen. Om vi vill förstå i vilken utsträckning sådana idéer antas, kan det vara viktigt att förstå hur dynamiken i antagandet sannolikt kommer att utvecklas inom det underliggande sociala nätverket: i vilken utsträckning människor sannolikt kommer att påverkas av sina vänners och kollegers beslut, eller i vilken utsträckning "ord-of-mouth"-effekterna kommer att få fäste. Sådana nätverk spridningsprocesser har en lång historia av studier i samhällsvetenskap. Några av de tidigaste systematiska undersökningarna inriktades på data om antagandet av medicinska och jordbruksinnovationer i både utvecklade och utvecklande delar av världen [23, 69, 79], i andra sammanhang, forskning har undersökt diffusionsprocesser för "ord-of-mouth" och "viral marknadsföring" effekter i framgången för nya produkter [8, 14, 26, 33, 32, 59, 68], plötsliga och utbredda antagandet av olika strategier i spelteoretiska miljöer [11, 29, 61, 85, 86], och problemet med kaskadfel i kraftsystem [7, 6]. Domingos och Richardson var motiverade av tillämpningar för marknadsföring och utgjorde ett grundläggande algoritmiskt problem för sådana system [26, 68]. Anta att vi har data på ett socialt nätverk, med uppskattningar av i vilken utsträckning individer påverkar varandra, och vi vill marknadsföra en ny produkt som vi hoppas kommer att antas av en stor del av nätverket. Premissen för viral marknadsföring är att genom att initialt rikta några "influentiella" medlemmar av nätverket-say, ge dem gratis prover av produkten-vi kan utlösa en kaskad av inflytande genom vilken vänner kommer att rekommendera produkten till andra vänner, och många individer kommer i slutändan att prova det. Men hur ska vi välja de få nyckelpersoner som vi kan använda för att så denna process? I [26, 68], denna fråga beaktades i en probabilistisk modell för interaktion; heuristik gavs för att välja kunder med en stor övergripande effekt på nätverket, och metoder utvecklades också för att dra slutsatsen den påverkan data som krävs för att posera dessa typer av problem. I den här artikeln betraktar vi frågan om att välja inflytelserika grupper av individer som ett problem i diskret optimering. Den optimala lösningen är NP-hård för de flesta modeller som har studerats, inklusive modellen av [26]. Den ram som föreslås i [68], å andra sidan, bygger på en enkel linjär modell där lösningen på optimeringsproblemet kan erhållas genom att lösa ett system med linjära ekvationer. Här fokuserar vi på en samling relaterade, NP-hårda modeller som har studerats ingående i sociala nätverk gemenskap, och få de första bevisbara approximationsgarantier för effektiv teori
Kempe, Kleinberg och Tardos REF formulerar problemet som ett diskret optimeringsproblem och tar itu med det med hjälp av en girig algoritm.
Maximizing the Spread of Influence through a Social Network
{'venue': 'Theory of Computing', 'journal': 'Theory of Computing', 'mag_field_of_study': ['Mathematics', 'Computer Science']}