A Local Graph Partitioning Algorithm Using Heat Kernel Pagerank
Fan Chung · Internet Mathematics · 2009
We give an improved local partitioning algorithm using heat kernel pagerank, a modified version of PageRank. For a subset _S_ with Cheeger ratio (or conductance) _h_, we show that at least a quarter of the vertices in _S_ can serve as seeds for heat kernel pagerank that lead to local cuts with Cheeger ratio at most _O_(√_h_), improving the previous bound by a factor of √log _s_, where _s_ denotes the volume of _S_.