Parallel order-based core maintenance in dynamic graphs

The core number of vertices in a graph is one of the most well-studied cohesive subgraph models due to linear running-time algorithms. In practice, many data graphs are dynamic graphs that continuously change by inserting and removing edges. The core numbers are updated in dynamic graphs with edge insertions and deletions, called core maintenance. When a burst of a large number of inserted or removed edges comes in, these must be handled on time to keep up with the data stream. There are two main sequential algorithms for core maintenance, Traversal and Order . Experiments show that the Order algorithm significantly outperforms the Traversal algorithm over various real graphs. To the best of our knowledge, all existing parallel approaches are based on the Traversal algorithm. These algorithms exploit parallelism only for vertices with different core numbers; they reduce to sequential algorithms when all vertices have the same core numbers. This paper proposes a new parallel core maintenance algorithm based on the Order algorithm. A distinguishing property is that the algorithm allows parallelism even for graphs where all vertices have the same core number. Extensive experiments are conducted over real-world, temporal, and synthetic graphs on a multicore machine. The results show that for inserting and removing a batch of edges using 16 workers, the proposed method achieves speeds of up to 289 times and 10 times compared to the most efficient existing method. This research was previously published in [1] as a short version. In this work, we expand to a full version that includes details on implementation, proofs, and experiments.