diff options
Diffstat (limited to 'notes')
| -rw-r--r-- | notes/econcs_presentation/extended_abstract.txt | 9 |
1 files changed, 6 insertions, 3 deletions
diff --git a/notes/econcs_presentation/extended_abstract.txt b/notes/econcs_presentation/extended_abstract.txt index 4a66381..47a12b9 100644 --- a/notes/econcs_presentation/extended_abstract.txt +++ b/notes/econcs_presentation/extended_abstract.txt @@ -1,7 +1,10 @@ -What: How can we estimate the parameters of a graph by observing its cascades? +Title: How can we estimate the parameters of a graph by observing its cascades? -For a long time, researchers have sought to understand how the parameters of a graph affect the spread of diffusion processes: can we predict cascades from these parameters? We consider the dual problem for a general class of diffusion processes: can we predict the graph's edges and weights from its cascades? If so, how many cascades are necessary? What is the rate of convergence? These questions are essential because they precede many other considerations of social network theory, such as how to maximize influence in a graph and conversely, how to limit the spread of influence. -In this talk, I present a framework for tackling the "graph inference" problem from cascades. This framework achieves a better convergence rate under weaker assumptions than prior work. We show that we (almost) match the lower bound and consider the robustness of our assumptions. Finally, the approach is validated on synthetic networks. +A standard problem in Social Network Theory is to understand how the parameters of a graph affect the properties of its cascades, which are diffusion processes that spread from node to node along the graph's weighted edges. In other words, can we predict cascades from the graph's parameters? + +Recent work has considered the dual problem: what knowledge about the existence of an edge in the graph do we gain by observing its cascades and how can we leverage that knowledge efficiently? A natural extension to this problem is: can we learn the weights of the graph's edges from cascades? These questions are fundamental to many aspects of social network theory: knowing the parameters of the graph precedes influence maximization or conversely influence minimization. + +In this talk, we present a "sparse recovery" framework for tackling the "graph inference" problem from cascades. This framework achieves a better convergence rate under weaker assumptions than prior work. We show that we (almost) match the lower bound and that our assumptions are robust to approximately sparse graphs. Finally, the approach is validated on synthetic networks. Joint work with Thibaut Horel
\ No newline at end of file |