Fast Biclique Counting on Bipartite Graphs: A Node Pivot-based Approach
Xiaowei Ye, Li, Rong-Hua, Longlong Lin, Shaojie Qiao, Guoren Wang · arXiv (Cornell University) · 2024
Counting the number of $(p, q)$-bicliques (complete bipartite subgraphs) in a bipartite graph is a fundamental problem which plays a crucial role in numerous bipartite graph analysis applications. However, existing algorithms for counting $(p, q)$-bicliques often face significant computational challenges, particularly on large real-world networks. In this paper, we propose a general biclique counting framework, called pivot, based on a novel concept of node-pivot. We show that previous methods can be viewed as specific implementations of this general framework. More importantly, we propose a novel implementation of pivot based on a carefully-designed minimum non-neighbor candidate partition strategy. We prove that our new implementation of pivot has lower worst-case time complexity than the state-of-the-art methods. Beyond basic biclique counting, a nice feature of pivot is that it also supports local counting (computing bicliques per node) and range counting (simultaneously counting bicliques within a size range). Extensive experiments on 12 real-world large datasets demonstrate that our proposed pivot substantially outperforms state-of-the-art algorithms by up to two orders of magnitude.