计算机科学与探索

作者：赵丹枫, 马健, 贺琪, 郑小罗, 李明刚

单位：上海海洋大学 信息学院，上海 201306

关键词：图计算,图摘要,图压缩,图简化

基金：国家自然科学基金（42376194）；国家自然科学基金青年项目（42106190）。

随着计算资源的进步，越来越多的现实世界数据以图的形式存储在计算机中。然而，直接处理大规模图所需的时间和资源成本不断攀升。有损图摘要技术在确保保留图的整体结构和主要属性的前提下，对图进行精炼和删减，从而生成一个近似输入图的紧凑表示，来获得较小存储需求和更高计算效率。然而，已有的工作通常面临计算效率与摘要质量的不平衡，或缺乏节点属性的纳入。为了解决这些问题，提出了一种基于迭代最小哈希局部敏感哈希（MinHash-LSH）的有损图摘要方法IMLS。方法通过引入结合属性权重的得分函数评估节点合并收益，迭代地合并节点对，生成一个限制节点数量的摘要图，旨在最大限度地减少重构误差与存储大小，同时最大限度地提高节点同质性。实验结果表明，IMLS在压缩比相似的情况下，运行时间比同类方法快约51.3倍，且能够生成较同类方法重构误差低约91.87%的摘要图。此外，IMLS方法具有线性可扩展性，适用于大规模图，并且通过控制属性权重参数，能够确保生成的摘要图具有可控的节点同质性。

来源：2025年第11期

《计算机科学与探索》期刊编辑部

查看计算机科学与探索杂志2025年第11期