Scalable method maintains dense groups in changing hypergraphs
Scalable Approximate Algorithm for Dynamic Densest Subhypergraphs with Solution-Guided Maintenance
Databases
Summary
Finding tightly connected groups in data that links many things at once can be very hard, especially when the connections keep changing. The authors created CAP, a fast and scalable method that keeps track of these dense groups even as connections are added or removed. It uses smart checks to only do work when necessary, making it much faster than previous methods. CAP also works well on simpler networks, not just complex hypergraphs.
What this means in practice
- •For network analysis teams: Quickly update and find closely connected groups in large dynamic networks involving multiple entities interacting simultaneously.
- •For social media platform engineers: Maintain and detect dense communities or group interactions efficiently despite frequent changes in user connections or group activities.$Commercial implications: Enables real-time community tracking and recommendations by efficiently handling changes in social interaction data.
Authors
Jingbang Chen, Chenhao Ma, Yingli Zhou
Abstract
Hypergraphs model interactions involving groups of entities, and finding highly connected groups is a fundamental task in analyzing these data. When interactions arrive and expire, maintaining a dense group can require frequent and expensive changes to the underlying representation. We propose CAP, a scalable algorithm that explicitly maintains a $(1+ε)$-approximate densest subhypergraph under hyperedge insertions and deletions. The algorithm keeps a solution candidate together with an endpoint allocation that bounds the optimum density. The candidate's density guides maintenance: an update triggers repair only when this bound is too large to establish the required approximation. Local searches redistribute load or find a denser candidate, allowing CAP to retain useful solutions across many updates. We give an analysis that relates maintenance work to the size of the regions searched and the density lost by the maintained solution. It identifies conditions under which local repair remains inexpensive and provides a theoretical explanation for the observed efficiency. Experiments on real-world hypergraphs show speedups of up to nearly four orders of magnitude over the evaluated dynamic baselines, while supporting frequent queries and high accuracy. CAP also remains competitive with specialized dynamic graph methods on ordinary graphs, with speedups of up to approximately $64\times$ on the tested workloads.