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 |
|---|---|---|---|---|
| 184 | Querying K-Truss Community in Large and Dynamic Graphs | 2014 | SIGMOD | 0.00026100147 |
| 758 | Streaming Algorithms for k-core Decomposition | 2013 | VLDB | 0.00014188163 |
| 766 | Maximum Biclique Search at Billion Scale | 2020 | VLDB | 0.00014118259 |
| 1,317 | Incremental Graph Pattern Matching | 2011 | SIGMOD | 0.00011050011 |
| 2,285 | Unboundedness and Efficiency of Truss Maintenance in Evolving Graphs | 2019 | SIGMOD | 8.6948587e-05 |
| 2,851 | Incremental Graph Computations: Doable and Undoable | 2017 | SIGMOD | 7.9419904e-05 |
| 5,629 | Efficient Core Maintenance in Large Bipartite Graphs | 2023 | SIGMOD | 6.0592611e-05 |
| 7,547 | Efficient Triangle-Connected Truss Community Search In Dynamic Graphs | 2023 | VLDB | 5.4981692e-05 |
| 7,807 | A Counting-based Approach for Efficient k-Clique Densest Subgraph Discovery | 2024 | SIGMOD | 5.4495451e-05 |
| 8,066 | Efficient Star-based Truss Maintenance on Dynamic Graphs | 2023 | SIGMOD | 5.3950351e-05 |
| 10,562 | Efficient and Scalable Directed Densest Subgraph Discovery | 2026 | SIGMOD | 4.9793485e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 766 | Maximum Biclique Search at Billion Scale | 2020 | VLDB |
| 2 | 4,044 | Efficient Bi-triangle Counting for Large Bipartite Networks | 2021 | VLDB |
| 3 | 10,519 | Zero-Redundancy Search for Bi-Components in Bipartite Graphs | 2026 | SIGMOD |
| 4 | 10,636 | Efficient Influential Community Search over Dynamic Graphs | 2026 | SIGMOD |
| 5 | 2,869 | Hierarchical Core Maintenance on Large Dynamic Graphs | 2021 | VLDB |
| 6 | 8,318 | Efficient Index for Temporal Core Queries over Bipartite Graphs | 2024 | VLDB |
| 7 | 9,865 | Density Decomposition of Bipartite Graphs | 2025 | SIGMOD |
| 8 | 10,612 | A Unified Framework for Dense Subgraph Maintenance over Dynamic Bipartite Graphs | 2026 | SIGMOD |
| 9 | 10,860 | Maximum Defective Biclique Search in Large Bipartite Graphs | 2026 | VLDB |
| 10 | 5,629 | Efficient Core Maintenance in Large Bipartite Graphs | 2023 | SIGMOD |