.png){kind=icon}
.png){kind=icon}
Return
Faster Parallel Core Maintenance Algorithms in Dynamic Graphs
.png){kind=icon}
PRE
AI
DOI：10.1109/TPDS.2019.2960226.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
This article studies the core maintenance problem for dynamic graphs which requires to update each vertex's core number with the insertion/deletion of vertices/edges. Previous algorithms can either process one edge associated with a vertex in each iteration or can only process one superior edge associated with the vertex (an edge < u, v > is a superior edge of vertex u if v' core number is no less than u's core number) in each iteration. Thus for high superior-degree vertices (the vertices associated with many superior edges) insertions/deletions, previous algorithms become very inefficient. In this article, we discovered a new structure called joint edge set whose insertions/deletions make each vertex's core number change at most one. The joint edge set mainly contains all the superior edges associated with the high superior-degree vertices as long as these vertices are 3(+)-hop independent. Based on this discovery, faster parallel algorithms are devised to solve the core maintenance problems. In our algorithms, we can process all edges in the joint edge set in one iteration and thus can greatly increase the parallelism and reduce the processing time. The results of extensive experiments conducted on various types of real-world, temporal, and synthetic graphs illustrate that the proposed algorithms achieve good efficiency, stability and scalability. Specifically, the new algorithms can outperform the single-edge processing algorithms by up to four orders of magnitude. Compared with the matching based algorithm and the superior edge based algorithm, our algorithms show a significant speedup up to 60x in the processing time.
Keywords:
Graph analysis
core maintenance problem
parallel algorithm
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
6
Papers:
5.2K
Citations:
1.1W
Organization
View more organizations