External memory bisimulation reduction of big graphs

In this paper, we present, to our knowledge, the first known I/O efficient solutions for computing the k-bisimulation partition of a massive directed graph, and performing maintenance of such a partition upon updates to the underlying graph. Ubiquitous in the theory and application of graph data, bisimulation is a robust notion of node equivalence which intuitively groups together nodes in a graph which share fundamental structural features. k-bisimulation is the standard variant of bisimulation where the topological features of nodes are only considered within a local neighborhood of radius $kgeqslant 0$. The I/O cost of our partition construction algorithm is bounded by $O(kcdot mathit{sort}(|et|) + kcdot scan(| t|) + mathit{sort}(| t|))$, while our maintenance algorithms are bounded by $O(kcdot mathit{sort}(|et|) + kcdot mathit{sort}(| t|))$. The space complexity bounds are $O(| t|+|et|)$ and $O(kcdot| t|+kcdot|et|)$, resp. Here, $|et|$ and $| t|$ are the number of disk pages occupied by the input graphs edge set and node set, resp., and $mathit{sort}(n)$ and $mathit{scan}(n)$ are the cost of sorting and scanning, resp., a file occupying $n$ pages in external memory. Empirical analysis on a variety of massive real-world and synthetic graph datasets shows that our algorithms perform efficiently in practice, scaling gracefully as graphs grow in size.