diff options
Diffstat (limited to 'poster_abstract')
| -rw-r--r-- | poster_abstract/main.tex | 11 |
1 files changed, 5 insertions, 6 deletions
diff --git a/poster_abstract/main.tex b/poster_abstract/main.tex index 41c074f..e892c37 100644 --- a/poster_abstract/main.tex +++ b/poster_abstract/main.tex @@ -81,11 +81,11 @@ we validate our approach empirically on synthetic graphs. A recent line of research has focused on the Graph Inference Problem:
recovering the directed edges of an unknown graph from the observations of a diffusion process propagating on this graph \cite{Abrahao:13, Daneshmand:2014,Netrapalli:2012}. For example, the Independent
-Cascade Model, formalised in \cite{Kempe:03}, is a famous diffusion process where each ``infected'' node has a weighted probability to ``infect'' its neighbors in the graph. If we are only able to observe the time step at which nodes are infected over several diffusion processes, can we recover the edges and the edge weights, of the graph?
+Cascade Model, formalised in \cite{Kempe:03}, is a famous diffusion process where each ``infected'' node has a weighted probability to ``infect'' its neighbors in the graph. If we are only able to observe the time step at which nodes are infected over several diffusion processes, can we recover the edges and the edge weights of the graph?
Here, we propose a sparse recovery framework to not only solve the Graph
Inference Problem, but also recover the unknown weights of the diffusion
-process. Recall that for every instance of the diffusion process, the only thing known to the observer are
+process, for a large class of discrete time diffusion processes. Recall that for every instance of the diffusion process, the only thing known to the observer are
the time steps at which the vertices in the graph become “infected” by the
diffusion process. The parallel with sparse recovery problems is as follows: for a given
vertex, the (unknown) “influence” of its
@@ -104,8 +104,7 @@ comparing its performance to prior algorithms on synthetic data. % the number of vertices in the graph and $n$ is the number of observations. In
% particular, given $\Omega(s\log m)$ measurements, we are able to recover the
% edges of the graph.
-
-
+\vspace{-.2cm}
\section{Model}
\begin{figure}
@@ -156,8 +155,8 @@ Defining $\Theta_{i,j} \defeq \log(1-p_{i,j})$, this can be rewritten as: Therefore, the independent cascade model fits into the previous framework with $f : z \mapsto 1 - e^z$. \newline
\noindent {\bf Voter Model} Here, nodes can be either \emph{red} or \emph{blue}. Each round, every node $j$ independently chooses
-one of its neighbors with probability $\Theta_{i,j}$ and adopts their color. Without loss of generality, we can suppose that the
-\emph{blue} nodes are contagious.
+one of its neighbors with probability $\Theta_{i,j}$ and adopts their color. Without loss of generality, we can suppose that being
+\emph{blue} is the contagious state.
The
cascades stops at a fixed horizon time $T$ or if all nodes are of the same color.
If we denote by $X^t$ the indicator variable of the set of blue nodes at time
|