  We consider the *adaptive influence maximization problem*: given a network
and a budget $k$, iteratively select $k$ seeds in the network to maximize the
expected number of adopters. In the *full-adoption feedback model*, after
selecting each seed, the seed-picker observes all the resulting adoptions. In
the *myopic feedback model*, the seed-picker only observes whether each
neighbor of the chosen seed adopts. Motivated by the extreme success of
greedy-based algorithms/heuristics for influence maximization, we propose the
concept of *greedy adaptivity gap*, which compares the performance of the
adaptive greedy algorithm to its non-adaptive counterpart. Our first result
shows that, for submodular influence maximization, the adaptive greedy
algorithm can perform up to a $(1-1/e)$-fraction worse than the non-adaptive
greedy algorithm, and that this ratio is tight. More specifically, on one side
we provide examples where the performance of the adaptive greedy algorithm is
only a $(1-1/e)$ fraction of the performance of the non-adaptive greedy
algorithm in four settings: for both feedback models and both the *independent
cascade model* and the *linear threshold model*. On the other side, we prove
that in any submodular cascade, the adaptive greedy algorithm always outputs a
$(1-1/e)$-approximation to the expected number of adoptions in the optimal
non-adaptive seed choice. Our second result shows that, for the general
submodular diffusion model with full-adoption feedback, the adaptive greedy
algorithm can outperform the non-adaptive greedy algorithm by an unbounded
factor. Finally, we propose a risk-free variant of the adaptive greedy
algorithm that always performs no worse than the non-adaptive greedy algorithm.
