Abstract
Traditional graph algorithms assume that the input graphs are completely resided in a single machine. However, due to data management or privacy reasons, a graph could be partitioned and stored on different machines. For instance, when a graph is dynamic and very large in scale, one would hope to partition it into parts so that updating one part would not affect the other parts. Alternatively, there may be multiple administrative parties, each owning only a part of a graph, but from time to time, these parties may want to work collaboratively on the whole graph (say, to compute some graph statistics), without others accessing their own part. To handle partitioned graphs, one may resort to design distributed algorithms, targeting to reduce the number of individual messages among the machines, as well as the overall running time. An orthogonal approach is to compute a small graph summary for each part of the graph (a.k.a. mimicking network), and then a single machine collects these summaries to perform subsequent computation. This approach is relatively underdeveloped and has only been restricted to the maximum flow problems. Yet, it has multiple advantages: (1) the messages among machines could be batched, (2) the computation of graph summaries could be parallelized, (3) machines with mediocre computing power or limited memory can be utilized, and (4) privacy of the internal structure of the partitioned graph can be preserved. In this paper, we explore both the theoretical and practical aspects of the graph summary approach on various fundamental graph algorithms. We demonstrated how graph summary works by designing and analyzing three commonly used graph algorithms: connected components, shortest path, and minimum spanning tree, and implemented a distributed system for answering the queries for large and dynamically updating graphs. Experimental results show that our system is almost 30 times faster than traditional master-slave architecture.