Description:

Title: New Perspectives on Learning Networks from Dynamics

Abstract: Suppose that a continuous-time, stochastic diffusion (e.g., an epidemic or cascade) spreads on an unknown graph. We only observe the times at which the diffusion reaches each vertex, i.e., the set of hitting times. What can be learned about the unknown graph from the hitting times? While there is far too little information to learn individual edges in the graph from a single diffusion, we show that certain high-level properties -- such as the number of vertices of sufficiently high degree -- can surprisingly be determined with high probability. To achieve this goal, we develop a suite of algorithms that can efficiently estimate the hitting time of vertices of degree asymptotically larger than $\sqrt{n}$, for a natural and general class of graphs. To complement these results, we show that our algorithms are information-theoretically optimal: there exist graphs for which it is impossible to tell whether vertices of degree larger than $n^{1/2 - \epsilon}$ exist from the vertices' hitting times. Finally, we discuss the broader implications of our ideas for change-point detection in non-stationary point processes. This talk is based on joint work with Anna Brandenberger and Elchanan Mossel.