A Unified Framework for Dense Subgraph Maintenance over Dynamic Bipartite Graphs

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 << d max of the maximum degree holds in practice. Our proposed maintenance algorithms can handle a batch update of multiple edge insertions/deletions simultaneously. Extensive results on large datasets demonstrate that our unified framework efficiently maintains several dense subgraphs and runs faster than state-of-the-art bi-core maintenance algorithms.