1 files changed, 359 insertions, 0 deletions
diff --git a/slides/main.tex b/slides/main.tex
new file mode 100755
index 0000000..ed10070
--- /dev/null
+++ b/slides/main.tex
@@ -0,0 +1,359 @@
+\documentclass[10pt]{beamer}
+\usepackage[utf8x]{inputenc}
+\usepackage{amsmath,bbm,verbatim, amsthm}
+\usepackage{algpseudocode,algorithm,bbding}
+\usepackage{graphicx}
+\usepackage{booktabs}
+\usepackage{caption}
+\usepackage{subcaption}
+\DeclareMathOperator*{\argmax}{arg\,max}
+\DeclareMathOperator*{\argmin}{arg\,min}
+\newcommand{\E}{{\tt E}}
+
+\title[Harvard EconCS Seminar]{Scalable Methods for Adaptive Seeding\\
+in Social Networks}
+\author[Thibaut Horel]{Thibaut Horel \and Yaron Singer}
+
+%\setbeamercovered{transparent}
+\setbeamertemplate{navigation symbols}{}
+
+\newcommand{\ie}{\emph{i.e.}}
+\newcommand{\eg}{\emph{e.g.}}
+\newcommand{\etc}{\emph{etc.}}
+\newcommand{\etal}{\emph{et al.}}
+\newcommand{\reals}{\ensuremath{\mathbb{R}}}
+\AtBeginSection[]
+{
+\begin{frame}<beamer>
+\frametitle{Outline}
+\tableofcontents[currentsection]
+\end{frame}
+}
+
+\begin{document}
+
+\maketitle
+
+\begin{frame}{}
+
+    \begin{center}
+        \begin{large}
+            How to leverage social networks to
+            
+            \vspace{1em}
+            
+            spread information effectively?
+    \end{large}
+    \end{center}
+
+\end{frame} 
+
+\begin{frame}{Influence Maximization}
+    \begin{center}
+        \includegraphics<1>[width=0.8\textwidth]{graph.pdf}
+        \includegraphics<2>[width=0.8\textwidth]{graph2.pdf}
+        \includegraphics<3->[width=0.8\textwidth]{graph3.pdf}
+\end{center}
+    \begin{center}
+        Which nodes to actively seed to maximize your influence? \only<4>{[KKT03]}
+    \end{center}
+\end{frame}
+
+\begin{frame}{Why it doesn't work}
+    \begin{itemize}
+        \item You cannot seed anyone in the network
+        \item Influential users are rare
+    \end{itemize}
+    \vspace{1em}
+    \begin{center}
+        \includegraphics<1>[width=0.7\textwidth]{graph.pdf}
+        \includegraphics<2>[width=0.7\textwidth]{graph4.pdf}
+        \includegraphics<3>[width=0.7\textwidth]{graph5.pdf}
+        \includegraphics<4>[width=0.7\textwidth]{graph6.pdf}
+    \end{center}
+\end{frame}
+
+\begin{frame}{Friendship Paradox}
+    \begin{center}
+        \begin{large}
+            ``Your friends have more friends than you do.'' 
+\end{large}
+\end{center}
+                \vspace{1em}
+                \only<2->{
+                \begin{overprint}
+        \onslide<2>
+    \begin{center}
+        \includegraphics[width=0.7\textwidth]{graph4.pdf}
+    \end{center}
+        \onslide<3>
+    \begin{center}
+        \includegraphics[width=0.9\textwidth]{dist.pdf}
+    \end{center}
+\end{overprint}}
+\end{frame}
+
+\begin{frame}{Adaptive Seeding}
+    \begin{itemize}
+        \item Two-stage process
+        \item Reach influential nodes through their friends
+    \end{itemize}
+    \vspace{1em}
+    \begin{center}
+        \includegraphics<1>[width=0.7\textwidth]{graph4.pdf}
+        \includegraphics<2>[width=0.7\textwidth]{graph7.pdf}
+        \includegraphics<3>[width=0.7\textwidth]{graph8.pdf}
+        \includegraphics<4>[width=0.7\textwidth]{graph9.pdf}
+        \includegraphics<5>[width=0.7\textwidth]{graph10.pdf}
+    \end{center}
+    \alert{Question:} Which nodes to select in the first stage? [SS13]
+\end{frame}
+
+\begin{frame}{Outline}
+\tableofcontents
+\end{frame}
+
+\section{Adaptive Seeding}
+
+\begin{frame}{Model}
+    Influence maximization:
+\begin{itemize}
+    \item graph $(V,E)$
+    \item influence function $f:2^V\rightarrow\mathbb{R}_+$
+    \item budget $k$
+\end{itemize}
+\vspace{1em}
+\pause
+Plus:
+\begin{itemize}
+    \item core set $X$
+    \item for $u\in N(X)$, probability $p_u$ of becoming seedable 
+\end{itemize}
+\end{frame}
+
+\begin{frame}{Adaptive Seeding}
+\begin{itemize}
+    \item \textbf{First stage:} select $S\subseteq X$ ($|S|\leq k$)
+        \vspace{1em}
+        \pause
+    \item each node $u\in N(S)$ becomes seedable w.p $p_u$
+        \\$\Rightarrow$ $R\subseteq N(S)$ subset of seedable nodes
+        \vspace{1em}
+        \pause
+    \item \textbf{Second stage:} maximize $f$ over $R$ with remaining budget ($k-|S|$)
+\end{itemize}
+\end{frame}
+
+\begin{frame}{Problem}
+    \begin{itemize}
+        \item \textbf{First stage:} select $S\subseteq X$ ($|S|\leq k$)
+        \vspace{1em}
+        \pause
+        \item $p_R$ probability that $R\subseteq N(S)$ becomes seedable:
+        \vspace{1em}
+        \pause
+        \item expected value when selecting $S$ ($|S|\leq k$):
+            \begin{displaymath}
+                F(S) = \sum_{R\subseteq N(S)} p_R\; \max_{\substack{T\subseteq R\\ |T|\leq k-|S|}} f(T)
+            \end{displaymath}
+    \end{itemize}
+    \vspace{2em}
+    \alert{Problem:} Compute $F^* \in \argmax_{|S|\leq k} F(S)$
+\end{frame}
+
+\begin{frame}{Problem}
+            \begin{displaymath}
+                F(S) = \sum_{R\subseteq N(S)} p_R\; \max_{\substack{T\subseteq R\\ |T|\leq k-|S|}} f(T)
+            \end{displaymath}
+
+    \vspace{1cm}
+
+    \alert{Problem:} Compute $F^* \in \argmax_{|S|\leq k} F(S)$
+
+    \vspace{1cm}
+
+    Even when the probabilities are all one:
+    \begin{itemize}
+        \item NP-hard problem
+        \item not submodular
+        \item computing $F(S)$ takes exponential time
+    \end{itemize}
+\vspace{1em}
+
+\pause
+However, $(1-1/e)^2$-approx. algorithm [SS13,\ldots]
+\pause
+\vspace{1em}
+
+But\ldots{} running time $O(n^\alpha)$, $\alpha \geq 10$.
+\end{frame}
+
+\begin{frame}{Non-adaptive relaxation}
+\begin{itemize}
+    \item commit in the first stage on the nodes to seed in the second stage
+    \item randomize
+\end{itemize}
+\vspace{1em}
+\pause
+
+A non-adaptive solution is a pair $(S, q)$
+\begin{itemize}
+    \item $S$: nodes selected in the first stage
+    \item $q$: if node $u\in N(S)$ realizes, select it w.p $q_u$
+\end{itemize}
+\vspace{1em}
+\pause
+
+Within budget in expectation:
+\begin{displaymath}
+    |S| + \sum_{u\in N(S)} p_u q_u\leq k
+\end{displaymath}
+\end{frame}
+
+\begin{frame}{Non-adaptive problem}
+\begin{displaymath}
+    \begin{split}
+        \max_{(S,q)}& \sum_{R\subseteq N(S)} (p\cdot q)_R \;f(R)\\
+        \text{s.t.}&\; |S| + \sum_{u\in N(S)} p_uq_u \leq k
+\end{split}
+\end{displaymath}
+\pause
+\vspace{1cm}
+
+Non-adaptive problem:
+\begin{itemize}
+    \item $(1-1/e)$ approx. to the adaptive problem
+    \item can be solved with approximation $(1-1/e)$
+        \pause
+    \item how to construct adaptive solution from non-adaptive solution?
+        \begin{displaymath}
+            (S,q) \mapsto S
+        \end{displaymath}
+\end{itemize}
+\end{frame}
+
+\begin{frame}{Non-adaptive relaxation}
+    \begin{center}
+        \includegraphics[height=0.5\textheight]{diag.pdf}
+    \end{center}
+\end{frame}
+
+\section{Additive Adaptive Seeding}
+
+\begin{frame}{Additive influence functions}
+
+From now on:
+\begin{displaymath}
+    f(S) = \sum_{u\in S} w_u
+\end{displaymath}
+
+\vspace{1cm}
+$w_u$ is the weight of node $u$:
+\begin{itemize}
+    \item $w_u = \text{deg}(u)$
+    \item $w_u$, influence of $u$ in the voter model
+    \item $w_u$ comes from an external source (e.g. Klout)
+\end{itemize}
+\end{frame}
+
+\begin{frame}{Results}
+    \begin{center}
+        \includegraphics<1>[height=0.5\textheight]{diag.pdf}
+        \includegraphics<2>[height=0.5\textheight]{diag2.pdf}
+    \end{center}
+\end{frame}
+
+\begin{frame}{Non-adaptive Problem (bis)}
+    \only<1>{
+\begin{displaymath}
+    \begin{split}
+        \max_{(S,q)}& \sum_{R\subseteq N(S)} (p\cdot q)_R \;f(R)\\
+        \text{s.t.}&\; |S| + \sum_{u\in N(S)} p_uq_u \leq k
+\end{split}
+}
+
+    \only<2->{
+\begin{displaymath}
+    \begin{split}
+        \max_{(S,q)}& \sum_{u\in N(S)} p_uq_uw_u\\
+        \text{s.t.}&\; |S| + \sum_{u\in N(S)} p_uq_u \leq k
+\end{split}
+}
+\end{displaymath}
+
+\pause
+
+\pause
+\vspace{1em}
+Two algorithms
+\begin{itemize}
+    \item submodular maximization: $\max_q \sum_{u\in N(S)} p_uq_uw_u$ is submodular
+    \item LP relaxation
+\end{itemize}
+
+\pause
+\vspace{1em}
+Running time: $O(k^2 n^2)$.
+\end{frame}
+
+
+\section{Experimental Results}
+
+\begin{frame}{Data Collection}
+
+\begin{table}[t]
+    \centering
+    \setlength{\tabcolsep}{3pt}
+    \begin{tabular}{llrr}
+    \toprule
+    Vertical & Page & $m$ & $n$ \\%& $S$ & $F$\\
+    \midrule
+    Charity & Kiva & 978 & 131334 \\%& 134.29 & 1036.26\\
+    Travel & Lonely Planet & 753 & 113250 \\%& 150.40 & 898.50\\
+    %Public Action & LaManifPourTous & 1041 & 97959 \\%& 94.10 & 722.02\\
+    Fashion & GAP & 996 & 115524 \\%& 115.99 & 681.98\\
+    Events & Coachella & 826 & 102291 \\%& 123.84 & 870.16\\
+    Politics & Green Party & 1044 & 83490 \\%& 79.97 & 1053.25\\
+    Technology & Google Nexus & 895 & 137995 \\%& 154.19 & 827.84\\
+    News & The New York Times & 894 & 156222 \\%& 174.74 & 1033.94 \\
+    %Consumption & Peet's & 776 & 56268 \\%& 72.51 & 520.47\\
+    Entertainment & HBO & 828 & 108699 \\%& 131.28 & 924.09\\
+    \bottomrule
+\end{tabular}
+\end{table}
+\end{frame}
+
+\begin{frame}{Friendship paradox (bis)}
+    \begin{center}
+        \includegraphics[width=0.8\textwidth]{para.pdf}
+    \end{center}
+\end{frame}
+
+\begin{frame}{Performance}
+    \begin{center}
+        \includegraphics[height=0.8\textheight]{perf10.pdf}
+    \end{center}
+\end{frame}
+
+\begin{frame}{Performance (bis)}
+\begin{figure}[t]
+    \begin{subfigure}[t]{0.48\textwidth}
+    \includegraphics[width=\textwidth]{prob.pdf}
+    \caption{}
+\end{subfigure}
+\hspace{1pt}
+\begin{subfigure}[t]{0.48\textwidth}
+    \includegraphics[width=\textwidth]{hbo_likes.pdf}
+    \caption{}
+     \end{subfigure}
+\end{figure}
+\end{frame}
+
+\begin{frame}{Running time}
+    \begin{center}
+        \includegraphics[width=\textwidth]{sampling2.pdf}
+    \end{center}
+
+\end{frame}
+
+\end{document}