Better bounds on the adaptivity gap of influence maximization under full-adoption feedback

In the influence maximization (IM) problem, we are given a social network and a budget k, and we look for a set of knodes 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 etal.[26]. However, most of the work focuses on the non-adaptiveversion of the problem where all the kseed nodes must be selected before the cascade starts. In this paper we study the adaptiveIM, where the nodes are selected sequentially one by one, and the decision on the i-th seed can be based on the observedcascade produced by the first i - 1seeds. We focus on the full-adoption feedbackin 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 workfor 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 (3)root n+ 1, where nis the number of nodes in the graph. Moreover, we improve over the known upper bound for in-arborescences from 2e/(e - 1) approximate to 3.16 to 2e(2)/(e(2) - 1) approximate to 2.31. Then, we consider (beta, gamma)-bounded-activation graphs, where all nodes but beta influence in expectation at most gamma is an element of[0, 1) neighbors each; for this class of influence graphs we show that the adaptivity gap is at most root beta+ 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 root 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 3e(3)/(e(3) - 1) approximate to 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. (c) 2023 Elsevier B.V. All rights reserved.