关键词: 图概要, 图聚集, 最小描述长度, 属性图, 节点相似性

Abstract:

Graph summarization is one of the key techniques of managing, analyzing and visualizing large-scale graphs. It is a challenge to summarize attribute graphs by integrating structure and attribute information. Most of the existing graph summarization methods either consider only one aspect of the structure or attribute information, or require that the representation of the attribute is consistent. Based on the principle of minimum description length in information theory, the attribute graph profile problem is modeled and transformed into solving the minimum representation cost problem to achieve the dual goals of graph compression and graph summarization. A method of calculating attribute similarity of nodes is proposed, which unifies the similarity between nodes as representation cost, and considers the neighborhood and attribute similarity of nodes. Two graph summarization algorithms for solving the minimum cost representation are proposed. Finally, experiments on real and synthetic datasets demonstrate the effectiveness of the proposed algorithm.

Key words: graph summarization, graph aggregation, minimum description length, attribute dgraph, node similarity