Order-based Algorithms for Efficient Core Maintenance in Large Bipartite Graphs
Summary: The paper gives the first boundedness analysis of dynamic bi-core maintenance, showing deletions are bounded but insertions are inherently unbounded. It introduces BD-Order plus an order-based update algorithm (with an auxiliary deletion structure) that sharply localizes affected vertices and yields up to 100× speedups. (summarized by gpt-5-mini on Apr 11 2026)
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
Authors
- 1. Qiaoyuan Yang (Peking University)
- 2. Wensheng Luo (Hunan University)
- 3. Yixiang Fang (Chinese University of Hong Kong)
- 4. Yuanyuan Zeng (Chinese University of Hong Kong)
BibTeX Citation
@inproceedings{yang_sigmod26,
title = {{Order-based Algorithms for Efficient Core Maintenance in Large Bipartite Graphs}},
author = {Yang, Qiaoyuan and Luo, Wensheng and Fang, Yixiang and Zeng, Yuanyuan},
series = {{SIGMOD} '26},
booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
publisher = {Association for Computing Machinery},
doi = {10.1145/3786674},
url = {https://dl.acm.org/doi/10.1145/3786674},
year = {2026}
}Incoming Citations (Sorted by Pagerank)
Showing 0 of 0 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 11 of 11 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 |
| 780 | Maximum Biclique Search at Billion Scale | 2020 | VLDB | 0.00014091815 |
| 793 | Streaming Algorithms for k-core Decomposition | 2013 | VLDB | 0.00013978774 |
| 1,296 | Incremental Graph Pattern Matching | 2011 | SIGMOD | 0.00011269684 |
| 2,243 | Unboundedness and Efficiency of Truss Maintenance in Evolving Graphs | 2019 | SIGMOD | 8.8813183e-05 |
| 2,798 | Incremental Graph Computations: Doable and Undoable | 2017 | SIGMOD | 8.1129891e-05 |
| 5,674 | Efficient Core Maintenance in Large Bipartite Graphs | 2023 | SIGMOD | 6.1255689e-05 |
| 7,408 | Efficient Triangle-Connected Truss Community Search In Dynamic Graphs | 2023 | VLDB | 5.6243648e-05 |
| 8,011 | Efficient Star-based Truss Maintenance on Dynamic Graphs | 2023 | SIGMOD | 5.5074939e-05 |
| 9,519 | A Counting-based Approach for Efficient k-Clique Densest Subgraph Discovery | 2024 | SIGMOD | 5.2562724e-05 |
| 10,363 | Efficient and Scalable Directed Densest Subgraph Discovery | 2026 | SIGMOD | 5.093636e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 11,173 | Efficient Maximal Biplex Enumerations with Improved Worst-Case Time Guarantee | 2024 | SIGMOD |
| 2 | 780 | Maximum Biclique Search at Billion Scale | 2020 | VLDB |
| 3 | 3,997 | Efficient Bi-triangle Counting for Large Bipartite Networks | 2021 | VLDB |
| 4 | 10,308 | Zero-Redundancy Search for Bi-Components in Bipartite Graphs | 2026 | SIGMOD |
| 5 | 2,826 | Hierarchical Core Maintenance on Large Dynamic Graphs | 2021 | VLDB |
| 6 | 10,448 | Efficient Influential Community Search over Dynamic Graphs | 2026 | SIGMOD |
| 7 | 8,149 | Efficient Index for Temporal Core Queries over Bipartite Graphs | 2024 | VLDB |
| 8 | 9,689 | Density Decomposition of Bipartite Graphs | 2025 | SIGMOD |
| 9 | 10,423 | A Unified Framework for Dense Subgraph Maintenance over Dynamic Bipartite Graphs | 2026 | SIGMOD |
| 10 | 5,674 | Efficient Core Maintenance in Large Bipartite Graphs | 2023 | SIGMOD |