面向大规模时态图的紧密子图维护算法

作者：车鑫恺; 陈雅迪; 胡淼; 吴迪^*

来源：南京大学学报(自然科学), 2022, 58(03): 398-412.

DOI：10.13232/j.cnki.jnju.2022.03.004

• 大规模图
• 核值维护
• 紧密子图
• 时态图

大规模图数据中的重要顶点与层级结构对于挖掘复杂网络（如社交网络、交通网络等）中有价值的信息具有重要意义.提出一种自顶向下的大规模时态图(k,h)-维护算法，对时态图中紧密度最高的前n层(k,h)-核，或满足自定义k,h值约束条件的核进行维护.首先提出识别(k,h)-最大层的方法 .当时态图中出现新的边时，为了定位当前时刻可能因新加入边导致核值需要更新的顶点的范围，提出候选插入子图与部分(k,h)-核的概念及相应的识别算法.针对加边情况，提出自顶向下的时态图(k,h)-核维护加边算法，根据部分(k,h)-核识别核值受加边影响的顶点并对其核值进行更新.针对当前时刻有已经存在的边被删除的情况，提出自顶向下的时态图(k,h)-核维护删边算法，对上一时刻的(k,h)-核做最小调整以得到当前时刻的核值.从理论上证明了算法的正确性，还在真实的时态图上设计了一系列对比实验.实验结果表明，在维护层数较少时下添加边，提出的核维护算法与其他对比算法相比，加速比可达几十倍；删边时，加速比也在1～2倍.提出的算法有良好的扩展性，对于增删不同数量的边和不同的(k,h)设置，都能保持较高的效率.

• 单位
  中山大学