Ani Sridhar (NJIT): Detecting super-spreaders in network cascades

Suppose that a continuous-time, stochastic diffusion (i.e., the Susceptible-Infected process) spreads on an unknown graph. We only observe the time at which the diffusion reaches each vertex, i.e., the set of infection times. What can be learned about the unknown graph from the infection times? While there is far too little information to learn individual edges in the graph, we show that certain high-level properties — such as the number of vertices of sufficiently high degree, or super-spreaders — can surprisingly be determined with certainty. To achieve this goal, we develop a suite of algorithms that can efficiently detect vertices of degree asymptotically greater than $\sqrt{n}$ from infection times, for a natural and general class of graphs with n vertices. 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 vertices' infection times, for any $\epsilon > 0$. 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 (MIT) and Elchanan Mossel (MIT).