From 2b0c6dee9da471600a7b7127d9f55c7635458a99 Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Sun, 15 Mar 2015 22:47:40 -0400
Subject: Poster abstract model

---
 poster_abstract/main.tex | 59 ++++++++++++++++++++++++++++++++++++++++++++----
 1 file changed, 54 insertions(+), 5 deletions(-)

diff --git a/poster_abstract/main.tex b/poster_abstract/main.tex
index 5b9570b..e5688ff 100644
--- a/poster_abstract/main.tex
+++ b/poster_abstract/main.tex
@@ -14,6 +14,7 @@
 \newcommand{\ex}[1]{\E\left[#1\right]}
 \newcommand{\prob}[1]{\P\left[#1\right]}
 \newcommand{\inprod}[2]{#1 \cdot #2}
+\newcommand{\neigh}[1]{\mathcal{N}(#1)}
 \newcommand{\defeq}{\equiv}
 \DeclareMathOperator*{\argmax}{argmax}
 \DeclareMathOperator*{\argmin}{argmin}
@@ -76,13 +77,11 @@ approaches of information dissemination.
 \end{abstract}
 
 \category{H.2.8}{Database Management}{Database Applications}[Data Mining]
-\category{F.2.2}{Analysis of Algorithms and Problem Complexity}{Nonnumerical Algorithms and Problems}
-%\terms{Theory, Algorithms, Performance}
-%\keywords{Influence Maximization; Two-stage Optimization}
+\category{F.2.2}{Analysis of Algorithms and Problem Complexity}{Nonnumerical
+Algorithms and Problems}
 
 \section{Introduction}
 
-
 Influence Maximization~\cite{KKT03, DR01} is the algorithmic challenge of
 selecting a fixed number of individuals who can serve as early adopters of
 a new idea, product, or technology in a manner that will trigger a large
@@ -95,7 +94,7 @@ networks can lead to poor outcomes: due to the heavy-tailed degree
 distribution of social networks, high degree nodes are rare, and since
 influence maximization techniques often depend on the ability to select high
 degree nodes, a naive application of influence maximization techniques to the
-core set can become ineffective.
+core set is ineffective.
 
 \begin{figure}
     \centering
@@ -126,6 +125,7 @@ well-studied \emph{voter model}~\cite{holley1975ergodic}. We then use these
 algorithms to conduct a series of experiments to show the potential of adaptive
 approaches for influence maximization both on synthetic and real social
 networks.
+
 %The main component of the experiments involved collecting publicly
 %available data from Facebook on users who expressed interest (``liked'')
 %a certain post from a topic they follow and data on their friends.  The premise
@@ -133,6 +133,55 @@ networks.
 %campaign.  The results on these data sets suggest that adaptive seeding can
 %have dramatic improvements over standard influence maximization methods.
 
+\section{Framework}
+
+\noindent\textbf{Model.} Given a graph $G=(V,E)$, for $S\subseteq  V$ we denote by $\neigh{S}$ the
+neighborhood of $S$. The notion of influence in the graph is captured by
+a function $f:2^{|V|}\rightarrow \reals_+$ mapping a subset of nodes to
+a non-negative influence value. In this work, we focus on linear influence
+functions: $f(S) = \sum_{u\in S} w_u$ where $(w_u)_{u\in V}$ are non-negative
+weights capturing the influence of individual vertices. The input of the
+\emph{adaptive seeding} problem is a \emph{core set} of nodes $X\subseteq V$
+and for any node $u\in\neigh{X}$ a probability $p_u$ that $u$ realizes if one
+of its neighbor in $X$ is seeded. The goal is to solve the following problem:
+\begin{equation}\label{eq:problem}
+    \begin{split}
+        &\max_{S\subseteq X} \sum_{R\subseteq\neigh{S}} p_R
+        \max_{\substack{T\subseteq R\\|T|\leq k-|S|}}f(T)\\
+        &\text{s.t. }|S|\leq k
+    \end{split}
+\end{equation}
+where $p_R$ is the probability that the set $R$ realizes, $p_R \defeq
+\prod_{u\in R}p_u\prod_{u\in\neigh{S}\setminus R}(1-p_u)$. Intuitively, we want
+to select at most $k$ nodes in the core set $X$ such that the expected maximum
+influence which can be derived from the set $R$ of neighbors realizing using
+the remaining budget is maximal.\newline
+
+\noindent\textbf{Non-adaptive Optimization.} We say that a policy is
+\emph{non-adaptive} if it selects a set of nodes $S \subseteq X$ to be seeded
+in the first stage and a vector of probabilities $\mathbf{q}\in[0,1]^n$, such
+that each neighbor $u$ of $S$ which realizes is included in the solution
+independently with probability $q_u$.  The constraint will now be that the
+budget is only respected in expectation, \emph{i.e.}  $|S|
++ \textbf{p}^T\textbf{q} \leq k$. Formally the optimization problem for
+non-adaptive policies can be written as:
+\begin{equation}\label{eq:relaxed}
+    \begin{split}
+        \max_{\substack{S\subseteq X\\\textbf{q}\in[0,1]^n} }& \;
+    \sum_{R\subseteq\neigh{X}} \Big (\prod_{u\in R} p_uq_u\prod_{u\in\neigh{X}\setminus
+    R}(1-p_uq_u) \Big )
+ f(R)\\
+    \text{s.t. } & \; |S|+\textbf{p}^T\textbf{q} \leq k,\;
+q_u \leq \mathbf{1}\{u\in\neigh{S}\}
+\end{split}
+\end{equation}
+where $\mathbf{1}\{E\}$ is the indicator variable of the event $E$.
+Non-adaptive policies are related to adaptive policies:
+\begin{proposition}\label{prop:cr}
+    Let $(S,\textbf{q})$ be an $\alpha$-approximate solution to
+    \eqref{eq:relaxed}, then $S$ is an $\alpha$-approximate solution to
+    \eqref{eq:problem}.
+\end{proposition}  
 
 \bibliographystyle{abbrv}
 \bibliography{main}
-- 
cgit v1.2.3-70-g09d2