GTC Silicon Valley-2019: Scalable K-Core Decomposition for Static Graphs Using a Dynamic Graph Data Structure
GTC Silicon Valley-2019 ID:S9440:Scalable K-Core Decomposition for Static Graphs Using a Dynamic Graph Data Structure
Alok Tripathy(Georgia Institute of Technology)
Learn how to find k-cores in graphs efficiently on GPUs using dynamic graph operations. The k-core of a graph is a metric used in social networks analytics, visualization, graph coloring, and other applications. We'll discuss a new parallel and scalable algorithm for finding the maximal k-core implemented. When run on an NVIDIA Tesla P100, that process is up to 58x faster than a sequential graph implementation and up to 4x faster than a similar parallel algorithm on a 36-core CPU. We'll explain how to extend our algorithm to support k-core edge decomposition for different size k-cores found in the graph. Our k-core decomposition algorithm on the P100 is up to 130x faster than sequential graph and up to 8x faster than the same CPU-based parallel algorithm. We'll also show how our algorithm finds a k-core with dynamic graph operations rather using a static graph.