| dc.description.abstract | The k-core of an undirected graph is the largest subgraph in which every vertex has a degree of at least some number k. Computing the k-core, also known as the k-core decomposition algorithm, has significant applications in network analysis, visualization, bioinformatics, and community detection. There exists a sequential procedure, developed by Batagelj and Zaversnik in 2003, that accurately performs k-core decomposition. This implementation has been consistently referenced as the gold standard, due to its O(n + m) runtime. However, due to its large working set and lack of parallelism, its performance suffers on modern big-data graph problems where sheer size tends to overwhelm runtime due to cache misses. A 2014 algorithm designed by Dasari, Desh and Zubair M implements a parallel version of k-core decomposition (ParK) with significant speedup on multithreaded architectures. This paper aims to describe the development and implementation of ParK using the SuiteSparse:GraphBLAS API in C, a robust framework that defines a set of matrix and vector operations based on an algebra of semirings to perform computations on graphs. We show that while the GraphBLAS algorithm underperforms versus the sequential implementation in a full decomposition, a modified version of the algorithm that only computes a partial decomposition given some value k is significantly faster. | |
