图的有损摘要问题的两阶段算法  

Two-stage Algorithm for Lossy Graph Summarization

作　　者：冯康 陈卫东[1] FENG Kang;CHEN Wei-Dong(School of Computer Science,South China Normal University,Guangzhou 510631,China)

机构地区：[1]华南师范大学计算机学院,广州510631

出　　处：《计算机系统应用》2023年第6期189-196,共8页Computer Systems & Applications

基　　金：国家自然科学基金(61370003)。

摘　　要：问题如下:给定图G=(V, E)和正整数k,要求将图G中所有节点合并成为k个超节点,满足由这些超节点组成的摘要图能够在一定误差范围内表示原图G.这是一个基于图划分的组合优化问题,一个主要求解思路是逐次地随机抽取节点对集并用启发式方法从中选取节点对进行合并.本文提出一个有效的两阶段求解算法TS_LGS.算法根据图G的平均点度特征设置阶段阈值:当前超节点数大于阶段阈值为第1阶段,期间算法在采样节点对中基于当前最佳合并分数批量选择节点对合并,旨在有效减少迭代次数;否则为第2阶段,期间算法在加权采样的基础上优先挑选相邻的节点对,旨在找到重构误差增量较小的节点对合并,直至超节点的个数为k.在典型的真实网络实例图上与现有最好算法SAA进行了实验对比,结果表明,算法TS_LGS以较低时间复杂度提取到的图摘要具有更低的重构误差和查询误差.The problem of lossy graph summarization is as follows:Given a graph G=(V,E)and a positive integer k,it is required to merge all nodes in graph G into k super nodes so that the resulting summary graph composed of these super nodes can represent the original graph G within a certain error range.As a combinatorial optimization problem based on graph partitioning,this problem is usually solved by randomly extracting node pairs successively and using heuristic methods to select node pairs for merging.This study proposes an effective two-stage algorithm,namely TS_LGS.The algorithm first sets the stage threshold according to the average degree of graph G.Specifically,in the first stage,the current number of super nodes is greater than the stage threshold,and the algorithm selects node pairs among the sampled node pairs in batch for merging based on the current best merging score,so as to effectively reduce the number of iterations;in the second stage,the algorithm preferentially selects adjacent node pairs based on weighted sampling,so as to merge the node pairs with small reconstruction error increment until the number of super nodes is k.The experimental results on several typical real network instances show that TS_LGS can extract graph summarization with lower reconstruction and query errors on the premise of lower time complexity compared with the existing best SAA algorithm.

关 键 词：图摘要 图有损摘要 重构误差 平均度 

分 类 号：O157.5[理学—数学]