Regularities and dynamics in bisimulation reductions of big graphs

Bisimulation is a basic graph reduction operation, which plays a key role in a wide range of graph analytical applications. While there are many algorithms dedicated to computing bisimulation results, to our knowledge, little work has been done to analyze the results themselves. Since data properties such as skew can greatly influence the performances of data-intensive tasks, the lack of such insight leads to inefficient algorithm and system design. In this paper we take a close look into various aspects of bisimulation results on big graphs, from both real-world scenarios and synthetic graph generators, with graph size varying from 1 million to 1 billion edges. We make the following observations: (1) A certain degree of regularity exists in real-world graphs' bisimulation results. Specifically, power-law distributions appear in many of the results' properties. (2) Synthetic graphs fail to fulfill one or more of these regularities that are revealed in the real-world graphs. (3) By examining a growing social network graph (Flickr-Grow), we see that the corresponding bisimulation partition relation graph grows as well, but the growth is stable with respect to the original graph