Back to papers
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)
- Paper ID
- 6760
- Venue
- SIGMOD
- Year
- 2023
- Pagerank
- 4.7263711e-05
- Overall Rank
- 7,451 | 48.17%
- DOI
-
10.1145/3626753
Incoming Non-self Citations Over Time
Incoming Citations (Sorted by Pagerank)
Showing 2 of 2 citing papers.
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.
| Rank |
Cited Paper |
Year |
Venue |
Pagerank |
| 283 |
Querying K-Truss Community in Large and Dynamic Graphs |
2014 |
SIGMOD |
0.00029041257 |
| 337 |
Influence Maximization in Near-Linear Time: A Martingale Approach |
2015 |
SIGMOD |
0.00027011645 |
| 589 |
Massive Graph Triangulation |
2013 |
SIGMOD |
0.00019576567 |
| 728 |
Meaningful Change Detection in Structured Data |
1997 |
SIGMOD |
0.00017494982 |
| 891 |
Maximum Biclique Search at Billion Scale |
2020 |
VLDB |
0.00015564292 |
| 943 |
Wander Join: Online Aggregation via Random Walks |
2016 |
SIGMOD |
0.00015145883 |
| 1,484 |
Vertex Priority Based Butterfly Counting for Large-scale Bipartite Networks |
2019 |
VLDB |
0.00011714263 |
| 2,242 |
HubPPR: Effective Indexing for Approximate Personalized PageRank |
2017 |
VLDB |
9.218875e-05 |
| 2,286 |
Effective and Efficient Community Search over Large Heterogeneous Information Networks |
2020 |
VLDB |
9.0982591e-05 |
| 2,664 |
Influence Maximization Revisited: Efficient Reverse Reachable Set Generation with Bound Tightened |
2020 |
SIGMOD |
8.3512717e-05 |
| 2,684 |
Truss Decomposition of Probabilistic Graphs: Semantics and Algorithms |
2016 |
SIGMOD |
8.3136866e-05 |
| 2,903 |
(p,q)-biclique Counting and Enumeration for Large Sparse Bipartite Graphs |
2022 |
VLDB |
7.9375744e-05 |
| 2,909 |
Efficient Algorithms for Densest Subgraph Discovery |
2019 |
VLDB |
7.9305767e-05 |
| 2,914 |
DDSketch: A Fast and Fully-Mergeable Quantile Sketch with Relative-Error Guarantees |
2019 |
VLDB |
7.9118579e-05 |
| 3,369 |
Query Driven-Graph Neural Networks for Community Search: From Non-Attributed, Attributed, to Interactive Attributed |
2022 |
VLDB |
7.171452e-05 |
| 4,171 |
Butterfly Counting on Uncertain Bipartite Graphs |
2022 |
VLDB |
6.3879236e-05 |
| 4,459 |
Efficient Bi-triangle Counting for Large Bipartite Networks |
2021 |
VLDB |
6.1651553e-05 |
| 4,657 |
Dynamic Structural Clustering on Graphs |
2021 |
SIGMOD |
6.0187213e-05 |
| 5,474 |
Efficient Load-Balanced Butterfly Counting on GPU |
2022 |
VLDB |
5.4881807e-05 |
| 5,655 |
Personalized PageRank on Evolving Graphs with an Incremental Index-Update Scheme |
2023 |
SIGMOD |
5.387631e-05 |
| 6,989 |
Effective Indexing for Dynamic Structural Graph Clustering |
2022 |
VLDB |
4.8716197e-05 |
| 7,914 |
Efficient Approximate Algorithms for Empirical Entropy and Mutual Information |
2021 |
SIGMOD |
4.6179608e-05 |
| 8,610 |
Efficient Dynamic Weighted Set Sampling and Its Extension |
2024 |
VLDB |
4.4853485e-05 |
Semantically Similar Papers
| Overall Rank |
Paper |
Year |
Venue |
Pagerank |
| 11,062 |
Maximum Balanced (k, e)-Bitruss Detection in Signed Bipartite Graph |
2024 |
VLDB |
4.1945683e-05 |
| 5,773 |
I/O-Efficient Butterfly Counting at Scale |
2023 |
SIGMOD |
5.3319911e-05 |
| 4,626 |
Efficient Biclique Counting in Large Bipartite Graphs |
2023 |
SIGMOD |
6.0399035e-05 |
| 10,563 |
Efficient Historical Butterfly Counting in Large Temporal Bipartite Networks via Graph Structure-aware Index |
2025 |
VLDB |
4.1945683e-05 |
| 10,078 |
Estimating Biclique Counts with Accuracy Guarantees |
2026 |
SIGMOD |
4.1945683e-05 |
| 10,300 |
Scalable Approximate Biclique Counting over Large Bipartite Graphs |
2026 |
VLDB |
4.1945683e-05 |
| 4,459 |
Efficient Bi-triangle Counting for Large Bipartite Networks |
2021 |
VLDB |
6.1651553e-05 |
| 4,481 |
Efficient Temporal Butterfly Counting and Enumeration on Temporal Bipartite Graphs |
2024 |
VLDB |
6.1485442e-05 |
| 4,171 |
Butterfly Counting on Uncertain Bipartite Graphs |
2022 |
VLDB |
6.3879236e-05 |
| 1,484 |
Vertex Priority Based Butterfly Counting for Large-scale Bipartite Networks |
2019 |
VLDB |
0.00011714263 |