From 3fe3a6a17548af07d6a1e23e4ef53aa5ca48bc21 Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Sun, 1 Feb 2015 17:56:33 -0500
Subject: Intro: add precision about "single node recovery"

---
 paper/sections/intro.tex | 10 +++++++---
 1 file changed, 7 insertions(+), 3 deletions(-)

(limited to 'paper/sections/intro.tex')

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
-- 
cgit v1.2.3-70-g09d2

