We first consider the choice of k seeds in a social network to maximize the expected spread size under a submodular model of diffusion. Most of the previous work on this problem (known as influence maximization) focuses on efficient algorithms to approximate the optimal seed sets with provable guarantees, assuming the knowledge of the entire network graph. However, in practice, obtaining full knowledge of the network structure is very costly. To address this gap, we propose algorithms that make a bounded number of queries to the graph structure and still provide almost tight approximation guarantees [arXiv:1905.04325].
We next shift attention to interventions that change the network structure to increase the speed of spread. Unlike sub-modular diffusions, for threshold-based contagions, recent work has argued that highly clustered, rather than randomly rewired, networks facilitate faster spread. We investigate conditions under which we can reverse this conclusion by allowing a small probability of adoptions below threshold.