Parallel-KCore

SIGMOD'25: Parallel k-Core Decomposition: Theory and Practice

Download

git clone --recursive [email protected]:ucrparlay/Parallel-KCore.git

Requirements

• CMake >= 3.15
• g++ or clang with C++17 features support (tested with g++ 12.1.1 and clang 14.0.6) on Linux machines.
• We use ParlayLib to support fork-join parallelism and some parallel primitives. It is provided as a submodule in our repository.

Compilation

cd KCore && make

Running Code

./kcore [-s] [-i graph_path]

• -s: indicate the input graph is symmetric (undirected). If not, the directed graph will be symmetrized without the -s parameter.
• -i graph_path: the graph path (.adj or .bin formats are both accepted, see GBBS graph format as a reference. You can find the datasets at PASGAL)

For example, to run our algorithm on twitter

./kcore -s -i data/twitter_sym.bin
./kcore -i data/twitter.bin

or

./kcore -s -i data/twitter_sym.adj
./kcore -i data/twitter.adj

If you use our code, please cite our paper:

@article{liu2025parallel,
  title={Parallel k-Core Decomposition: Theory and Practice},
  author={Liu, Youzhe and Dong, Xiaojun and Gu, Yan and Sun, Yihan},
  journal={Proceedings of the ACM on Management of Data},
  volume={3},
  number={3},
  pages={1--27},
  year={2025},
  publisher={ACM New York, NY, USA}
}