Efficient Core Maintenance Method Based on Dynamic Social Networks
In the real world,the structure of a social network graph is dynamically changing,resulting in a change in the core number of a vertex.Core maintenance refers to dynamically updating the core number of all vertices in the graph when the graph undergoes dynamic changes.The existing state-of-the-art core maintenance methods are traversal-based core maintenance algorithms and order-based core maintenance algorithm.To address the problem that the existing core maintenance algorithms are relatively inefficient in large-scale dynamic graphs,an efficient core maintenance method based on dynamic social networks is proposed.The shortcomings of traversal-based and order-based core maintenance algorithms are first analyzed.Then,a new kn-order index is constructed to maintain the order and neighbor information of vertices,a traversal query is improved to efficiently obtain the vertex set with changing core number after the dynamic change of the graph,and an edge insertion-based and an edge deletion-based core maintenance algorithms are proposed to efficiently maintain the core numbers of vertices.Finally,on four real datasets,it is demonstrated that the proposed algorithm effectively improves the efficiency of core maintenance based on dynamic social networks,which improves the execution efficiency of the algorithms by 3～4 times over that of the order-based core maintenance approach,and the proportion of accessing vertices in the graph decreases by about 2%on average,and the speedup ratio is improved by at least a factor of 2.
k-corecore numbercore decompositioncore maintenancekn-order index
国家科技期刊平台
NSTL
万方数据
