Abstract
We consider influence maximization (IM) in social networks, which is theproblem of maximizing the number of users that become aware of a product byselecting a set of "seed" users to expose the product to. While prior workassumes a known model of information diffusion, we propose a novelparametrization that not only makes our framework agnostic to the underlyingdiffusion model, but also statistically efficient to learn from data. We give acorresponding monotone, submodular surrogate function, and show that it is agood approximation to the original IM objective. We also consider the case of anew marketer looking to exploit an existing social network, whilesimultaneously learning the factors governing information propagation. Forthis, we propose a pairwise-influence semi-bandit feedback model and develop aLinUCB-based bandit algorithm. Our model-independent analysis shows that ourregret bound has a better (as compared to previous work) dependence on the sizeof the network. Experimental evaluation suggests that our framework is robustto the underlying diffusion model and can efficiently learn a near-optimalsolution.