Daniel J. DiTursi, Gaurav Ghosh, Petko Bogdanov

We propose a filter-and-verify framework for dynamic community detection. Toscale to long intervals of graph evolution, we employ novel spectral bounds fordynamic community conductance and employ them to filter suboptimal periods innear-linear time. We also design a time-and-graph-aware locality sensitivehashing family to effectively spot promising community cores. Our method PHASRdiscovers communities of consistently higher quality (2 to 67 times better)than those of baselines. At the same time, our bounds allow for pruning between$55\%$ and $95\%$ of the search space, resulting in significant savings inrunning time compared to exhaustive alternatives for even modest time intervalsof graph evolution.