Influence maximization, definierat som ett problem att hitta en uppsättning frönoder för att utlösa en maximerad spridning av inflytande, är avgörande för viral marknadsföring på sociala nätverk. För praktisk viral marknadsföring på storskaliga sociala nätverk, är det nödvändigt att påverka maximering algoritmer bör ha både garanterad noggrannhet och hög skalbarhet. Emellertid, befintliga algoritmer lider en skalbarhet-noggrannhet dilemma: konventionella giriga algoritmer garanterar noggrannheten med dyra beräkningar, medan skalbara heuristiska algoritmer lider av instabil noggrannhet. I detta dokument fokuserar vi på att lösa detta dilemma med skalbarhet och noggrannhet. Vi påpekar att den väsentliga orsaken till dilemmat är det överraskande faktum att submoduliteten, ett viktigt krav på den objektiva funktionen för en girig algoritm för att approximera det optimala, inte garanteras i alla konventionella giriga algoritmer i litteraturen om inflytande maximering. Därför måste en girig algoritm ha råd med ett stort antal Monte Carlo simuleringar för att minska den smärta som orsakas av ogaranterad submodulitet. Motiverade av detta kritiska fynd, föreslår vi en statisk girig algoritm, som heter StaticGreedy, för att strikt garantera submodulaliteten av inflytande spridning funktion under frö urvalsprocessen. Den föreslagna algoritmen gör beräkningsutgiften dramatiskt reducerad med två storleksordningar utan förlust av noggrannhet. Dessutom föreslår vi en dynamisk uppdateringsstrategi som kan påskynda algoritmen StaticGreedy 2-7 gånger på storskaliga sociala nätverk.
Cheng m.fl. REF dra nytta av statiska ögonblicksbilder och föreslå en statisk girig algoritm som kallas Stat-icGreedy, som minskar omgången av Monte-Carlo simulering med ungefär två storleksordningar.
StaticGreedy: solving the scalability-accuracy dilemma in influence maximization
{'venue': 'CIKM', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Physics']}