Distributed method speeds up butterfly pattern counting in large signed graphs
Distributed Balanced Butterfly Counting in Signed Bipartite Graphs
Distributed, Parallel, and Cluster Computing
Summary
Counting balanced butterfly patterns in signed bipartite graphs helps understand complex relationships and communities in networks. Existing methods are slow on large graphs because they run on a single computer. The authors created a new distributed algorithm called D-BBC that splits the work across many processors to speed up counting. Tests show their method runs much faster than previous single-machine and distributed methods. This makes analyzing large real-world signed graphs more practical.
What this means in practice
- •For data engineers: Analyze large signed bipartite networks efficiently by counting balanced butterfly motifs to identify structural patterns at scale.
- •For social network analysts: Accelerate detection of community structures in social networks modeled as signed bipartite graphs using faster balanced butterfly counting.
Authors
Kiran Mekala, Apurba Das, Suman Banerjee
Abstract
The balanced butterfly is a fundamental primitive for analyzing signed bipartite graphs and provides a basis for studying higher-order structural properties, such as clustering coefficients and community structure. Despite its importance, existing approaches primarily rely on serial algorithms for balanced butterfly counting, which become inefficient on large-scale graphs. To address this limitation, we propose a distributed algorithm, D-BBC, based on a hybrid MPI+TBB framework that exploits MPI for inter-process communication and Intel TBB for intra-node parallelism. We conduct an experimental assessment of the proposed approach across 15 real-world datasets. Experimental results demonstrate that, on a single-node distributed system, D-BBC achieves average speedups of 1321x and 16.2x over the serial BB2K and multi-core M-BBC implementations, respectively. Furthermore, D-BBC achieves a maximum speedup of 23.58x over the distributed baseline S-Monarch in terms of end-to-end execution time. These results demonstrate the efficiency of the proposed distributed approach and its potential to enable high- performance signed motif analysis on large-scale bipartite graphs.