Paper Info
Title
Beyond Worst-Case (In)approximability of Nonsubmodular Influence Maximization.
Abstract
We consider the problem of maximizing the spread of influence in a social network by choosing a fixed number of initial seeds, formally referred to as the influence maximization problem. It admits a (1−1/e)-factor approximation algorithm if the influence function is submodular. Otherwise, in the worst case, the problem is NP-hard to approximate to within a factor of N1−&varepsilon. This article studies whether this worst-case hardness result can be circumvented by making assumptions about either the underlying network topology or the cascade model. All our assumptions are motivated by many real-life social network cascades. First, we present strong inapproximability results for a very restricted class of networks called the (stochastic) hierarchical blockmodel, a special case of the well-studied (stochastic) blockmodel in which relationships between blocks admit a tree structure. We also provide a dynamic-programming-based polynomial time algorithm, which optimally computes a directed variant of the influence maximization problem on hierarchical blockmodel networks. Our algorithm indicates that the inapproximability result is due to the bidirectionality of influence between agent-blocks. Second, we present strong inapproximability results for a class of influence functions that are “almost” submodular, called 2-quasi-submodular. Our inapproximability results hold even for any 2-quasi-submodular f fixed in advance. This result also indicates that the “threshold” between submodularity and nonsubmodularity is sharp, regarding the approximability of influence maximization.
Year
DOI
Venue
2017
10.1145/3313904
WINE
Keywords
DocType
Volume
(non)submodular optimization, Influence maximization, approximability
Journal
abs/1710.02827
Issue
ISSN
Citations 
3
ACM Transactions on Computation Theory (April 2019)
0
PageRank 
References 
Authors
0.34
15
2
Name
Order
Citations
PageRank
Grant Schoenebeck150939.48
Biaoshuai Tao2264.69