Online-Verarbeitungsalgorithmen zur Maximierung des Einflusses

Die Maximierung des Einflusses ist ein klassisches und umfassend erforschtes Problem mit wichtigen Anwendungen im viralen Marketing. Bestehende Algorithmen zur Maximierung des Einflusses konzentrieren sich jedoch größtenteils auf die Offline-Verarbeitung, in dem Sinne, dass sie keine Ausgabe an den Benutzer liefern, bis die endgültige Antwort abgeleitet wird, und dass der Benutzer den Algorithmus nicht vorzeitig beenden darf, um die Qualität der Lösung gegen Effizienz zu tauschen. Ein solches Fehlen von Interaktivität und Flexibilität führt zu einer schlechten Benutzererfahrung, insbesondere wenn der Algorithmus lange Laufzeiten verursacht. Um das oben genannte Problem anzugehen, untersucht dieses Papier Algorithmen für die Online-Verarbeitung der Einflussmaximierung (OPIM), bei denen der Benutzer den Algorithmus jederzeit pausieren und nach einer Lösung (für das Einflussmaximierungsproblem) sowie ihrer Näherungsgarantie fragen kann und den Algorithmus wieder aufnehmen kann, um die Qualität der Lösung zu verbessern, indem ihm mehr Zeit zum Laufen gegeben wird. (Dieses interaktive Paradigma ist im Geiste dem Online-Abfrageprocessing in Datenbanksystemen ähnlich.) Wir zeigen, dass der einzige bestehende Algorithmus für OPIM in der Praxis äußerst ineffektiv ist, und dass die Adaption bestehender Methoden zur Einflussmaximierung für OPIM unbefriedigende Ergebnisse liefert. Motiviert durch dies schlagen wir einen neuen Algorithmus für OPIM vor, der sowohl überlegene empirische Effektivität als auch starke theoretische Garantien bietet, und wir zeigen, dass er auch erweitert werden kann, um die konventionelle Einflussmaximierung zu behandeln. Umfangreiche Experimente mit realen Daten zeigen, dass unsere Lösungen die aktuelle Spitzenleistung sowohl für OPIM als auch für die konventionelle Einflussmaximierung übertreffen.