Bibliography | Rollbühler, Felix: Influence maximization in the linear threshold diffusion model. University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Bachelor Thesis No. 24 (2021). 77 pages, english.
|
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.
|