Luo, Qi, Dongxiao Yu, Zhipeng Cai, Xuemin Lin, Guanghui Wang, and Xiuzhen Cheng. "Toward maintenance of hypercores in large-scale dynamic hypergraphs." The VLDB Journal 32, no. 3 (2023): 647-664.
2024年10月28日

【Abstract】  In this paper, we study hypercore maintenance in large-scale dynamic hypergraphs. A hypergraph, whose hyperedges may contain a set of vertices rather than two vertices in pairwise graphs, can represent complex interactions in more sophisticated applications. However, the exponential number of hyperedges incurs unaffordable costs to recompute the hypercore number of vertices and hyperedges when updating a hypergraph. This motivates us to propose an efficient approach for exact hypercore maintenance with the intention of significantly reducing the hypercore updating time comparing with recomputation approaches. The proposed algorithms can pinpoint the vertices and hyperedges whose hypercore numbers have to be updated by only traversing a small sub-hypergraph. We also propose an index called Core-Index that can facilitate our maintenance algorithms. Extensive experiments on real-world and temporal hypergraphs demonstrate the superiority of our algorithms in terms of efficiency.