一种新的高效图聚集算法

摘要

图聚集是将一个大规模的图用简洁的并能有效反映原始图的结构和属性信息的小规模图来表示的技术。图聚集在图数据管理、分析和可视化中发挥着重要作用。图聚集方面现有研究结果还很少,也很不系统。文章针对现有图聚集算法存在的主要不足,提出一种有向图新型图聚集算法,该算法采用一种新的聚集图质量函数,全面刻画了聚集图多样性、覆盖性、简洁性和实用性。该算法使用LSH(locality sensitive Hashing)技术和基于熵的划分技术,保证了聚集图的质量。在真实数据集上进行了大量的实验,验证了算法的有效性。