Independent Cascade Model (ICM) är en väl studerad modell som syftar till att fånga dynamiken i informationsspridningen i sociala nätverk och i allmänna komplexa nätverk. I denna modell kan vi skilja mellan aktiva noder som sprider information och inaktiva. Processen startar från en uppsättning av initialt aktiva noder som kallas frön. Rekursivt, för närvarande aktiva noder kan aktivera sina grannar enligt en sannolikhetsfördelning på uppsättningen av kanter. Efter ett visst antal av dessa rekursiva cykler kan ett stort antal noder bli aktiva. Processen avslutas när ingen ytterligare nod aktiveras. Med utgångspunkt från Domingos och Richardsons arbete [9, 25] har flera studier genomförts i syfte att forma en given diffusionsprocess för att maximera antalet aktiverade noder i slutet av processen. Ett av de mest studerade problemen har formaliserats av Kempe et al. och består i att hitta en uppsättning ursprungliga frön som maximerar det förväntade antalet aktiva noder under en budget begränsning [13]. I detta dokument studerar vi en generalisering av problemet med Kempe et al. I vilken vi får spendera en del av budgeten för att skapa nya kanter incident till fröna. Det vill säga, budgeten kan användas för att köpa frön eller kanter enligt en kostnadsfunktion. Problemet inte admin en PTAS, om inte P = N P. Vi föreslår två approximation algoritmer: den förra ger ett approximationsförhållande som beror på kantkostnader och ökar när dessa kostnader är höga; den senare algoritmen ger en konstant approximation garanti som är större än den första algoritmen när kantkostnaderna kan vara små.
Ett liknande problem där kärnan är gjord av hela nätverket och nätverket kan förstärkas genom att lägga kanter enligt en given kostnadsfunktion har visat sig erkänna en 0,0878-uppskattning algoritm REF.
Selecting nodes and buying links to maximize the information diffusion in a network
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}