diff options
| -rw-r--r-- | poster_abstract/main.tex | 59 |
1 files 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}
|