\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}