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

Cohesive subgraph maintenance algorithms for large-scale temporal graphs

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

The important vertices and hierarchies in large-scale graph are of great significance for mining valuable information in complex networks(e.g.,social networks,traffic networks). In this paper,we propose a top-down(k,h)-core maintenance approach which can maintain only the top-n layers of the densest(k,h)-cores or the(k,h)-cores satisfying certain constraints.Firstly,we propose a method to identify the densest layer so as to locate the influenced scope of inserted edges. We also propose the concepts of candidate graph and partial(k,h)-core and provide their corresponding detection methods. With the help of partial(k,h)-core,our insertion algorithm can find the minimum incremental graph for each influenced(k,h)-core. For the removal case,our removal algorithm makes the minimum adjustment on previous(k,h)-cores to obtain current(k,h)-cores. We also theoretically prove the correctness of our algorithms. To verify the effectiveness of our methods,we conduct extensive experiments on several real temporal graphs. Experimental results show that our top-down(k,h)-core maintenance algorithms can accelerate dozens of times when adding edges and the number of maintenance layers is small. When deleting edges,the speedup ratio can reach 1 to 2 times. Our algorithm is flexible under various(k,h) settings,and maintains high efficiency for adding and deleting different numbers of edges.