Sparse Cut Projections in Graph Streams

Finding sparse cuts is an important tool for analyzing large graphs that arise in practice, such as the web graph, online social communities, and VLSI circuits. When dealing with such graphs having billions of nodes, it is often hard to visualize global partitions. While studies on sparse cuts have traditionally looked at cuts with respect to all the nodes in the graph, some recent works analyze graph properties projected onto a small subset of vertices that may be of interest in a given context, e.g., relevant documents to a query in a search engine. In this paper, we study how sparse cuts in a graph partition a certain subset of nodes. We call this partition a {\em cut projection}. We note that this projection is with respect to the whole graph.

A well developed framework for working with large graphs is the streaming model wherein the input is often too large to store in main memory and any algorithm is allowed to make few passes over the input stored on the disk. It is therefore important to design graph algorithms that adapt naturally to the streaming problem. In this paper, we present such an approach for finding cut projections of small conductance.

Specifically, for a $d$-regular graph $G$ of constant balance and $\Phi$ at least the conductance of $G$, we show how to partition a randomly chosen set of $k$ nodes in $\tilde{O}(\frac{1}{\sqrt{\alpha\Phi}})$ passes over the graph stream and space $\tilde{O}(n\alpha + \frac{n^{3/4}k^{1/4}}{\sqrt{\alpha}\Phi^{19/4}})$, for any choice of $\alpha\leq 1$. The resulting partition is the projection of a cut of conductance of at most $\tilde{O}(\sqrt{\Phi})$. We note that for $k < n\alpha^{6}\Phi^{O(1)}$, this can be done in $\tilde{O}(1/\sqrt{\alpha\Phi})$ passes and sub-linear space of $\tilde{O}(n\alpha)$.

In  17th Annual European Symposium on Algorithms (ESA)

Publisher  European Association for Theoretical Computer Science