Comparative Study of Combinatorial Algorithms for Solving the Influence Maximization Problem in Networks under a Deterministic Linear Threshold Model

摘要

The Influence Maximization problem consists in finding a set of most influential agents in a social network. In the present paper this problem is studied for a variant of Deterministic Linear Threshold Model of information dissemination with equivalent weights. It is closely related to Granovetter’s threshold model of collective behaviour. The fact that the considered model does not employ randomization makes it possible to use state-of-the-art combinatorial algorithms for finding sets of influential vertices. The implementations for different algorithms are proposed and evaluated for several computational approaches to solving influence maximization problem for a considered model. The algorithms in question include genetic algorithms, greedy algorithms, graph-based heuristics and algorithms for solving Boolean satisfiability problem.