Influence maximization, grundläggande för word-of-mouth marknadsföring och viral marknadsföring, syftar till att hitta en uppsättning frönoder maximera inflytande sprids på sociala nätverk. Tidiga metoder faller främst in i två paradigm med vissa fördelar och nackdelar: (1) Giriga algoritmer, välja frö noder en efter en, ger en garanterad noggrannhet beroende på den exakta approximationen av inflytande spridning med höga beräkningskostnader; (2) Heuristiska algoritmer, uppskatta påverkan spridning med hjälp av effektiv heuristik, har låg beräkningskostnad men instabil noggrannhet. Vi påpekar först att giriga algoritmer i huvudsak hittar en självkonsekvent ranking, där nodernas led är förenliga med deras rankning-baserade marginella inflytande spridning. Denna insikt motiverar oss att utveckla ett iterativt rankningsramverk, dvs. IMRank, för att effektivt lösa påverkansmaximeringsproblem under oberoende kaskadmodell. Med utgångspunkt från en inledande rankning, t.ex. en som erhållits från effektiv heuristisk algoritm, finner IMRank en självkonsistent rankning genom att omordna noder iterativt i termer av deras rankning-baserade marginalinfluens spridd enligt aktuell rankning. Vi bevisar också att IMRank definitivt konvergerar till en självkonsistent ranking från alla ursprungliga ranking. Inom denna ram föreslås dessutom en sista-till-första fördelningsstrategi och en generalisering av denna strategi för att förbättra effektiviteten i uppskattningen av rankningsbaserad marginell påverkansspridning för en given rankning. På så sätt uppnår IMRank både anmärkningsvärd effektivitet och hög noggrannhet genom att samtidigt utnyttja fördelarna med giriga algoritmer och heuristiska algoritmer. Som framgår av omfattande experiment på storskaliga sociala nätverk i verkligheten uppnår IMRank alltid hög noggrannhet jämförbar med giriga algoritmer, medan beräkningskostnaden minskas dramatiskt, cirka 10 – 100 gånger snabbare än andra skalbara heuristiker.
Att kombinera både giriga och heuristiska algoritmer, Cheng et al. Ref föreslog IMRank, som fann en självkonsekvent rankning genom att överväga rankning baserad marginell påverkan spridning enligt nuvarande rankning.
IMRank: influence maximization via finding self-consistent ranking
{'venue': None, 'journal': 'Proceedings of the 37th international ACM SIGIR conference on Research & development in information retrieval', 'mag_field_of_study': ['Computer Science']}