diff options
Diffstat (limited to 'notes')
| -rw-r--r-- | notes/reportYaron.tex | 9 |
1 files changed, 5 insertions, 4 deletions
diff --git a/notes/reportYaron.tex b/notes/reportYaron.tex index a702db4..1ee0964 100644 --- a/notes/reportYaron.tex +++ b/notes/reportYaron.tex @@ -15,7 +15,7 @@ \section{Introduction} -Given a set of observed cascades, the \textbf{graph reconstruction problem} consists of finding the underlying graph on which these cascades spread. We explore different models for cascade creation, namely the {\bf voter model} and the \textbf{independent cascade model}. +Given a set of observed cascades, the graph reconstruction problem consists of finding the underlying graph on which these cascades spread. We explore different models for cascade creation, namely the voter model and the independent cascade model. Our objective is therefore to approximately compute the `inverse' of the cascade generation function from as few observations as possible. \section{Related Work} @@ -29,9 +29,9 @@ There have been several works tackling the graph reconstruction problem in varia \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 The authors make a 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}, 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. + \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 on other types of graphs. \end{itemize} \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} @@ -302,6 +302,7 @@ We were only able to test our algorithm in the case of the independent cascade m \section{Conclusion} +In conclusion, we described how a well-studied framework could be applied to the graph reconstruction problem. We give arguments as to why applying this framework could lead to better guarantees than pre-existing results. We also test our model in practice and show that it performs better than a simple heuristic, validating our approach to a certain extent. \begin{thebibliography}{42} @@ -320,7 +321,7 @@ Netrapalli, P., and Sanghavi, S., \bibitem{abrahao} Abrahao, B., Chierichetti, F., Kleinberg, R., and Panconesi, A. -\newblock{Trace Complexity of Network Inference} +\newblock{\it Trace Complexity of Network Inference} \newblock In Proc. 19th ACM SIGKDD international conference on Knowledge discovery and data mingin, KDD'13, pages 491--499, \newblock 2013 |