Edge conductance estimation using MCMC

Abstract

We propose an iterative and distributed Markov Chain Monte Carlo scheme for estimation of effective edge conductances in a graph. A sample complexity analysis is provided. The theoretical guarantees on the performance of the proposed algorithm are weak compared to those of existing algorithms. But numerical experiments suggest that the algorithm might still be effective while offering the advantages of low per iterate computation and memory requirements.