\subsection{Related work}
Influence maximization was introduced by Domingos and Richardson~\cite{DR01, RD02}, and later formulated by Kempe, Kleinberg and Tardos~\cite{KKT03, KKT05}, and has been extensively studied since.  Kempe, Kleinberg and Tardos~\cite{KKT03, KKT05} were able to cast this problem as a submodular optimization problem for many classes of influence models, hence allowing for algorithms with good approximations guarantees. Further refinements of the influence models and associated approximation guarantees can be found in \cite{MR07, C08}.  In~\cite{even-dar}, the authors look at the special case of the voter model and design efficient algorithms in this setting.

Our two-stage model for influence maximization is related to the field of stochastic optimization where problems are commonly solved using the \emph{sample average approximation} method \cite{SampleAverage}. In \cite{dean2004approximating, gupta2012approximation}, the authors use a notion of non-adaptive solutions related though not equivalent to ours.

%The problem we study is the same as in \cite{singer} but our goals are different. 
%Our main goal here is to obtain scalable algorithms that can be applied on the datasets we collected.

Other models of adaptive optimization have been previously studied in the context of influence maximization.  In \cite{asadpour2008stochastic}, the authors study a stochastic sequential submodular maximization problem where at each step an element is chosen, its realization is revealed and the next decision is made. Golovin and Krause \cite{golovin2011adaptive} study a similar model and apply it to a multi-stage influence maximization problem. We note that contrary to our model, the decision made at a given stage does not affect the following stages as the entire set of nodes is available as potential seeds at every stage.
