Local Algorithms for Estimating Effective Resistance
  Effective resistance is an important metric that measures the similarity of
two vertices in a graph. It has found applications in graph clustering,
recommendation systems and network reliability, among others. In spite of the
importance of the effective resistances, we still lack efficient algorithms to
exactly compute or approximate them on massive graphs.
  In this work, we design several \emph{local algorithms} for estimating
effective resistances, which are algorithms that only read a small portion of
the input while still having provable performance guarantees. To illustrate,
our main algorithm approximates the effective resistance between any vertex
pair $s,t$ with an arbitrarily small additive error $\varepsilon$ in time
$O(\mathrm{poly}(\log n/\varepsilon))$, whenever the underlying graph has
bounded mixing time. We perform an extensive empirical study on several
benchmark datasets, validating the performance of our algorithms.
