From 4f7d4804234f5515a4dded8b05d9568653b7ae3c Mon Sep 17 00:00:00 2001 From: Thibaut Horel Date: Fri, 24 Oct 2014 12:32:08 -0400 Subject: Add paper --- paper/sections/related.tex | 9 +++++++++ 1 file changed, 9 insertions(+) create mode 100644 paper/sections/related.tex (limited to 'paper/sections/related.tex') diff --git a/paper/sections/related.tex b/paper/sections/related.tex new file mode 100644 index 0000000..b4200c1 --- /dev/null +++ b/paper/sections/related.tex @@ -0,0 +1,9 @@ +\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. -- cgit v1.2.3-70-g09d2