图数据经常在现实生活中用来描述实体之间的关系。节点表示实体,边表示实体与实体之间的特定关系,如网络中用户之间的关系、交通网络中道路之间的关系、WEB图中网页之间的关系等。随着图数据规模不断增大,无法直接通过肉眼视觉来处理和分析这些图数据。为了节省存储空间和便于对图数据进行分析和查询,需要将大规模图进行压缩,以便于可视化和分析图数据。因此,图聚集技术成为了研究热点。面向查询的图聚集的主要目的是保持原始图中的查询信息,如可达性关系,邻域关系,节点距离等,以此为目标对节点进行聚集。通过对现有图聚集技术现状总结分析,本文主要在面向距离查询的图聚集和可达性保护的图聚集两个方面展开了深入的研究,并取得了如下研究成果:1.提出了融合结构与属性相似性的加权图聚集算法:针对现有算法未考虑图数据同时带有节点属性与边权重的情况,提出一种融合结构与属性相似性的加权图聚集算法,本方法首先使用一种剪枝策略来快速判断节点之间的闭邻域结构相似度,去除掉结构不相似的节点对,并计算剩余节点对精确的结构相似度;其次使用最小哈希技术,计算结构相似的节点对之间的属性相似度;再次,结合节点对之间的结构相似度和属性相似度,得到节点对之间的联合相似度;最后选择联合相似度高的节点进行合并,并计算聚集后新的节点之间的边权重值。2.提出了面向距离查询的属性加权图聚集算法:针对在聚集图上执行节点间距离查询的任务,提出了面向距离查询的属性加权图聚集算法,可用于查询和存储加权图和无权图,且使用此算法进行聚集对节点间的距离影响最小。具体来说,当合并两个节点成一个超点,引入方程组使合并导致的距离差异最小化,基本原理就是使误差的平均值等于零。算法首先使用剪枝策略过滤掉结构不相似的节点对,并计算剩余节点对间的精确结构相似度;其次,使用属性熵来衡量形成的超点内部属性的一致性;然后,根据已得到的结构相似度值和属性熵值,来计算节点对之间的质量分数,决定该节点对是否合并;最后,通过联立方程组并解方程来赋予新边的权重值,使新边权重对节点间距离的影响最小。3.提出了面向可达性保护的图聚集算法:针对在聚集图上执行可达性查询的任务,提出了一种高度紧凑且带有修正表的可达性保护图聚集算法。该算法首先通过原始图中的可达性等价关系将原始图中的节点划分为等价类。然后根据其前驱和后继节点的相似性进一步压缩每对等价类。此外,使用了一组修正来保持原始图中节点的可达性关系。该方法生成规模很小的聚集图,只保留了与可达性查询相关的信息,而不保留整个原始图,从而获得更好的压缩率。任何用于评估可达性查询的算法都可以在该方法产生的聚集图上直接执行,而无需解压聚集图。此外,为了处理原始图的动态变化,本章还提出了一种动态可达性保持压缩算法,对压缩后的图和修正表进行更新,在压缩一次后不需要解压缩就可以执行更新来保持原始图的可达性。