Graph summarization is to obtain a concise representation of a large graph, which is suitable for visualization and analysis. The main idea is to construct a super-graph by grouping similar nodes together. In this paper, we propose a new information-preserving approach for graph summarization, which consists of two parts: a super-graph and a list of probability distribution vectors affiliated to the super-nodes and super-edges. After a carefully analysis of the approximately homogenous grouping, we propose a unified model using information theory to relax all conditions and measure the quality of the summarization. We also develop a new lazy algorithm to compute the exactly homogenous grouping, as well as two algorithms to compute the approximate grouping. We conducted experiments and confirmed that our approaches can efficiently summarize attributed graphs homogeneously and achieve low entropy.
展开▼
