Updating Strategy For K-core Hierarchy Index Tree On Dynamic Graph

Communities refer to subnetworks in a network that are tightly connected internally but sparsely connected to the outside.A k-core community is a connected subgraph of a graph in which each vertex has degree greater than or equal to k.Because of its linear time solvability,the k-core community is one of the most important community structures and is often used for solving other community structures.The specific research in this paper is as follows.First,to support efficient k-core community search,this paper proposes a k-core index tree based on label encoding.This index tree speeds up the search of k-core communities by adding appropriate labels to the tree nodes and thus exploiting the inclusion relationships between the labels.Second,to support dynamic networks,this paper proposes a three-stage update scheme to maintain this index tree,including coreness maintenance,tree structure maintenance,and label maintenance.For tree structure maintenance,this paper proposes the RMEC algorithm using vertex connectivity at both ends of the deleted edges,which reduces the traversal of vertices and their neighbors and speeds up the maintenance speed.For label maintenance,this paper proposes the Maintain*algorithm,which supports fast updates on dynamic graphs by maintaining labels only on subtrees affected by graph changes.Finally,experiments are conducted based on eight real data sets and compared with existing methods.On the query side,the efficiency of the proposed index structure is verified by varying the query set size;on the protection side,experiments are conducted for each phase to verify the efficiency of the RMEC algorithm and Maintain* algorithm.