动态图中核值维护算法研究

发布时间：2021-01-25 23:26

　　紧密子图挖掘是图数据分析领域的研究热点,可用于社区发现、分析网络拓扑结构以及网络行为和功能预测等。图中顶点核值是反映顶点所在子图紧密性的重要指标,被广泛应用于紧密子图挖掘。以往的研究多集中于静态图中核值计算,在更为常见的动态数据图中如何避免重复计算,实现动态核值维护,因多边插入/删除时顶点核值变化量难以确定等难题,还未有高效算法提出。为解决上述难题,基于边分组思想的核值维护算法得以提出。根据一定约束条件将插入/删除的边分为多个组,使得同一个组内的边插入/删除时造成的顶点核值变化量可确定,将多边更新时的核值维护问题分解为边分组和寻找核值变化的顶点两个子问题,从而高效解决动态核值更新问题。更具体地,通过证明满足“匹配”和“优边集”性质的边集在被同时处理时,能够保证顶点的核值变化量为确定值,给出基于“匹配”和“优边集”两种不同的边分组策略,得到高效核值维护算法。其中,基于匹配的算法具有更少的预处理时间,而基于优边集的算法可同时处理更多的边,减少处理轮数。相比于传统基于单边处理算法的多边顺序处理方式,基于分组策略的处理算法不仅极大降低核值更新的时间,提高核值更新效率,而且可以有效减少单边处理算... 

【文章来源】：华中科技大学湖北省 211工程院校 985工程院校 教育部直属院校

【文章页数】：64 页

【学位级别】：硕士

【部分图文】：

包含0,1,2,3核的图

图 1-2 辅助数组 vert, pos, bin 的对应关系作者考虑了当图太大无法放入内存中的情况，e，该算法采用自顶向下的方法，首先计算核值较核值。算法主要包括三个部分：一方面是一个顶点核值上界的机制，以及一个递归的自顶向遍历图一次便可以将图分成若干个小块，这样载入内存。估计顶点核值上界的机制保证了自

图 1-3 图中同时插入两条边内容工作如下：究了现有的核值维护算法，介绍了相关算法的在的问题，提出了同时处理多条边的核值维护单边核值维护算法处理多边插入/删除时存在出了一种能够解决多条边插入/删除的方法。其除的边根据一定的约束条件分成若干组，每次然后进行核值更新。通过理论论证，本文证明，可以保证图中所有顶点的核值变化最多为值需要更新的顶点。解决思路，本文首先提出一种称为“匹配”的边分成若干匹配，通过理论证明了一个匹配


本文编号：3000071