This repository implements edge connectivity-based hierarchical graph decomposition algorithms proposed in our VLDB 2022 paper. If you are using the code, please cite our papers.

Lijun Chang and Zhiyi Wang.
A Near-Optimal Approach to Edge Connectivity-Based Hierarchical Graph Decomposition.
Proc. VLDB Endow. 15(6), (2022)

Lijun Chang and Zhiyi Wang.
A Near-Optimal Approach to Edge Connectivity-Based Hierarchical Graph Decomposition.
VLDB Journal, (2023)

Compile the code

$ make clean
$ make

It generates an executable “eco_decompose”.

Run the code

Different algorithms can be invoked by executing “eco_decompose”. You can find how to use the code by

$ ./eco_decompose -h

An example of computing edge connectivity-base hierarchical graph decomposition for the dataset CA-GrQc by the ECo-DC-AA algorithm is as follows

$ ./eco_decompose -g datasets/CA-GrQc/ -a eco-decompose-dcs -o result.txt

An example of computing edge connectivity-base hierarchical graph decomposition for the dataset CA-GrQc by the BU*-AA algorithm is as follows

$ ./eco_decompose -g datasets/CA-GrQc/ -a eco-decompose-buso -o result.txt

An example of computing 10-edge connected components for the dataset CA-GrQc by the algorithm KECC-AA is as follows

$ ./eco_decompose -g datasets/CA-GrQc/ -a kecc-space -k 10 -o result.txt

Data format

Each graph is represented by two binary files, b_adj.bin and b_degree.bin (e.g. datasets/CA-GrQc/b_adj.bin and datasets/CA-GrQc/b_degree.bin). More details of the data format can be found in https://lijunchang.github.io/Cohesive_subgraph_book/datasets