  Given a time-evolving network, how can we detect communities over periods of
high internal and low external interactions? To address this question we
generalize traditional local community detection in graphs to the setting of
dynamic networks. Adopting existing static-network approaches in an
"aggregated" graph of all temporal interactions is not appropriate for the
problem as dynamic communities may be short-lived and thus lost when mixing
interactions over long periods. Hence, dynamic community mining requires the
detection of both the community nodes and an optimal time interval in which
they are actively interacting.
  We propose a filter-and-verify framework for dynamic community detection. To
scale to long intervals of graph evolution, we employ novel spectral bounds for
dynamic community conductance and employ them to filter suboptimal periods in
near-linear time. We also design a time-and-graph-aware locality sensitive
hashing family to effectively spot promising community cores. Our method PHASR
discovers 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 in
running time compared to exhaustive alternatives for even modest time intervals
of graph evolution.
