A Unified Framework for Dense Subgraph Maintenance over Dynamic Bipartite Graphs
Proceedings of the ACM on Management of Data · 02.04.2026 · 4 (1) · 1-27
DOI: 10.1145/3786618 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 07.04.2026. Verfasst von Zitan Sun und 4 weiteren Autor:innen. Die Arbeit nennt 53 Literaturangaben. Gefördert von: Research Grants Council of the Hong Kong Special Administrative Region, China.
Abstract (Originalsprache)
To identify dense subgraphs, many specific-subgraph algorithms are developed for decomposition and maintenance on dynamic graphs. However, it suffers from two significant limitations. First, for each kind of subgraphs, it needs the development of specific maintenance algorithms, which is a costly effort. This may also lead to potentially missing solutions for an existing subgraph (e.g., k -nucleus maintenance). Second, no commonly useful properties and rules can be derived from these quite different algorithms. To address these bottlenecks, we propose a unified framework for dense subgraph maintenance over dynamic bipartite graphs. We first give a definition of (α, β)-core as bi-core and formulate the problem of bi-core maintenance. To our best knowledge, we are the first to propose the maintenance equivalence of bi-core to other subgraphs, e.g., k -core, k -truss, bi-truss, and k -nucleus. To handle the update efficiently, we propose a novel index structure of bi-core and onion layers, which finely decomposes one (α, β)-core into different levels of layers. This theoretically improves state-of-the-art bi-core maintenance algorithms from unbounded to bounded. However, due to two search dimensions of (α, β)-cores w.r.t. parameters α and β, it brings significant challenges for fast update. To tackle it, we develop a novel κBCO-index for fast maintenance by adding a shortcut search of κ-direction. This reorganizes bi-core onion layers and reduces the space complexity from O(nd max ) to O(nk max ), where n is the size of vertices, and the cardinality of κ-direction k max
Förderung
- Research Grants Council of the Hong Kong Special Administrative Region, China
Zitieren
APA
Sun, Z., Jia, Z., Cheng, H., Huang, X., & Yu, J. X. (2026). A Unified Framework for Dense Subgraph Maintenance over Dynamic Bipartite Graphs. Proceedings of the ACM on Management of Data, 4(1), 1-27. https://doi.org/10.1145/3786618
Vancouver
Sun Z, Jia Z, Cheng H, Huang X, Yu JX. A Unified Framework for Dense Subgraph Maintenance over Dynamic Bipartite Graphs. Proceedings of the ACM on Management of Data. 2026;4(1):1-27. doi:10.1145/3786618
BibTeX
@article{Sun2026,
author = {Sun, Zitan and Jia, Zihan and Cheng, Hong and Huang, Xin and Yu, Jeffrey Xu},
title = {A Unified Framework for Dense Subgraph Maintenance over Dynamic Bipartite Graphs},
journal = {Proceedings of the ACM on Management of Data},
year = {2026},
volume = {4},
number = {1},
pages = {1--27},
doi = {10.1145/3786618}
}
EUVIMED