Distributed Computation of Sparse Cuts via Random Walks
Atish Das Sarma, Anisur Rahaman Molla, Gopal Pandurangan · 2015
A sparse cut of a graph is a partition of the vertices into two disjoint subsets such that the ratio of the number of edges across the two subsets divided by the sum of degrees of vertices in the smaller side is minimum. Finding sparse cuts is an important tool in analyzing large-scale distributed networks such as the Internet and Peer-to-Peer networks, as well as large-scale graphs such as the web graph, online social communities, and VLSI circuits. Sparse cuts are useful in graph clustering and partitioning among numerous other applications. In distributed communication networks, they are useful for topology maintenance and for designing better search and routing algorithms.