EUVIMEDEUVIMED entdecken
Crossref

A Unified Framework for Dense Subgraph Maintenance over Dynamic Bipartite Graphs

Zitan Sun, Zihan Jia, Hong Cheng, Xin Huang, Jeffrey Xu Yu

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →