diff options
| -rw-r--r-- | notes/cracking_cascades_classposter.tex | 142 | ||||
| -rw-r--r-- | notes/reportYaron.tex | 73 |
2 files changed, 157 insertions, 58 deletions
diff --git a/notes/cracking_cascades_classposter.tex b/notes/cracking_cascades_classposter.tex index 52fd78d..9140e27 100644 --- a/notes/cracking_cascades_classposter.tex +++ b/notes/cracking_cascades_classposter.tex @@ -1,6 +1,6 @@ \documentclass[final]{beamer} \usepackage[utf8]{inputenc} -\usepackage[scale=1.41]{beamerposter} % Use the beamerposter package for laying out the poster +\usepackage[scale=1.6]{beamerposter} % Use the beamerposter package for laying out the poster \usetheme{confposter} % Use the confposter theme supplied with this template @@ -125,9 +125,8 @@ \vspace{0.5 cm} \begin{itemize} -\item Two types of nodes, {\color{red} red} and {\color{blue} blue}. -\item $\mathbb{P}$(node is {\color{blue} blue} at $t=0) = p_{\text{init}}$ -\item $\mathbb{P}$(node is {\color{blue} blue} at t+1) = $\frac{\text{Number of {\color{blue}blue} neighbors}}{\text{Total number of neighbors}}$ +\item $\mathbb{P}$({\color{blue} blue} at $t=0) = p_{\text{init}}$ +\item $\mathbb{P}$({\color{blue} blue} at $t+1) = \frac{\text{Number of {\color{blue}blue} neighbors}}{\text{Total number of neighbors}}$ \end{itemize} \vspace{0.5 cm} @@ -137,34 +136,40 @@ \vspace{0.5 cm} -To recover the neighbors of $v_1$: - -Observe which nodes are {\color{red} red} (1) or {\color{blue} blue} (0) in the two first iterations: +To recover the neighbors of $v_1$, observe which nodes are {\color{red} red} (1) or {\color{blue} blue} (0) at time step $t$: \begin{align*} -&v_2 \hspace{0.2 cm} v_3 \hspace{0.2 cm} v_4 \hspace{0.2 cm} v_5 \\ +&v_2 \hspace{0.2 cm} v_3 \hspace{0.2 cm} v_4 \hspace{0.2 cm} v_5 &\\ \vspace{1 cm} M = & \left( \begin{array}{cccc} 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \\ -\end{array} \right) +\end{array} \right) & \begin{array}{l} \hspace{ - 5cm} +\text{time step 0} \\ + \hspace{ - 5cm} \text{time step 1} \\ +\end{array} \end{align*} -and which color $v_1$ is in the two last iterations: +and which color $v_1$ is at time step $t+1$ due to $M$: \begin{align*} b_1 = & \left( \begin{array}{c} 1 \\ 1 \\ -\end{array} \right) +\end{array} \right) & \begin{array}{l} \hspace{ - 5cm} +\text{time step 1} \\ + \hspace{ - 5cm} \text{time step 2} \\ + \end{array} \end{align*} -If $(\vec x_{1})_j := \frac{\text{1}}{\text{deg}(i)} \cdot \left[\text{j parent of 1 in }{\cal G}\right] $, then our goal is to solve: +Then , \begin{equation} \boxed{M \vec x_1 = \vec b_1 + \epsilon \nonumber} \end{equation} -This problem is a {\bf Noisy Sparse Recovery} problem, which has been studied extensively. Here, the vectors $\vec x_i$ are deg(i)-sparse. +where $(\vec x_{1})_j := \frac{\text{1}}{\text{deg}(i)} \cdot \left[\text{j parent of 1 in }{\cal G}\right] $ + + \end{block} @@ -203,47 +208,62 @@ This problem is a {\bf Noisy Sparse Recovery} problem, which has been studied ex \includegraphics[width=0.6\textwidth]{icc.png} \end{figure} -{\bf Description} +\vspace{0.5 cm} +{\bf Description} +\vspace{0.5 cm} \begin{itemize} -\item Three possible states: susceptible {\color{blue} blue}, infected {\color{red} red}, inactive {\color{yellow} yellow} +\item Three possible states: {\color{blue} susceptible}, {\color{red} infected}, {\color{yellow} inactive } \item $\mathbb{P}$(infected at t=0)$=p_{\text{init}}$ \item Infected node $j$ infects its susceptible neighbors $i$ with probability $p_{j,i}$ independently \end{itemize} +\vspace{0.5 cm} {\bf Sparse Recovery Formulation} -To recover the neighbors of $v_5$: +\vspace{0.5 cm} -Observe which nodes are {\color{red} red} (1), {\color{blue} blue} (0), or yellow {\color{yellow} yellow} (0) in the two first iterations: +To recover the neighbors of $v_5$,observe which nodes are {\color{red} red} (1), {\color{blue} blue} (0), or {\color{yellow} yellow} (0) at time step $t$: \begin{align*} &v_1 \hspace{0.2 cm} v_2 \hspace{0.2 cm} v_3 \hspace{0.2 cm} v_4 \\ \vspace{1 cm} M = & \left( \begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ -\end{array} \right) +\end{array} \right) \begin{array}{l} \hspace{ 1cm} +\text{time step 0} \\ + \hspace{ 1cm} \text{time step 1} \\ + \end{array} \end{align*} -and if $v_5$ is infected in the two last iterations: +and if $M$ caused $v_5$ to be infected at time step $t+1$: \begin{align*} -b_1 = & \left( \begin{array}{c} +b_5 = & \left( \begin{array}{c} 0 \\ 1 \\ -\end{array} \right) +\end{array} \right) \begin{array}{l} \hspace{ 1cm} +\text{time step 1} \\ + \hspace{ 1cm} \text{time step 2} \\ + \end{array} \end{align*} -If $(\vec \theta_i)_j := \log ( 1 - p_{j,i}) $, then our goal is to solve: + +Then, \begin{equation} -\boxed{e^{M \vec \theta_i} = (1 - \vec b_i) + \epsilon} \nonumber +\boxed{e^{M \vec \theta_5} = (1 - \vec b_5) + \epsilon} \nonumber \end{equation} +where $(\vec \theta_5)_j := \log ( 1 - p_{j,5}) $ +\vspace{1 cm} + + +This problem is a {\bf Noisy Sparse Recovery} problem, which has been studied extensively. Here, the vectors $\vec x_i$ are deg(i)-sparse. \end{block} @@ -252,27 +272,7 @@ If $(\vec \theta_i)_j := \log ( 1 - p_{j,i}) $, then our goal is to solve: -\begin{block}{Algorithms} -{\bf Voter Model} - -\begin{itemize} -\item Solve for each node i: -\begin{equation} -\min_{\vec x_i} \|\vec x_i\|_1 + \lambda \|M \vec x_i - \vec b_i \|_2 \nonumber -\end{equation} -\end{itemize} - -{\bf Independent Cascade Model} - -\begin{itemize} -\item Solve for each node i: -\begin{equation} -\min_{\vec \theta_i} \|\vec \theta_i\|_1 + \lambda \|e^{M \vec \theta_i} - \vec b_i \|_2 \nonumber -\end{equation} -\end{itemize} - -\end{block} @@ -308,27 +308,42 @@ If $(\vec \theta_i)_j := \log ( 1 - p_{j,i}) $, then our goal is to solve: %---------------------------------------------------------------------------------------- +\begin{block}{Algorithms} + +{\bf Voter Model} + +\begin{itemize} +\item Solve for each node i: +\begin{equation} +\min_{\vec x_i} \|\vec x_i\|_1 + \lambda \|M \vec x_i - \vec b_i \|_2 \nonumber +\end{equation} +\end{itemize} + +{\bf Independent Cascade Model} + +\begin{itemize} +\item Solve for each node i: +\begin{equation} +\min_{\vec \theta_i} \|\vec \theta_i\|_1 + \lambda \|e^{M \vec \theta_i} - (1 - \vec b_i) \|_2 \nonumber +\end{equation} +\end{itemize} +\end{block} \begin{block}{Restricted Isometry Property (RIP)} {\bf Definition} \begin{itemize} -\item The Restricted Isometry Property (RIP) characterizes a quasi-orthonormality of the measurement matrix M on sparse vectors. +\item Characterizes a quasi-orthonormality of M on sparse vectors. -\item For all k, we define $\delta_k$ as the best possible constant such that for all unit-normed ($l$2) and k-sparse vectors $x$: +\item The RIP constant $\delta_k$ is the best possible constant such that for all unit-normed ($l$2) and k-sparse vectors $x$: \begin{equation} 1-\delta_k \leq \|Mx\|^2_2 \leq 1 + \delta_k \nonumber \end{equation} -\item In general, the smaller $\delta_k$ is, the better we can recover $k$-sparse vectors $x$! +\item The smaller $\delta_k$ is, the better we can recover $k$-sparse vectors $x$. \end{itemize} -{\bf Relevance} -\begin{itemize} -\item Commonly studied in stable sparse recovery -\item $\mathbb{E}_{a \in F}(a a^T) \approx I_n$ + RIP property (with $\delta = \frac{1}{4}$) should get similar conclusion as above -\end{itemize} @@ -336,13 +351,13 @@ If $(\vec \theta_i)_j := \log ( 1 - p_{j,i}) $, then our goal is to solve: \begin{block}{Theoretical Guarantees} -In the case of small RIP constants $(\delta \leq 0.25)$ for $M$ and some assumption on the noise $\epsilon$: +With small RIP constants $(\delta \leq 0.25)$ for $M$ and some assumption on the noise $\epsilon$: {\bf Theorem \cite{candes}} If node $i$ has degree $\Delta$ and $n_{\text{rows}}(M) \geq C_1 \mu \Delta \log n$, then, w.h.p., -$$\| \hat x - x^* \|_2 \leq C (1 + \log^{3/2}(n))\sqrt{\frac{\Delta \log n}{m}}$$ +$$\| \hat x - x^* \|_2 \leq C (1 + \log^{3/2}(n))\sqrt{\frac{\Delta \log n}{n_{\text{rows}}(M) }}$$ \end{block} @@ -354,14 +369,19 @@ $$\| \hat x - x^* \|_2 \leq C (1 + \log^{3/2}(n))\sqrt{\frac{\Delta \log n}{m}}$ % RESULTS %---------------------------------------------------------------------------------------- -\begin{block}{Description of Experiments} +\begin{block}{RIP Experiments} -\begin{tabular}{ c | c | c | c | c } -& c = 100, &c = 1000,&c = 100, &c = 1000,\\ -& i = 0.1&i = 0.1& i = 0.05& i = 0.05\\ +\begin{center} +\begin{table} +\begin{tabular}{c | c | c | c | c } +& $c$ = 100, &$c$ = 1000,& $c$ = 100, &$c$ = 1000,\\ +& $i$ = 0.1& $i$ = 0.1& $i$ = 0.05& $i$ = 0.05\\ \hline $\delta_4$ & 0.54 & 0.37 &0.43&0.23 \\ -\end{tabular} + \end{tabular} + \caption{RIP constant for a small graph. Here, $c$ is the number of cascades and $i$ is $p_{\text{init}}$.} +\end{table} +\end{center} \end{block} @@ -402,6 +422,12 @@ $$\| \hat x - x^* \|_2 \leq C (1 + \log^{3/2}(n))\sqrt{\frac{\Delta \log n}{m}}$ \begin{block}{Conclusion} +\begin{center} + + +{\bf Graph reconstruction can naturally be expressed as Sparse Recovery. Understanding properties of $M$, for example RIP, leads to theoretical guarantees on the reconstruction.} + +\end{center} \end{block} diff --git a/notes/reportYaron.tex b/notes/reportYaron.tex index d39d060..1dc0db1 100644 --- a/notes/reportYaron.tex +++ b/notes/reportYaron.tex @@ -84,6 +84,42 @@ If the vector $\vec x_i$ is sufficiently sparse, i.e. node $i$ has sufficiently \subsection{Example} + +\begin{figure} +\centering +\includegraphics[width=0.3\textwidth]{voter.png} +\caption{A cascade in the voter model with time steps $t = 0,1,2$ over a graph with 5 vertices} +\end{figure} + + + + +To recover the neighbors of $v_1$, we get the following matrix $M$ for the example in Figure 1: + +\begin{align*} +&\hspace{0.35cm} v_2 \hspace{0.2 cm} v_3 \hspace{0.2 cm} v_4 \hspace{0.2 cm} v_5 &\\ +\vspace{1 cm} +M = & \left( \begin{array}{cccc} +0 & 0 & 1 & 1 \\ +1 & 1 & 0 & 0 \\ +\end{array} \right) & \begin{array}{l} \hspace{ -4.5 cm} +\text{time step 0} \\ + \hspace{ - 4.5cm} \text{time step 1} \\ +\end{array} +\end{align*} + +and the vector $b_1$: + +\begin{align*} +b_1 = & \left( \begin{array}{c} +1 \\ +1 \\ +\end{array} \right) & \begin{array}{l} \hspace{ - 5cm} +\text{time step 1} \\ + \hspace{ - 5cm} \text{time step 2} \\ + \end{array} +\end{align*} + \section{The Independent Cascade Model} \subsection{Description} @@ -127,6 +163,43 @@ e^{M_i \vec \theta_i} = 1 - \vec b_i + \vec \epsilon_i Note that this is not exactly a sparse recovery model due to the non-linear exponential term. It is of the author's opinion however that if the probabilities $p_{j,i}$ are restrained to a bounded interval $[0, 1- \eta]$, then most of the results which hold for the linear voter model will continue to hold in this case. +\subsection{Example} + +\begin{figure} +\centering +\includegraphics[width=0.3\textwidth]{icc.png} +\caption{A cascade in the independent cascade model with time steps $t = 0,1,2$ over a graph with 5 vertices} +\end{figure} + + + +To recover the neighbors of $v_5$, we get the following matrix $M$ for the example in Figure 2: +\begin{align*} +&v_1 \hspace{0.2 cm} v_2 \hspace{0.2 cm} v_3 \hspace{0.2 cm} v_4 \\ +\vspace{1 cm} +M = & \left( \begin{array}{cccc} +1 & 0 & 0 & 0 \\ +0 & 1 & 1 & 0 \\ +\end{array} \right) \begin{array}{l} \hspace{ 1cm} +\text{time step 0} \\ + \hspace{ 1cm} \text{time step 1} \\ + \end{array} +\end{align*} + +and the vector $b_5$: + +\begin{align*} +b_5 = & \left( \begin{array}{c} +0 \\ +1 \\ +\end{array} \right) \begin{array}{l} \hspace{ 1cm} +\text{time step 1} \\ + \hspace{ 1cm} \text{time step 2} \\ + \end{array} +\end{align*} + + + \section{Sparse Recovery} \subsection{Introduction} |