end of related works

1 files changed, 15 insertions, 7 deletions

diff --git a/notes/reportYaron.tex b/notes/reportYaron.tex
index be356d2..a702db4 100644
--- a/notes/reportYaron.tex
+++ b/notes/reportYaron.tex
@@ -27,16 +27,16 @@ There have been several works tackling the graph reconstruction problem in varia
   \begin{itemize}
   \item The first algorithm they discuss is a convex and parallelizable optimization problem. However, the theoretical guarantee is close to perfect reconstruction of `strong' edges after ${\cal O}(d^2 \log n)$ with high probability. There are several problems to this result however.
   \begin{itemize}
-  \item Researchers believe the true threshold of cascades necessary is closer to ${\cal O}(d \log n)$
-  \item The constant in the big ${\cal O}$ is highly polynomial in the different constants, of the order of billions even for very generous initializations of these parameters
-  \item The authors make a highly restrictive assumption on the probabilities of each edge, which they call `correlation decay': $\forall i, \sum_{j \in {\cal N}(i)} p_{j,i} < 1 -\alpha$, where $0 < \alpha < 1$
+    \item Researchers believe the true threshold of cascades necessary is closer to ${\cal O}(d \log n)$
+    \item The constant in the big ${\cal O}$ is highly polynomial in the different constants, of the order of billions even for very generous initializations of these parameters
+    \item The authors make a highly restrictive assumption on the probabilities of each edge, which they call `correlation decay': $\forall i, \sum_{j \in {\cal N}(i)} p_{j,i} < 1 -\alpha$, where $0 < \alpha < 1$
   \end{itemize}
-  \item The second algorithm, to which we will compare ourselves in Section~\ref{sec:exp}
+  \item The second algorithm, to which we will compare ourselves in Section~\ref{sec:exp}, is \textsc{Greedy}. It achieves perfect reconstruction after ${\cal O}(d \log n)$ observed cascades with high probability. However, this guarantee has been proven only in the case of tree-graphs. The authors mention that it does fairly well in pratice.
   \end{itemize}
-\item 
+\item Finally, a recent paper by Bruno Abrahao, Flavio Chierichetti, Robert Kleinberg, Alessandro Panconesi gives several algorithms and a different approach to showing their theoretical guarantees. Their strongest result is for bounded-degree graphs, where they show that they can obtain perfect reconstruction after observing ${\cal O}(\Delta^9 \log^2 \Delta \log n)$ algorithm. This is weaker than the first algorithm suggested by \cite{netrapalli}, but does not make the `correlation decay' assumption., where $\Delta$ is the max degree in graph ${\cal G}$.
 \end{itemize}
 
-
+What we aim for with the following framework is to achieve theoretical guarantees promising close-to-perfect reconstruction with observing ${\cal O}(\Delta \log n)$ cascades with high probability without relying on unreasonable assumptions like `correlation decay'. We also want our method to be easily implementable in practice and compare favorably to the above algorithms.
 
 \section{The Voter Model}
 
@@ -256,7 +256,6 @@ where $\sigma$ is a constant dependent on the variance of $\epsilon$, and $\tild
 \end{equation}
 
 In general, the smaller $\delta_k$ is, the better we can recover $k$-sparse vectors $x$. In the next section, we explore the $\delta$ constant of such a matrix, and show that in certain contexts it can be shown to be $\delta < \frac{1}{4}$.
-% \item Finally, though it is not yet clear which normalization to choose for the matrix $M$, it is to be noted that for our ultimate goal of support recovery, (i.e. detecting whether an edge exists rather), the literature seems to suggest that the precise normalization seems not to be important. Furthermore, normalizing the matrix by a constant does not modify our results (other than modifying the $\mu$ constant in Theorem~\ref{thm:candes}).
 \end{itemize}
 
 \section{Experiments}
@@ -298,6 +297,8 @@ The results of our findings on a very small social network (a subset of the famo
 
 \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}.
+
 
 \section{Conclusion}
 
@@ -334,6 +335,13 @@ Candès, E., and Plan, Y.
 \newblock {\it A Probabilistic and RIPless Theory of Compressed Sensing}
 \newblock Information Theory, IEEE Transactions on, 57(11): 7235--7254,
 \newblock 2011.
+
+\bibitem{snap}
+Leskovec, J., and Krevl, A.,
+\newblock {\it SNAP Datasets: Stanford Large Network Dataset Collection},
+\newblock 2014.
+
+
 \end{thebibliography}
 
 \end{document}
\ No newline at end of file