Summary: In the influence maximization (IM) problem, we are given a social network and a budget \(k\), and we look for a set of \(k\) nodes in the network, called seeds, that maximize the expected number of nodes that are reached by an influence cascade generated by the seeds, according to some stochastic model for influence diffusion. Extensive studies have been done on the IM problem, since this definition by Kempe et al. [26]. However, most of the work focuses on the non-adaptive version of the problem where all the \(k\) seed nodes must be selected before the cascade starts. In this paper we study the adaptive IM, where the nodes are selected sequentially one by one, and the decision on the \(i\)-th seed can be based on the observed cascade produced by the first \(i - 1\) seeds. We focus on the full-adoption feedback in which we can observe the entire cascade of each previously selected seed under the independent cascade model where each edge is associated with an independent probability of diffusing influence.
Previous works showed that there are constant upper bounds on the adaptivity gap, which compares the performance of an adaptive algorithm against a non-adaptive one, but the analyses used to prove these bounds only work for specific graph classes such as in-arborescences, out-arborescences, and one-directional bipartite graphs. Our main result is the first sub-linear upper bound that holds for any graph. Specifically, we show that the adaptivity gap is upper-bounded by \(\sqrt[ 3]{ n} + 1\), where \(n\) is the number of nodes in the graph. Moreover, we improve over the known upper bound for in-arborescences from \(2 e /(e - 1) \approx 3.16\) to \(2 e^2 /(e^2 - 1) \approx 2.31\). Then, we consider \((\beta, \gamma)\)-bounded-activation graphs, where all nodes but \(\beta\) influence in expectation at most \(\gamma \in [0, 1)\) neighbors each; for this class of influence graphs we show that the adaptivity gap is at most \(\sqrt{ \beta} + \frac{ 1}{ 1 - \gamma}\). Finally, we study \(\alpha\)-bounded-degree graphs, that is the class of undirected graphs in which the sum of node degrees higher than two is at most \(\alpha\), and show that the adaptivity gap is upper-bounded by \(\sqrt{ \alpha} + O(1)\); we also show that in 0-bounded-degree graphs, i.e. undirected graphs in which each connected component is a path or a cycle, the adaptivity gap is at most \(3 e^3 /(e^3 - 1) \approx 3.16\).
To prove our bounds, we introduce new techniques to relate adaptive policies with non-adaptive ones that might be of their own interest.