Efficient counting of balanced (2, k)-bicliques in Signed Bipartite Graphs

Analysis of large-scale networks for different structural patterns (also called motifs) remains an active area of research in the domain of graph data management and mining. In the past three decades, research has led to a large volume of literature in this area. However, the literature in the context of a signed bipartite graph is limited. In this paper, we study the problem of counting the balanced motifs in a signed bipartite graph. Specifically, We design an efficient algorithm BB2K for counting balanced (2, k)-bicliques. Previous studies for balanced bicliques in a signed bipartite graph focus on a set enumeration-based approach. We observe that the set enumeration-based approaches are expensive as they need to discard a large number of structures, which are not balanced. We take a different approach where we systematically group the symmetric and asymmetric wedges and count the balanced bicliques by counting on those wedges in such a way that we eliminate the generation of unbalanced structures completely. We conducted experiments with nine real-life datasets, and the experimental results demonstrate that our algorithm BB2K is more than 100× faster than the baseline SBCList++ - an adaptation of the state-of-the-art algorithm BCList++ combined with the filtering technique to filter out unbalanced bicliques. We have also shown the scalability of the proposed algorithm by using datasets of different sizes in our experiments.