Influence maximization in the linear threshold diffusion model

Abstract

Influence Maximization (IM) is a combinatorial optimization problem which, given a graph, diffusion model and a number k, selects the k vertices that produce the highest combined influence propagation in the graph. This is mainly used in viral marketing, but also other areas. Due to the great economic interests behind it, it has been extensively researched in recent years. The so-called Reverse Influence Sampling (RIS) framework, in which samples are first computed in the form of so-called Reverse Reachable (RR) sets and then the k seed vertices are selected on their basis, has turned out to be one of the central approximation solutions. Although this framework has been researched extensively, there are some gaps in the research in two key areas, namely the generation of the RR sets and also the seed vertex selection. In this work, we examine these two areas of the framework and consider how changes to sampling and seed vertex selection affect the resulting propagated influence in the graph. We specifically consider the Linear Threshold (LT) model, which, along with the Independent Cascade (IC) model, is one of the most widely used diffusion models in the IM domain. Moreover, we present a new way to approximate the RIS framework, whereby the required memory depends only on the number of vertices and is thus independent of the number of RR sets. Furthermore, this is up to a factor of 2500 faster than the state-of-the-art solution. However, in doing so, we lose the (1 − 1/e − ε)-approximation guarantee of the classical Reverse Influence Sampling (RIS)-based approaches and cannot provide any theoretical guarantees for this.

Influence Maximization (IM) ist ein kombinatorisches Optimierungsproblem, welches, gegeben einem Graphen, einem Diffussionsmodell und einer Zahl k, die k Knoten auswählt, welche die höchste kombinierte Einflussausbreitung im Graph hervorrufen. Dieses findet vorallem im Bereich des viralen Marketings, aber auch in anderen Bereichen, Anwendung. Aufgrund der großen dahinterstehenden wirschaftlichen Interessen, wurde es in den vergangenen Jahren ausgiebig erforscht. Dabei hat sich das sogenannte Reverse Influence Sampling (RIS)-Framework, bei welchem zuerst Samples in Form von sogenannten Reverse Reachable (RR) Sets berechnet und anschließend auf deren Basis die k Seedknoten ausgewählt werden, als eine der zentralen Approximationslösungen herausgestellt. Obwohl dieses Framwework sehr ausgiebig erforscht wurde, weist die Forschung in zwei zentralen Bereichen, nämlich der Generierung der RR Sets und auch der Seedknotenauswahl, einige Lücken auf. In dieser Arbeit untersuchen wir diese beiden Bereiche des Frameworks und betrachten, wie sich Veränderungen am Sampling und an der Seedknotenauswahl auf den resultierenden propagierten Einfluss im Graphen auswirken. Dabei betrachten wir speziell das Linear Threshold (LT) Modell, welches neben dem Independent Cascade (IC) Modell eines der am weitesten verbreiteten Diffusionsmodelle im Bereich von IM ist. Zudem stellen wir eine neue Möglichkeit zum Approximieren des RIS-Frameworks vor, wodurch der benötigte Speicherplatz nur noch von der Anzahl der Knoten abhänt und somit unabhängig von der Anzahl der RR Sets ist. Außerdem kann dadurch gegenüber der state-of-the-art Lösung bis zu einem Faktor von 2500 Laufzeit eingespaart werden. Dabei verlieren wir jedoch die (1 − 1/e − ε)-Approximationsgarantie der klassischen RIS-basierten Ansätze und können dafür keine theoretischen Garantien geben.