Timezone: »

 
Poster
Influence Maximization with $\varepsilon$-Almost Submodular Threshold Functions
Qiang Li · Wei Chen · Institute of Computing Xiaoming Sun · Institute of Computing Jialin Zhang

Mon Dec 04 06:30 PM -- 10:30 PM (PST) @ Pacific Ballroom #158
in Posters Mon »
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 non-submodular 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 $\varepsilon$-almost submodular). We first show a strong hardness result: there is no $1/n^{\gamma/c}$ approximation for influence maximization (unless P = NP) for all networks with up to $n^{\gamma}$ $\varepsilon$-almost submodular nodes, where $\gamma$ is in (0,1) and $c$ is a parameter depending on $\varepsilon$. This indicates that influence maximization is still hard to approximate even though threshold functions are close to submodular. We then provide $(1-\varepsilon)^{\ell}(1-1/e)$ approximation algorithms when the number of $\varepsilon$-almost submodular nodes is $\ell$. Finally, we conduct experiments on a number of real-world datasets, and the results demonstrate that our approximation algorithms outperform other baseline algorithms.
Keywords: Combinatorial Optimization · Submodular Optimization · Non-Convex Optimization · Hardness of Learning and Approximations
[ Paper] 

Author Information

Qiang Li (Institute of Computing Technol)
Wei Chen (Microsoft Research)
Institute of Computing Xiaoming Sun (Institute of Computing Technology, Chinese Academy of Sciences)
Institute of Computing Jialin Zhang (Institute of Computing Technology, Chinese Academy of Sciences)

More from the Same Authors