graphB+ v0.3
graphB+ is a balancing algorithm for signed social network graphs. It operates on graphs stored in CSV format. A sample input graph can be found here.
The inputs are simple text files consisting of a header line followed by an arbitrary number of lines, each specifying one edge of the graph, where the edge weight is the sign (either 1 or -1):
From Node ID, To Node ID, Edge Weight
10,33,-1
8,5,1
Click on graphBplus_03.cu to download the CUDA code or on graphBplus_03.cpp to download the OpenMP C++ code (with g++ intrinsics). Note that graphB+ is protected by the 3-clause BSD license included in the beginning of the code.
The CUDA code can be compiled as follows:
nvcc -O3 -arch=sm_70 graphBplus_03.cu -o graphBplus
The OpenMP C++ code can be compiled as follows:
g++ -O3 -march=native -fopenmp graphBplus_03.cpp -o graphBplus
To run the code on the input file graph.csv with 100 samples and save the results of the balanced solutions in out.csv, enter:
./graphBplus graph.csv 100 out.csv
To obtain the inputs used in the paper listed below and convert them to our format, download and run the file input_script.sh. Note that this script takes about an hour to execute and requires a large amount of disk space.
Publication
G. Alabandi, J. Tesic, L. Rusnak, and M. Burtscher. "Discovering and Balancing Fundamental Cycles in Large Signed Graphs." Proceedings of the 2021 ACM/IEEE International Conference for High-Performance Computing, Networking, Storage and Analysis. November 2021.
[doi]
[pdf]
Summary: At the core of graphB+ is an algorithm for quickly identifying, traversing, and balancing all fundamental cycles in a connected signed graph. Given a spanning tree of the input graph, graphB+ relabels each vertex according to a pre-order traversal starting from the root. The new vertex IDs enable graphB+ to assign a pair of values to each edge of the tree that expresses the exact range of vertex IDs reachable when traversing that edge in the parent-to-child direction. For the fundamental cycle formed by including each non-tree graph edge, these pairs allow to quickly find the edges of the corresponding fundamental cycle. Minimizing the traversal time required to identify the cycles is the key contribution of graphB+. As each cycle is traversed, graphB+ collects information on the number of negative-signed edges and balances the cycle by switching the sign of the non-tree graph edge associated with the cycle as needed. To further improve performance, graphB+ is parallelized using OpenMP and CUDA.
This work has been supported in part by the National Science Foundation under Award Number 1955367, by the Department of Energy, National Nuclear Security Administration under Award Number DE-NA0003969, and by a hardware donation from NVIDIA Corporation.
|