diff options
| -rw-r--r-- | notes/reportYaron.tex | 13 |
1 files changed, 10 insertions, 3 deletions
diff --git a/notes/reportYaron.tex b/notes/reportYaron.tex index 1ee0964..bbde9dc 100644 --- a/notes/reportYaron.tex +++ b/notes/reportYaron.tex @@ -241,7 +241,7 @@ If the number of rows $l$ of our matrix $M$ verifies $l \geq C \mu s \log n$ (wh \label{eq:first_guarantee} \| \hat x - x^* \|_2 \leq C (1 + \log^{3/2}n)\left[\frac{\|x^* - \tilde x\|_1}{\sqrt{s}} + \sigma \sqrt{\frac{s\log n}{l}}\right] \end{equation} -where $\sigma$ is a constant dependent on the variance of $\epsilon$, and $\tilde x$ is the best s-sparse approximation to the ground truth $x^*$. In other words if node $i$ is of degree at most $s$, then $\|x^* - \tilde x\|_1 = 0$ since $x^*$ is $s-sparse$. +where $\sigma$ is a constant dependent on the variance of $\epsilon$, and $\tilde x$ is the best s-sparse approximation to the ground truth $x^*$. In other words if node $i$ is of degree at most $s$, then $\|x^* - \tilde x\|_1 = 0$ since $x^*$ is $s-sparse$.\footnote{The result in the paper supposes that $x_i^*$ is $s$-sparse, i.e. that node $i$ has at most $s$ neighbors.} \end{theorem} \paragraph{Discussion} @@ -292,12 +292,19 @@ $\delta_4 = .54$ & $\delta_4 = .37$ & $\delta_4 = .43$ & $\delta_4 = .23$ \\ \paragraph{Discussion} Note how choosing the minimum of Eq~\ref{eq:lower_bound} over all extracted matrices returns the lowest possible $1 - \delta^-_k$ and choosing the maximum of Eq~\ref{eq:upper_bound} over all extracted matrices returns the highest possible $1 + \delta^+_k$. The smallest admissible $k-$RIP constant is therefore: $\max(\delta^+_k, \delta^-_k)$. Equations \ref{eq:lower_bound} and \ref{eq:upper_bound} can be solved efficiently since they correspond to the smallest and greatest eigenvalues of $M^TM$ respectively. -The results of our findings on a very small social network (a subset of the famous Karate club), show that as the number of cascades increase the RIP constants decrease and that if $p_\text{init}$ is small then the RIP constant decrease as well. Finally the constants we obtain are either under or close to the $.25$ mark set by the authors of \cite{candes}. +The results of our findings on a very small social network (a subset of the famous Karate club), show that as the number of cascades increase the RIP constants decrease and that if $p_\text{init}$ is small then the RIP constant decrease as well. Finally the constants we obtain are either under or close to the $.25$ mark set by the authors of \cite{candes}. By choosing appropriate parameters (number of cascades large enough, and $p_\text{init}$ small enough), we can place ourselves in the framework of this theorem for nodes of degree $4$ in a dataset of size 22. \subsection{Testing our algorithm} -We were only able to test our algorithm in the case of the independent cascade model and compare it to the \textsc{greedy} baseline suggested in \cite{netrapalli}. We picked a small subset of 333 nodes and 5039 edges from the Facebook graph, made available by \cite{snap}. As we can see from Figure TODO!!!!!!, our algorithm outperforms considerably the \textsc{greedy} baseline. Of things to take into consideration are the fact that the graph is very small, that the \textsc{greedy} algorithm has no guarantee for non-tree networks\footnote{Their authors do mention that it performs well in practice on non-tree networks as well}, and that \textsc{greedy} is a very simple heuristic. To get an accurate picture of our algorithm's contribution, it would be necessary to compare it to every other algorithm suggested in \cite{netrapalli} and \cite{abrahao}. +\begin{figure} +\centering +\label{fig:comparison-with-greedy} +\includegraphics[scale=.35]{images/greedy_sparse_comparison.pdf} +\caption{Plot of the F1 score for different number of cascades for both the \textsc{greedy} algorithm and Algorithm~\ref{eq:optimization_program}. The cascades, graphs, and edge probabilities were identical for both algorithms. The dataset is a subset of 333 nodes and 5039 edges taken from the Facebook graph, made available by \cite{snap}. We chose $p_\text{init}=.05$, and the edge probability were chosen uniformly between $0$ and $0.8$. For Algorithm~\ref{eq:optimization_program}, we chose $\lambda=10$ and kept all edges with probability greater than $.1$ as true edges.} +\end{figure} + +We were only able to test our algorithm in the case of the independent cascade model and compare it to the \textsc{greedy} baseline suggested in \cite{netrapalli}. We picked a small subset of 333 nodes and 5039 edges from the Facebook graph, made available by \cite{snap}. As we can see from Figure~\ref{fig:comparison-with-greedy}, our algorithm outperforms considerably the \textsc{greedy} baseline. Of things to take into consideration are the fact that the graph is very small, that the \textsc{greedy} algorithm has no guarantee for non-tree networks\footnote{Their authors do mention that it performs well in practice on non-tree networks as well}, and that \textsc{greedy} is a very simple heuristic. To get an accurate picture of our algorithm's contribution, it would be necessary to compare it to every other algorithm suggested in \cite{netrapalli} and \cite{abrahao}. \section{Conclusion} |