Can I read Fast Biclique Counting on Bipartite Graphs: A Node Pivot-based Approach on EtoBox?

Fast Biclique Counting on Bipartite Graphs: A Node Pivot-based Approach by Ye, Xiaowei; Li, Rong-Hua; Lin, Longlong; Qiao, Shaojie; Wang, Guoren is a scholarly article available to read on EtoBox.

What is Fast Biclique Counting on Bipartite Graphs: A Node Pivot-based Approach about?

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 \npivot, 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 \npivot based on a carefully-designed minimum non-neighbor candidate partition strategy. We prove that our new implementation of \npivot has lower worst-case time complexity than the state-of-the-art methods. Beyond basic biclique counting, a nice feature of \npivot 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 \npivot substantially outperforms state-of-the-art algorithms by up to two or

Author

Ye, Xiaowei; Li, Rong-Hua; Lin, Longlong; Qiao, Shaojie; Wang, Guoren

Published

2024

Language

EN