Efficiency and Precision Trade-Offs in Graph Summary Algorithms

ACM Digital Library
International Database Engineering & Applications Symposium
Conference Paper
In many applications, it is convenient to substitute a large data graph with a smaller homomorphic graph. Accurate graph summarization algorithms are sub-optimal for a shared-nothing infrastructure such as MapReduce as they require multiple iterations over the data graph. We investigate approximate graph summarization algorithms that are efficient to compute in a shared-nothing infrastructure. We evaluate over several datasets the trade-offs between performance and precision. Experiments highlight the need of trade-offs between precision and complexity of a summarization algorithm.