diff options
Diffstat (limited to 'paper')
| -rw-r--r-- | paper/paper.tex | 1 | ||||
| -rw-r--r-- | paper/sections/experiments.tex | 19 | ||||
| -rw-r--r-- | paper/sparse.bib | 27 |
3 files changed, 47 insertions, 0 deletions
diff --git a/paper/paper.tex b/paper/paper.tex index 3110252..4a25484 100644 --- a/paper/paper.tex +++ b/paper/paper.tex @@ -102,6 +102,7 @@ \input{sections/model.tex} \section{Results} +\label{sec:results} \input{sections/results.tex} \section{A lower bound} diff --git a/paper/sections/experiments.tex b/paper/sections/experiments.tex index efcf754..4876927 100644 --- a/paper/sections/experiments.tex +++ b/paper/sections/experiments.tex @@ -8,6 +8,25 @@ \caption{Watts-Strogatz Model. 200 nodes, 20000 edges.} \end{figure} +In this section, we validate empirically the results and assumptions of Section~\ref{sec:results} for different initializations of parameters ($n$, $m$, $\lambda$) and for varying levels of sparsity. We compare our algorithm to two different state-of-the-art algorithms: \textsc{Greedy} and \textsc{MLE} from \cite{Netrapalli:2012}. We introduce an approximate \textsc{Lasso} algorithm and validate its effectiveness empirically. + +\paragraph{Experimental setup} + +We focus our analysis to synthetic graphs, which are known to exhibit the properties of real social networks. We therefore consider a Watts-Strogatz graph ($300$ nodes, $4500$ edges), a Barabasi-Albert graph ($300$ nodes, $16200$ edges), the Holme-Kim power law graph ($200$ nodes, $9772$ edges) \cite{Holme:2002}, and the recently introduced Kronecker graph ($256$ nodes, $10000$ edges) \cite{Leskovec:2010}. For every reported data point, we generate $n$ cascades from the Independent Cascade model for $n \in \{100, 500, 1000, 2000, 5000\}$, and compute the estimated graph $\hat {\cal G}$ for each algorithm. + +In the case of the \textsc{Lasso}, \textsc{MLE} and \textsc{Sparse MLE} algorithms, we construct the edges of $\hat {\cal G} : \cup_{j \in V} \{i : \Theta_{ij} > 0.1\}$. We report the F1-score$=2\frac{\text{precision}\cdot\text{recall}}{\text{precision}+\text{recall}}$. For each graph, the initial probability of a node being a source is fixed to $0.05$, i.e. an average of $15$ nodes source nodes per cascades. Except when testing for approximately sparse graphs, all edge weights are chosen uniformly in the interval $[0.2, 0.7]$. + +\paragraph{Comparison with other algorithms} +\begin{itemize} +\item Continuous time + single source -> no comparison with NETRATE... +\item This is a modeling decision: in practice, we do not have access to the cascade's ``patient 0'', which makes learning the graph harder. +\item Lasso +\end{itemize} + + +\paragraph{Quantifying robustness} + + \begin{itemize} \item Compare edge recovery to First Edge and Greedy as number of cascades grows on different types of graphs... diff --git a/paper/sparse.bib b/paper/sparse.bib index c05d318..48017cc 100644 --- a/paper/sparse.bib +++ b/paper/sparse.bib @@ -344,3 +344,30 @@ year = "2009" bibsource = {dblp computer science bibliography, http://dblp.org} } +@article{Leskovec:2010, + author = {Jure Leskovec and + Deepayan Chakrabarti and + Jon M. Kleinberg and + Christos Faloutsos and + Zoubin Ghahramani}, + title = {Kronecker Graphs: An Approach to Modeling Networks}, + journal = {Journal of Machine Learning Research}, + volume = {11}, + pages = {985--1042}, + year = {2010}, + url = {http://doi.acm.org/10.1145/1756006.1756039}, + doi = {10.1145/1756006.1756039}, + timestamp = {Thu, 22 Apr 2010 13:26:26 +0200}, + biburl = {http://dblp.uni-trier.de/rec/bib/journals/jmlr/LeskovecCKFG10}, + bibsource = {dblp computer science bibliography, http://dblp.org} +} + +@article{Holme:2002, + author= {Petter Holme and Beom Jun Kim}, + title = {Growing scale-free networks with tunable clustering}, + journal = {Physical review E}, + volume = {65}, + issue = {2}, + pages = {026--107}, + year = {2002} +} |