Influence Maximization with ε-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). We first show a strong hardness result: there is no 1/n γ/c approximation for influence maximization (unless P = NP) for all networks with up to n γ ε-almost submodular nodes, where γ is in (0,1) and c is a parameter depending on ε. This indicates that influence maximization is still hard to approximate even though threshold functions are close to submodular. We then provide (1 − ε) (1 − 1/e) approximation algorithms when the number of ε-almost submodular nodes is . Finally, we conduct experiments on a number of real-world datasets, and the results demonstrate that our approximation algorithms outperform other baseline algorithms.
This paper studies influence maximization in the general threshold diffusion model, specifically when node threshold functions are almost submodular (or epsilon-submodular). The key results are: 1) a proof of inapproximability for the influence maximization problem under this model when there are sufficiently many epsilon-submodular threshold nodes; 2) an efficient, simple and principled approximation algorithm for this problem when there is some fixed number of epsilon-submodular threshold nodes.
        This is a strong paper for the following reasons:
        1- Influence maximization under the General Threshold model is a challenging and poorly studied problem;
        2- The epsilon-submodularity condition is very reasonable because it is consistent with empirical evidence in real diffusion processes;
        3- The hardness result and the approximate algorithms are intuitive and non-trivial.
        Barring minor typos and the like (see below for details), the paper is very well-written. In my understanding, the technical proofs are correct. The experimental evaluation is thorough and convincing, and the results are consistent with the theoretical guarantees.
        Minor comments (by line):
        102: shouldn't the equation right-hand side have 1/(1-\epsilon) instead of (1-\epsilon)?
        237: "linear" instead of "liner"
        241: "satisfying" instead of "satisfies"
        262: "PageRank" instead of "PagrRank"
        297: "compared to 2.05" instead of "while 2.05"
        298: "spread" instead of "spreads"
        299: "The more $\epsilon$-AS nodes there are in the network, the more improvement is obtained"