现实世界中存在大量用图建模并表示的数据,如道路网络、社会网络、生物网络、Web图等,其中顶点表示实体,边表示实体之间的关系。随着图模型的广泛应用,图数据规模也越来越大,往往一个图中就包含有上百万个顶点和上千万条边。在这些大规模的图数据中,隐含了大量有用的信息。但是,图数据规模的增大,也使用户无法通过视觉观察或者简单的手工操作了解其内部有用的信息。因此把大型图数据集总结成精简的形式是迫切需要的。近年来,人们开始研究如何将一个大规模图的顶点聚集成若干组,并以这些顶点子集为新的顶点,构造一个简洁并能有效反映原始图的结构和属性信息的小规模图,叫做“聚集图”,从而帮助用户理解和分析原始图中的有用信息,这个过程就叫做“图聚集”。图聚集在图数据管理、分析和可视化中发挥着重要作用。图聚集方面现有研究结果还很少,也很不系统。其主要不足之处在于:1)算法依赖于具体应用;2)算法仅考虑了图的某方面信息,如结构信息或属性信息;3)算法对用户提供的交互和反馈信息的约束很强;4)算法忽略聚集图中顶点之间的关系。针对现有图聚集技术存在的问题,本文提出一种有向图上时间复杂性为O(|V|log|V| + |E|)的新型图聚集算法,其中|V|和|E|分别为输入图的顶点数和边数。该算法使用局部敏感哈希(Locality Sensitive Hashing简称LSH)技术和基于熵的顶点划分技术,不仅有效保证了算法时间复杂性,也保证了聚集图的质量。为了衡量聚集图的质量,本文进一步定义了新的聚集图质量评价标准,全面地刻画了聚集图的多样性、覆盖性、简洁性和实用性。对比已有的聚集图质量评价标准,本文提出的聚集图质量评价算法更关注聚集图在实际应用中的意义。本文在真实数据集上进行实验,证实了算法的有效性。