Bitruss Decomposition On GPU

Prerequisites

• CMake 3.22 or higher
• NVIDIA CUDA Toolkit 12.2 or higher
• A CUDA-capable GPU device

Build from Source

To build the GPU bitruss code, execute the following commands in your terminal:

mkdir build && cd build
cmake -DCMAKE_BUILD_TYPE=Release .. && cmake --build . && make

CMake Configuration

For a better performance, you need to change the set(CMAKE_CUDA_ARCHITECTURES 86) in CMakeLists.txt file. The value of CMAKE_CUDA_ARCHITECTURES can be obtained from the output of GPU device info (Compute Capability):

./coh --device 0 --device_info
----------------------------------------------------------------
|            Property             |            Info            |
----------------------------------------------------------------
...
| Compute Capability              | 86                         |
...
----------------------------------------------------------------

Set the appropriate CMAKE_CUDA_ARCHITECTURES according to the output, then rebuild the code.

Usage

> ./coh --help                                            
Usage: bitruss [--help] [--version] [--device VAR] [--device_info] [--graph VAR] [--bin VAR] [--cpu] [--gpu] [--algo VAR] [--threads VAR]

Optional arguments:
  -h, --help     shows help message and exits 
  -v, --version  prints version information and exits 
  --device       GPU Device ID (must be a positive integer) [nargs=0..1] [default: 0]
  --device_info  Display GPU device properties 
  --graph        Graph file path [nargs=0..1] [default: "/"]
  --bin          Output binary file path 
  --cpu          Run CPU algorithms 
  --gpu          Run GPU algorithms 
  --algo         Algorithm to run including: bfc, hidx, msp [nargs=0..1] [default: "msp"]
  --threads      Number of threads (must be a positive integer) [nargs=0..1] [default: 1]

Algorithms

The table below details the commands for running different algorithms on CPU and GPU:

	Butterfly counting	Butterfly support counting	h-index bitruss	GBiD
CPU	--cpu --algo bfc	--cpu --algo ebfc	--cpu --algo hidx	--cpu --algo msp
GPU	--gpu --algo bfc	--gpu --algo ebfc	--gpu --algo hidx	--gpu --algo msp

Convert graph to binary file

The command only supports standard bipartite graphs and does not support temporal or multilayer bipartite graphs. For other types of bipartite graphs, they must be converted to standard bipartite graphs before running the algorithm.

Basic Conversion Command

./coh --graph data/aw.graph --bin data/aw.bin

Using Datasets from KONECT

If you download the dataset from http://konect.cc/, you can use the following command to convert the graph file to binary file:

./coh --graph out.xxxxx --bin xxx.bin

Note that, the graph file downloaded from http://konect.cc/ is named as out.xxxxx. For example, you can download the SC dataset, after decompressing the file, you can convert the graph file to binary file:

./coh --graph brunson_south-africa/out.brunson_south-africa_south-africa --bin sc.bin

Examples

Converting the graph file to binary file:

./coh --graph data/aw.graph --bin data/aw.bin

Running the bitruss algorithm on GPU:

./coh --gpu --device 0 --algo msp --graph data/aw.bin

Running the bitruss algorithm on CPU:

./coh --cpu --threads 32 --algo msp --graph data/aw.bin

Running the butterfly support counting algorithm on GPU:

./coh --gpu --device 0 --algo ebfc --graph data/aw.bin

Running the butterfly counting algorithm on GPU:

./coh --gpu --device 0 --algo bfc --graph data/aw.bin

--device 0 denotes the GPU device ID, you can change it to other GPU device ID.

Run with Docker

Use the following commands to build and run your Docker container, ensuring that it utilizes the GPU capabilities:

docker build -t bitruss .
docker run -it --gpus all bitruss

If you have the following error:

docker: Error response from daemon: could not select device driver "" with capabilities: [[gpu]]. ERRO[0000] error waiting for container: context canceled

you can execute the following command to solve this issue:

sudo apt install -y nvidia-docker2 
sudo systemctl daemon-reload
sudo systemctl restart docker