Beyond Worst-Case (In)approximability of Nonsubmodular Influence Maximization

/p>

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.
The majority of existing work on this problem considers the case where the influence function is submodular,
in which case there is a known (1-1/e)-factor approximation algorithm.
However, in many cases, this assumption may not be realistic.
On the other hand, in the worst case, the problem is NP-hard to approximate to within of a factor of N^{1-\eps} where N
is the number of nodes in the network and $\eps > 0$ is any constant. A key open question is
whether this worst-case hardness result for nonsubmodular influence maximization can be
circumvented by making assumptions about either the underlying network topology or the cascade model.
We give several strong negative results and a complementary positive result to this question.

First, we present 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 the relationship between blocks admits a tree structure.
We show that the difficulty comes from the "back-and-forth' influence between agent-blocks, by
presenting a dynamic-program based polynomial time algorithm for the influence maximization problem when we additionally
assume the influence from one block to another is "one-way" .

Second, we present inapproximability results for a large variety of specific cascades.
For any local influence function f from a general family, which we call 2-submodular, we show inapproximability even if all
agents have local influence function f. This can be seen as a threshold result for
inapproximability of influence maximization, because if f is submodular,
then the problem can be approximated, but if f is just barely nonsubmodular
the problem can no longer be approximated to within a constant factor.