Scalable Approximate Butterfly and Bi-triangle Counting for Large Bipartite Networks
Summary: Proposes one-sided weighted sampling, a bipartite-specific, unbiased approximate method for counting butterflies (2x2 bicliques) with a nontrivial extension to bi-triangles. Under power-law bipartite graphs, experiments show substantial speedups over exact methods and a fast approximate clustering coefficient estimator with <1% relative error. (summarized by gpt-5-nano on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Fangyuan Zhang (Chinese University of Hong Kong)
- 2. Dechuang Chen (Chinese University of Hong Kong; Xidian University)
- 3. Sibo Wang (Chinese University of Hong Kong)
- 4. Yin Yang (Hamad Bin Khalifa University)
- 5. Junhao Gan (University of Melbourne)
BibTeX Citation
@inproceedings{zhang_sigmod23,
title = {{Scalable Approximate Butterfly and Bi-triangle Counting for Large Bipartite Networks}},
author = {Zhang, Fangyuan and Chen, Dechuang and Wang, Sibo and Yang, Yin and Gan, Junhao},
series = {{SIGMOD} '23},
booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
publisher = {Association for Computing Machinery},
doi = {10.1145/3626753},
url = {https://dl.acm.org/doi/10.1145/3626753},
year = {2023}
}
Incoming Citations (Sorted by Pagerank)
Showing 2 of 2 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 9,916 | Efficient Historical Butterfly Counting in Large Temporal Bipartite Networks via Graph Structure-aware Index | 2025 | VLDB | 5.1955087e-05 |
| 11,094 | Efficient Computation of Hyper-triangles on Hypergraphs | 2025 | VLDB | 5.093636e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 23 of 23 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 11,269 | Maximum Balanced (k, epsilon)-Bitruss Detection in Signed Bipartite Graph | 2024 | VLDB |
| 2 | 5,427 | I/O-Efficient Butterfly Counting at Scale | 2023 | SIGMOD |
| 3 | 4,143 | Efficient Biclique Counting in Large Bipartite Graphs | 2023 | SIGMOD |
| 4 | 9,916 | Efficient Historical Butterfly Counting in Large Temporal Bipartite Networks via Graph Structure-aware Index | 2025 | VLDB |
| 5 | 10,369 | Estimating Biclique Counts with Accuracy Guarantees | 2026 | SIGMOD |
| 6 | 10,598 | Scalable Approximate Biclique Counting over Large Bipartite Graphs | 2026 | VLDB |
| 7 | 3,997 | Efficient Bi-triangle Counting for Large Bipartite Networks | 2021 | VLDB |
| 8 | 3,911 | Efficient Temporal Butterfly Counting and Enumeration on Temporal Bipartite Graphs | 2024 | VLDB |
| 9 | 3,723 | Butterfly Counting on Uncertain Bipartite Graphs | 2022 | VLDB |
| 10 | 1,211 | Vertex Priority Based Butterfly Counting for Large-scale Bipartite Networks | 2019 | VLDB |