#### Theory Seminar

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

Add to Google Calendar

/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.