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.4661079e-05
Overall Rank
7,624 | 48.90%
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
182 Querying K-Truss Community in Large and Dynamic Graphs 2014 SIGMOD 0.00026383593
305 Influence Maximization in Near-Linear Time: A Martingale Approach 2015 SIGMOD 0.00021567807
594 Wander Join: Online Aggregation via Random Walks 2016 SIGMOD 0.00015814493
599 Massive Graph Triangulation 2013 SIGMOD 0.00015700433
771 Maximum Biclique Search at Billion Scale 2020 VLDB 0.00014081924
910 Meaningful Change Detection in Structured Data 1997 SIGMOD 0.00013108662
1,227 Vertex Priority Based Butterfly Counting for Large-scale Bipartite Networks 2019 VLDB 0.00011426039
1,590 Effective and Efficient Community Search over Large Heterogeneous Information Networks 2020 VLDB 0.00010110798
1,995 Efficient Algorithms for Densest Subgraph Discovery 2019 VLDB 9.2189157e-05
2,072 Truss Decomposition of Probabilistic Graphs: Semantics and Algorithms 2016 SIGMOD 9.0668141e-05
2,171 Influence Maximization Revisited: Efficient Reverse Reachable Set Generation with Bound Tightened 2020 SIGMOD 8.9117572e-05
2,188 HubPPR: Effective Indexing for Approximate Personalized PageRank 2017 VLDB 8.8879472e-05
2,332 DDSketch: A Fast and Fully-Mergeable Quantile Sketch with Relative-Error Guarantees 2019 VLDB 8.614375e-05
2,339 (p,q)-biclique Counting and Enumeration for Large Sparse Bipartite Graphs 2022 VLDB 8.599495e-05
2,941 Query Driven-Graph Neural Networks for Community Search: From Non-Attributed, Attributed, to Interactive Attributed 2022 VLDB 7.8196527e-05
3,804 Butterfly Counting on Uncertain Bipartite Graphs 2022 VLDB 6.9907371e-05
3,988 Personalized PageRank on Evolving Graphs with an Incremental Index-Update Scheme 2023 SIGMOD 6.8626164e-05
4,057 Efficient Bi-triangle Counting for Large Bipartite Networks 2021 VLDB 6.8140795e-05
4,372 Dynamic Structural Clustering on Graphs 2021 SIGMOD 6.6204444e-05
5,164 Efficient Load-Balanced Butterfly Counting on GPU 2022 VLDB 6.2343301e-05
7,267 Efficient Dynamic Weighted Set Sampling and Its Extension 2024 VLDB 5.5539363e-05
7,309 Effective Indexing for Dynamic Structural Graph Clustering 2022 VLDB 5.5432822e-05
7,970 Efficient Approximate Algorithms for Empirical Entropy and Mutual Information 2021 SIGMOD 5.3997018e-05
Previous Page 1 / 1 Next

Semantically Similar Papers