基于节点相似性分组与图压缩的图摘要算法

作     者：宏宇 陈鸿昶 张建朋 黄瑞阳 HONG Yu;CHEN Hongchang;ZHANG Jianpeng;HUANG Ruiyang

作者机构：郑州大学网络空间安全学院郑州450002 信息工程大学信息技术研究所郑州450002 

出 版 物：《计算机应用》 (journal of Computer Applications)

年 卷 期：2023年第43卷第10期

页      面：3047-3053页

学科分类：081203[工学-计算机应用技术] 08[工学] 0835[工学-软件工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：国家自然科学基金资助项目(62002384) 中国博士后科学基金资助项目(2020M683760) 

主　　题：图摘要 图压缩 图查询 超边 最小描述长度 

摘      要：针对当前图摘要方法压缩率较高,图压缩算法无法直接被用于下游任务分析的问题,提出一种图摘要与图压缩的融合算法,即基于节点相似性分组与图压缩的图摘要算法(GSNSC)。首先,初始化节点为超节点,并根据相似度对超节点分组;其次,将每个组的超节点合并,直到达到指定次数或指定节点数;再次,在超节点之间添加超边和校正边以恢复原始图;最后,对于图压缩部分,判断对每个超节点的邻接边压缩和摘要的代价,并选择二者中代价较小的执行。在Web-NotreDame、Web-Google和Web-Berkstan等6个数据集上进行了图压缩率和图查询实验。实验结果表明,在6个数据集上,与SLUGGER(Scalable Lossless sUmmarization of Graphs with HiERarchy)算法相比,所提算法的压缩率至少降低了23个百分点;与SWeG(Summarization of Web-scale Graphs)算法相比,所提算法的压缩率至少降低了13个百分点;在Web-NotreDame数据集上,所提算法的度误差比SWeG降低了41.6%。以上验证了所提算法具有更好的图压缩率和图查询准确度。