Lecture Notes in Computer Science, 2009, Volume 5427/2009, 62-75, DOI: 10.1007/978-3-540-95995-3_6

A Local Graph Partitioning Algorithm Using Heat Kernel Pagerank

Fan Chung

View Related Documents

Abstract

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 there are at least a quarter of the vertices in S that can serve as seeds for heat kernel pagerank which lead to local cuts with Cheeger ratio at most O(Öh)O(\sqrt{h}), improving the previously bound by a factor of Ö{log|S|}\sqrt{log|S|}.

Fulltext Preview

Image of the first page of the fulltext document