DBScholar

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
hf1634bfbcde84544
Venue
SIGMOD
Year
2023
Pagerank
5.4868396e-05
Overall Rank
7,602 | 48.89%
DOI
10.1145/3626753

Incoming Non-self Citations Over Time

Authors

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.

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.

Rank Cited Paper Year Venue Pagerank
184 Querying K-Truss Community in Large and Dynamic Graphs 2014 SIGMOD 0.00026100147
320 Influence Maximization in Near-Linear Time: A Martingale Approach 2015 SIGMOD 0.00021143147
596 Wander Join: Online Aggregation via Random Walks 2016 SIGMOD 0.00015785583
600 Massive Graph Triangulation 2013 SIGMOD 0.00015740352
766 Maximum Biclique Search at Billion Scale 2020 VLDB 0.00014118259
908 Meaningful Change Detection in Structured Data 1997 SIGMOD 0.00013157386
1,222 Vertex Priority Based Butterfly Counting for Large-scale Bipartite Networks 2019 VLDB 0.00011463714
1,663 Effective and Efficient Community Search over Large Heterogeneous Information Networks 2020 VLDB 9.9441685e-05
2,042 Efficient Algorithms for Densest Subgraph Discovery 2019 VLDB 9.1416822e-05
2,086 Truss Decomposition of Probabilistic Graphs: Semantics and Algorithms 2016 SIGMOD 9.0689711e-05
2,258 HubPPR: Effective Indexing for Approximate Personalized PageRank 2017 VLDB 8.7385422e-05
2,278 Influence Maximization Revisited: Efficient Reverse Reachable Set Generation with Bound Tightened 2020 SIGMOD 8.7070902e-05
2,325 (p,q)-biclique Counting and Enumeration for Large Sparse Bipartite Graphs 2022 VLDB 8.6310032e-05
2,432 DDSketch: A Fast and Fully-Mergeable Quantile Sketch with Relative-Error Guarantees 2019 VLDB 8.4766851e-05
2,940 Query Driven-Graph Neural Networks for Community Search: From Non-Attributed, Attributed, to Interactive Attributed 2022 VLDB 7.8334815e-05
3,794 Butterfly Counting on Uncertain Bipartite Graphs 2022 VLDB 7.0172514e-05
4,044 Efficient Bi-triangle Counting for Large Bipartite Networks 2021 VLDB 6.8334494e-05
4,264 Personalized PageRank on Evolving Graphs with an Incremental Index-Update Scheme 2023 SIGMOD 6.6978776e-05
4,527 Dynamic Structural Clustering on Graphs 2021 SIGMOD 6.5602226e-05
5,139 Efficient Load-Balanced Butterfly Counting on GPU 2022 VLDB 6.2579755e-05
7,246 Efficient Dynamic Weighted Set Sampling and Its Extension 2024 VLDB 5.5750011e-05
7,290 Effective Indexing for Dynamic Structural Graph Clustering 2022 VLDB 5.5643066e-05
7,965 Efficient Approximate Algorithms for Empirical Entropy and Mutual Information 2021 SIGMOD 5.4161136e-05
Previous Page 1 / 1 Next

Semantically Similar Papers