Constrained Reachability Queries on Hypergraphs
摘要
The hypergraph, which captures group-wise relationships among multiple entities, effectively addresses the limitation of conventional graphs that only represent pairwise relationships. It has been widely applied in querying and mining collaboration networks, social networks, protein interaction networks, and so on. In this paper, we study the reachability on hypergraphs. We formally define the reachability problem with a specified constraint on the edges of the hypergraphs. To overcome the time inefficiency of traversal-based methods, and the space overhead and poor update support of union-find and 2-hop-based approaches, we propose a novel tree-based index \(\textsf{HRTree}\) for efficient hypergraph reachability queries, achieving \(O(\log (|E|))\) query time and O(|E|) space complexity, where E denotes the hyperedge set of a hypergraph. Furthermore, we design an incremental maintenance method for \(\textsf{HRTree}\) to support hypergraph updates without index reconstruction. The maintenance time is only related to the influence region of updates. Extensive experiments on 8 real-world datasets demonstrate that our algorithm outperforms baseline methods in both time and space efficiency. Moreover, \(\textsf{HRTree}\) efficiently supports updates on hypergraphs.