一种动态图下多边更新的单轮核值维护方法

摘要

本发明公开了一种动态图下多边更新的单轮核值维护方法，包括插入点或边时的顶点核值维护单轮算法和删除点或边时的顶点核值维护单轮算法。在更新图之前，维护一个全局有序的节点次序。插入点或边的核值维护算法在单轮中一次性加入所有边，之后按照次序依次对顶点开始遍历，将核值增加的顶点的影响向高次序顶点移动，直到没有顶点的核值发生变化。删除点或边的核值维护算法在单轮中一次性删除所有边，并从删除了边的顶点开始遍历，通过不断的迭代直到所有顶点的核值处于稳定状态。本发明方法通过单轮算法便完成了所有顶点的核值维护，减少了图遍历过程中对顶点的冗余计算，缩减了核值维护的时间，尤其对于大规模图而言具有极好的扩展性和稳定性。