张 陶，于 炯，廖 彬，毕雪华

1.新疆大学 信息科学与工程学院，乌鲁木齐 830046

2.新疆医科大学 医学工程技术学院，乌鲁木齐 830011

3.新疆财经大学 统计与信息学院，乌鲁木齐 830012

图是一种能够表现实体及其之间复杂关系的模型。许多领域如Web网络、通信网络、社交网络、生物网络、交通网络、传球网络[1]等，都可以用图数据结构进行描述，采用基于图数据的方法进行处理。然而，随着时间的推移，图变得越来越大，例如截止2017 年10 月，Facebook 的常规移动用户达到20 亿[2]。如何从这些具有上亿节点和千亿条边的大规模图数据中找到和分析用户所需要的信息，是一个极具挑战性的难题。因为将如此大规模的图直接加载内存，不仅耗费大量资源，而且导致可视化视图非常混乱。图概要（图聚集）技术是大图内存处理的一种有效的方法。它将一个大规模图概要成一个简洁且能够反映原始图结构和属性信息的小规模图（被称为“概要图”或“摘要图”）。概要图代替原始大图进行数据分析，帮助用户理解和分析原始图中的有用信息。如图1所示，图1（右）是图1（左）的一个摘要结果。显然图1（右）较图1（左）更容易分析和理解。超点V4、V5，因为里面的节点属性不相似，被划分到不同超点中。若为了结构更紧凑，可继续合并超点V4、V5为超点V6。

图1 由原始图产生的摘要图Fig.1 Summary graphs generated from original graphs

实际应用中图数据往往拥有大量信息，除了用节点来表示实体、边表示实体之间的关系之外，还有大量的属性信息伴随着节点和边出现。这种图称为属性图。……