Adaptive Influence Maximization: Bounding Adaptivity Gaps and Beyond

The influence maximization (IM) problem is a discrete optimization problem [Kempe et al. [1]] of selecting the k most influential nodes in a network, and has ample applications ranging from viral marketing to outbreak detection. The IM problem is as follows: given a budget k and a graph G, our goal is to find a seed set S consisting of k nodes of G which maximizes the expected number of nodes influenced by S, according to some model of influence diffusion. The classic IM problem, which is also referred to as the non-adaptive IM, selects the seed set S before starting the diffusion process. Therefore, the focus is on the efficiency of the solution. A few years later, Golovin and Krause [2] introduced the adaptive IM (AIM) to target the efficacy of the problem. In the adaptive setting, selection of the k seed nodes occurs one at a time, such that the j-th seed node is selected after observing the actual influence from the previously selected j − 1 seeds. There are two main feedback models that have been studied: full-adoption, where the entire diffusion carried out by a seed node in the previous step is observed, and myopic, where only the neighbours of the previously selected seed nodes are considered as a feedback. While adaptive policies are strictly stronger than non-adaptive ones, the latter are much easier to design and implement. Golovin and Krause [2] proposed a measure called the adaptivity gap (AG), which is the ratio between the adaptive and non-adaptive optima. If the AG is small, we say that the non-adaptive policy provides a good approximation of the adaptive optimum. In this thesis, we study AG with both feedback models. Under the full adoption feedback, we investigate the upper bound of AG over several graph classes, from in-arborescences to general graphs. We show the first sub-linear upper bound on AG that holds for any graph. Next, we have the experimental part, where we take different network mod- els, such as random, scale-free and real world networks, and draw several comparisons between the adaptive greedy and the non-adaptive greedy algorithms under various net- work settings and parameters. Eventually, we move on to the myopic feedback model, which lacks the property of submodularity. To recover from the drawbacks of being non-submodular, an artificial diffusion process is taken into account. We introduce a new technique to bound the AG without using the commonly used approaches, such as multi-linear extensions or random walks. We also study the adaptive greedy algorithm under the new setting and compare it to optimal adaptive policy. Our approach is of independent interest and can be used for further studies related to different adaptive optimization problems.