diff options
| -rw-r--r-- | paper/sections/intro.tex | 10 |
1 files changed, 7 insertions, 3 deletions
diff --git a/paper/sections/intro.tex b/paper/sections/intro.tex index 8e36a37..b84f562 100644 --- a/paper/sections/intro.tex +++ b/paper/sections/intro.tex @@ -22,9 +22,13 @@ an algorithm taking as input as set of observed cascades (realisations of the diffusion process) and recovers with high probability a large fraction of the graph edges. The goal is then to understand the relationship between the number of observations, the probability of success, and the accuracy of the -reconstruction. Prior work has shown that the typical required number of -observed cascades is $\O(poly(s)\log m)$, where $m$ is the number of nodes in -the graph, and $s$ is the maximum degree. +reconstruction. + +In most cases, the Graph Inference problem can be decomposed and analyzed +``node-by-node''. In this introduction, we will thus focus on a single node of +degree $s$ and discuss how to identify its parents among the $m$ nodes of the +graph. Prior work has shown that the typical required number of observed +cascades is $\O(poly(s)\log m)$. A more recent line of research has focused on applying advances on sparse inverse problems to the graph inference problem. Indeed, the graph can be |