Med tanke på ett socialt nätverk G och en konstant k, influence maximization problem frågar efter k noder i G som (direkt och indirekt) påverkar det största antalet noder under en fördefinierad diffusion modell. Detta problem finner viktiga tillämpningar inom viral marknadsföring och har studerats i stor utsträckning i litteraturen. Befintliga algoritmer för påverkan maximering, dock, antingen handels approximation garantier för praktisk effektivitet, eller vice versa. Bland de algoritmer som uppnår konstanta faktor approximationer enligt den framträdande oberoende kaskadmodellen eller modellen med linjär tröskel (LT) kan ingen hantera en millionnodekurva utan att ådra sig oöverkomliga omkostnader. Denna uppsats presenterar TIM, en algoritm som syftar till att överbrygga teori och praktik i påverkan maximering. På teorisidan visar vi att TIM körs i O(k + )n + m) log n/ε 2 ) förväntad tid och returnerar en (1 − 1/e − ε) ungefärlig lösning med minst 1 − n − sannolikhet. Tids komplexiteten hos TIM är nära optimal under IC-modellen, eftersom det bara är en log n faktor större än den (m + n) lägre gränsen etablerad i tidigare arbete (för fasta k,, och ε). Dessutom stöder TIM den utlösande modellen, som är en allmän spridningsmodell som omfattar både IC och LT som specialfall. På praktiksidan innehåller TIM nya heuristiker som avsevärt förbättrar dess empiriska effektivitet utan att äventyra dess asymptotiska prestanda. Vi utvärderar experimentellt TIM med de största datauppsättningar som någonsin testats i litteraturen, och visar att det överträffar de toppmoderna lösningarna (med approximativa garantier) med upp till fyra storleksordningar i fråga om körtid. Särskilt när k = 50, ε = 0,2 och = 1, TIM kräver mindre än en timme på en varumaskin för att bearbeta ett nätverk med 41,6 miljoner noder och 1,4 miljarder kanter. Detta visar att influensalgoritmer för maximering kan göras praktiska samtidigt som de erbjuder starka teoretiska garantier.
Här noterar vi att det för närvarande är den senaste tekniken för MaxSpread och har visat sig skala till en miljard-kant nät REF.
Influence maximization: near-optimal time complexity meets practical efficiency
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}