Fast Biclique Counting on Bipartite Graphs: A Node Pivot-based Approach
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916537876611072 |
|---|---|
| author | Ye, Xiaowei Li, Rong-Hua Lin, Longlong Qiao, Shaojie Wang, Guoren |
| author_facet | Ye, Xiaowei Li, Rong-Hua Lin, Longlong Qiao, Shaojie Wang, Guoren |
| contents | 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 orders of magnitude. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_16485 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Fast Biclique Counting on Bipartite Graphs: A Node Pivot-based Approach Ye, Xiaowei Li, Rong-Hua Lin, Longlong Qiao, Shaojie Wang, Guoren Data Structures and Algorithms 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 orders of magnitude. |
| title | Fast Biclique Counting on Bipartite Graphs: A Node Pivot-based Approach |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2412.16485 |