Abstract
We propose neighborhood-based core decomposition: a novel way of decomposing hypergraphs into hierarchical neighborhood-cohesive subhypergraphs. Alternative approaches to decomposing hypergraphs, e.g., reduction to clique or bipartite graphs, are not meaningful in certain applications, the later also results in inefficient decomposition; while existing degree-based hypergraph decomposition does not distinguish nodes with different neighborhood sizes. Our case studies show that the proposed decomposition is more effective than degree and clique graph-based decompositions in disease intervention and in extracting provably approximate and application-wise meaningful densest subhypergraphs. We propose three algorithms: Peel, its efficient variant E-Peel, and a novel local algorithm: Localcore with parallel implementation. Our most efficient parallel algorithm Local-core(P) decomposes hypergraph with 27 M nodes and 17 M hyperedges in-memory within 91 seconds by adopting various optimizations. Finally, we develop a new hypergraph-core model, the (neighborhood, degree)-core by considering both neighborhood and degree constraints, design its decomposition algorithm Localcore+Peel, and demonstrate its superiority in spreading diffusion.
Original language | English |
---|---|
Journal | Proceedings of the VLDB Endowment |
Volume | 16 |
Issue number | 9 |
Pages (from-to) | 2061-2074 |
Number of pages | 14 |
ISSN | 2150-8097 |
DOIs | |
Publication status | Published - 2023 |
Event | 49th International Conference on Very Large Data Bases, VLDB 2023 - Vancouver, Canada Duration: 28 Aug 2023 → 1 Sept 2023 |
Conference
Conference | 49th International Conference on Very Large Data Bases, VLDB 2023 |
---|---|
Country/Territory | Canada |
City | Vancouver |
Period | 28/08/2023 → 01/09/2023 |