Algorithmic Studies For Core Maintenance In Dynamic Graphs

Dense subgraph mining is a hot topic in graph analytics,which can be used in community detection,network topology analysis and network function prediction.The core number of a vertex is a fundamental index reflecting the cohesiveness of a graph,which is widely used in dense subgraphs mining.Most previous works focus on core decomposition in static graphs,but in the more commonly seen dynamic graphs,there have been no efficient algorithms presented to maintain core numbers of vertices,such that duplicated computations can be avoided,due to the value of core number change of each vertex is hard to determine when multiple edges are inserted/deleted.To solve the above challenge,the core maintenance algorithms based on edge division are proposed.The inserted/deleted edges are divided into groups according to specific constraints,such that the core number change of each vertex can be determined when a group of edges are inserted/deleted.In this way,the core maintenance problem is split into two subproblems: edge division and identifying vertices that change core number,which makes the problem solved efficiently.Specifically,we prove that the structures of matching and a proposed superior edge set can be used in the edge division.When inserting/deleting edges in a matching or a superior edge set,the core number change of each vertex can be determined.Based on these two structures,we propose efficient algorithms for core maintenance.In contrast,the matching based algorithms take less preprocessing time,while the superior edge set based algorithms can process more edges in each iteration,and hence need less processing iterations.Compared with the traditional approaches that sequentially execute an single-edge update algorithm to handle multiple edges,our edge division based algorithms can not only improve the efficiency of core maintenance,but also reduce the extra computations and save time and memory significantly.Besides,the edge division based algorithms can be implemented in parallel which can further enhance the efficiency of core maintenance.Extensive experiments are conducted on different types of real-world,temporal and synthetic datasets,and the results illustrate that the edge division based algorithms can maintain core numbers efficiently and exhibit good scalability in parallel systems.