Influence Maximization with $\varepsilon$-Almost Submodular Threshold Functions

Influence maximization is the problem of selecting k nodes in a social network to maximize their influence spread. The problem has been extensively studied but most works focus on the submodular influence diffusion models. In this paper, motivated by empirical evidences, we explore influence maximization in the nonsubmodular regime. In particular, we study the general threshold model in which a fraction of nodes have non-submodular threshold functions, but their threshold functions are closely upper-and lower-bounded by some submodular functions (we call them ε-almost submodular).