SC21 Proceedings

The International Conference for High Performance Computing, Networking, Storage, and Analysis

Discovering and Balancing Fundamental Cycles in Large Signed Graphs

Authors: Ghadeer Alabandi, Jelena Tešić, Lucas Rusnak, and Martin Burtscher (Texas State University)

Abstract: Computing consensus states via global sign balancing is a key step in social network analysis. This paper presents graphB+, a fast algorithm for balancing signed graphs based on a new vertex and edge labeling technique, and a parallel implementation thereof for rapidly detecting and balancing all fundamental cycles. The main benefits of graphB+ are that the labels can be computed with linear time complexity, only require a linear amount of memory, and that the running time for balancing a cycle is linear in the length of the cycle times the vertex degrees but independent of the size of the graph. We parallelized graphB+ using OpenMP and CUDA. It takes 0.85 seconds on a Titan V GPU to balance the signs on the edges of an Amazon graph with 10 million vertices and 22 million edges, amounting to over 14 million fundamental cycles identified, traversed, and balanced per second.

Presentation: file

Back to Technical Papers Archive Listing