TL;DR
This paper introduces the $(k, s)$-HCore model, a hyperedge-centric approach to community search that captures higher-order group interactions more accurately than traditional vertex-centric models. To find the most relevant results, the authors define the Hyperedge-Centric Minimum Community Search (HMCS) problem and provide an optimized branch-and-bound algorithm (OBBAB) that achieves up to a $10^4$ speedup over baseline methods.
What Problem Does This Paper Address?
Community Search (CS) aims to find a cohesive group of vertices containing a specific query vertex. While well-studied in simple graphs (pairwise relationships), traditional CS fails in hypergraphs, where a single "edge" (hyperedge) can connect any number of vertices (e.g., a research paper with five authors).
The authors identify two major gaps in existing hypergraph CS:
- Ignoring Hyperedge Overlap: Most models are "vertex-centric," focusing on how many neighbors a vertex has. This ignores the "strength" of group interactions—how much different hyperedges overlap and share members.
- Excessive Community Size: Existing methods often return massive communities that are difficult to interpret. Finding the minimum cohesive community is a more useful but computationally harder (NP-Hard) problem.
Methods
The researchers propose a two-pronged solution involving a new structural model and an efficient search algorithm.
1. The $(k, s)$-HCore Model
Instead of looking at vertex degrees, this model focuses on hyperedge interactions:
- Interaction Engagement ($k$): A hyperedge must intersect with at least $k$ other hyperedges.
- Intersection Strength ($s$): Those intersections must share at least $s$ vertices. By combining these, the $(k, s)$-HCore identifies sub-hypergraphs where groups are tightly "locked" together through significant shared membership.
2. The OBBAB Algorithm
Finding the minimum sub-hypergraph that satisfies the $(k, s)$-HCore constraint is NP-Hard. The authors develop an Optimized Branch-and-Bound (OBBAB) algorithm featuring three key techniques: candidate set pruning, lower bound pruning, and strategic branching.
- Candidate Set Pruning: Systematically eliminates hyperedges that cannot possibly be part of a valid $(k, s)$-HCore based on their local connectivity.
- Lower Bound Pruning: Uses a greedy estimation to predict the minimum possible size of a community in a specific search branch. If that estimate exceeds the size of the best community found so far, the branch is discarded.
- Strategic Branching: Instead of picking edges at random, the algorithm uses "connectivity scores" to prioritize hyperedges that are most likely to lead to a small, cohesive community quickly.
Key Results
The study evaluates the model on 10 real-world datasets across six domains, including pharmaceutical, Q&A networks, and academic collaboration (e.g., AMiner with ~27 million edges).
- Cohesion: Communities found by the $(k, s)$-HCore model exhibited twice the "overlapness" (average hyperedges per vertex) compared to traditional $k$-core or $CoCore$ models.
- Efficiency: The OBBAB algorithm outperformed the baseline Branch-and-Bound (BAB) by 2 to 4 orders of magnitude.
- Scalability: While the baseline BAB's runtime increased exponentially with dataset size, OBBAB demonstrated near-linear scalability, making it viable for massive datasets.
- Application Success: Case studies in influence spreading showed that vertices within a $(k, s)$-HCore are more effective "seeds" for information dissemination than those identified by vertex-centric measures.
Limitations and Future Work
Despite massive speedups, the underlying problem remains NP-Hard. Future work could explore attributed hypergraphs or adapt these minimum search techniques to dynamic hypergraphs that evolve over time.
Summary updated