Graph Summarization Based on Attribute-Connected Network

摘要

Techniques to summarize and cluster graphs are important to understand the structure and pattern of large complex networks. State-of-art graph summarization techniques mainly focus on either node attributes or graph topological structure. In this work, we introduce a unified framework based on node attributes and topological structure to support attribute-based summarization. We propose a summarizing method based on virtual links (node attributes) and real links (topological structure) called Greedy Merge (GM) to aggregate similar nodes into k non-overlapping attribute-connected groups. We adopt the Locality Sensitive Hashing (LSH) technique to construct virtual links for high efficiency. Experiments on real datasets indicate that our proposed method GM is both effective and efficient.