diff options
Diffstat (limited to 'paper/sections/intro.tex')
| -rw-r--r-- | paper/sections/intro.tex | 6 |
1 files changed, 3 insertions, 3 deletions
diff --git a/paper/sections/intro.tex b/paper/sections/intro.tex index 5507513..8e03394 100644 --- a/paper/sections/intro.tex +++ b/paper/sections/intro.tex @@ -1,8 +1,8 @@ -Many real-world phenomena can be modeled as complex diffusion processes on networks: from behavior adoption, sharing of internet memes, citations of articles, and the spread of infectious diseases. Oftentimes, the exact network is unknown to us: we observe only the behavior of the nodes through time, without knowledge of who `influenced' whom. The spread of a particular behavior through a network is known as an {\it Influence Cascade}. In this context, the {\it Graph Inference} problem is to recover the edges of the graph, and as we will argue, along with its weights, from the observation of few influence cascades. +Many real-world phenomena can be modeled as complex diffusion processes on networks: from behavior adoption, sharing of internet memes, citations of articles, and the spread of infectious diseases. Oftentimes, the exact network is unknown to us: we observe only the behavior of the nodes through time, without knowledge of who `influenced' whom. The spread of a particular behavior through a network is known as an {\it Influence Cascade}. In this context, the {\it Graph Inference} problem is to recover the edges of the graph from the observation of few influence cascades. -An effective algorithm recovers most of the edge links correctly from very few cascades. This problem is made all the more interesting by the fact that graph inference has shown to be possible, under various assumptions, in $\Omega(poly(\Delta) \log p)$ number of observed cascades, where $\Delta$ is the maximum degree of the graph and $p$ is the number of nodes. In other words, the dependence on $p$ is (almost miraculously) logarithmic. +In this context, an effective algorithm will recover a large majority of edges correctly from very few cascades. It has shown that the graph inference problem can be solved, under various assumptions, in $\Omega(poly(\Delta) \log p)$ number of observed cascades, where $\Delta$ is the maximum degree of the graph and $p$ is the number of nodes. In other words, the dependence of the number of cascades required to reconstruct the graph is (almost miraculously) logarithmic in the number of nodes of the graph. -Since the first few papers on link prediction in networks, the research community has made good progress in defining the {\it Graph Inference} problem more clearly and suggesting effective algorithms. However, not only can the known results be improved to $\Omega(\Delta \log p)$, but it can be shown that this is tight to a certain extent. Furthermore, not only can the support of the graph be recovered effectively, but it can be shown that the edge weights themselves can be estimated under the same assumptions, and that this is also tight to a certain extent. +Since the first few papers on link prediction in networks, the research community has made good progress in defining the Graph Inference problem more clearly and suggesting effective algorithms. However, not only can the known results be improved to $\Omega(\Delta \log p)$, but it can be shown that this is tight to a certain extent. Furthermore, not only can the support of the graph be recovered effectively, but it can be shown that the edge weights themselves can be estimated under the same assumptions, and that this is also tight to a certain extent. Throughout this paper, we focus on the two main diffusion processes, outlined by Kempe et al. (...) in their seminal work [cite]: the independent cascade model (IC) and the linear threshold model. More generally, we aim to cast the graph inference problem as a {\it generalized linear model} regression problem. |