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
6822
Venue
SIGMOD
Year
2023
Pagerank
5.6127752e-05
Overall Rank
7,455 | 48.86%
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
189 Querying K-Truss Community in Large and Dynamic Graphs 2014 SIGMOD 0.00026114928
315 Influence Maximization in Near-Linear Time: A Martingale Approach 2015 SIGMOD 0.00021436156
593 Wander Join: Online Aggregation via Random Walks 2016 SIGMOD 0.00016027871
594 Massive Graph Triangulation 2013 SIGMOD 0.00015979077
780 Maximum Biclique Search at Billion Scale 2020 VLDB 0.00014091815
881 Meaningful Change Detection in Structured Data 1997 SIGMOD 0.00013430652
1,211 Vertex Priority Based Butterfly Counting for Large-scale Bipartite Networks 2019 VLDB 0.00011648789
1,647 Effective and Efficient Community Search over Large Heterogeneous Information Networks 2020 VLDB 0.00010125633
2,024 Efficient Algorithms for Densest Subgraph Discovery 2019 VLDB 9.2907829e-05
2,225 HubPPR: Effective Indexing for Approximate Personalized PageRank 2017 VLDB 8.9183159e-05
2,294 (p,q)-biclique Counting and Enumeration for Large Sparse Bipartite Graphs 2022 VLDB 8.7939844e-05
2,320 Influence Maximization Revisited: Efficient Reverse Reachable Set Generation with Bound Tightened 2020 SIGMOD 8.7576221e-05
2,323 Truss Decomposition of Probabilistic Graphs: Semantics and Algorithms 2016 SIGMOD 8.750808e-05
2,455 DDSketch: A Fast and Fully-Mergeable Quantile Sketch with Relative-Error Guarantees 2019 VLDB 8.5552968e-05
2,873 Query Driven-Graph Neural Networks for Community Search: From Non-Attributed, Attributed, to Interactive Attributed 2022 VLDB 8.0099557e-05
3,723 Butterfly Counting on Uncertain Bipartite Graphs 2022 VLDB 7.1725638e-05
3,997 Efficient Bi-triangle Counting for Large Bipartite Networks 2021 VLDB 6.9679551e-05
4,423 Dynamic Structural Clustering on Graphs 2021 SIGMOD 6.7107949e-05
4,714 Personalized PageRank on Evolving Graphs with an Incremental Index-Update Scheme 2023 SIGMOD 6.5497309e-05
5,317 Efficient Load-Balanced Butterfly Counting on GPU 2022 VLDB 6.2685847e-05
7,141 Effective Indexing for Dynamic Structural Graph Clustering 2022 VLDB 5.6920203e-05
7,142 Efficient Dynamic Weighted Set Sampling and Its Extension 2024 VLDB 5.6917227e-05
7,807 Efficient Approximate Algorithms for Empirical Entropy and Mutual Information 2021 SIGMOD 5.5404259e-05
Previous Page 1 / 1 Next

Semantically Similar Papers