  We consider stochastic influence maximization problems arising in social
networks. In contrast to existing studies that involve greedy approximation
algorithms with a 63% performance guarantee, our work focuses on solving the
problem optimally. To this end, we introduce a new class of problems that we
refer to as two-stage stochastic submodular optimization models. We propose a
delayed constraint generation algorithm to find the optimal solution to this
class of problems with a finite number of samples. The influence maximization
problems of interest are special cases of this general problem class. We show
that the submodularity of the influence function can be exploited to develop
strong optimality cuts that are more effective than the standard optimality
cuts available in the literature. Finally, we report our computational
experiments with large-scale real-world datasets for two fundamental influence
maximization problems, independent cascade and linear threshold, and show that
our proposed algorithm outperforms the greedy algorithm.
