Efficient Computation of Maximum Flexi-Clique in Networks
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910018684583936 |
|---|---|
| author | Kim, Song Kim, Hyewon Yu, Kaiqiang Han, Taejoon Kim, Junghoon Yoon, Susik Kim, Jungeun |
| author_facet | Kim, Song Kim, Hyewon Yu, Kaiqiang Han, Taejoon Kim, Junghoon Yoon, Susik Kim, Jungeun |
| contents | Discovering large cohesive subgraphs is a key task for graph mining. Existing models, such as clique, k-plex, and γ-quasi-clique, use fixed density thresholds that overlook the natural decay of connectivity as the subgraph size increases. The Flexi-clique model overcomes this limitation by imposing a degree constraint that grows sub-linearly with subgraph size. We provide the algorithmic study of Flexi-clique, proving its NP-hardness and analysing its non-hereditary properties. To address its computational challenge, we propose the Flexi-Prune Algorithm FPA, a fast heuristic using core-based seeding and connectivity-aware pruning, and the Efficient Branch-and-Bound Algorithm EBA, an exact framework enhanced with multiple pruning rules. Experiments on large real-world and synthetic networks demonstrate that FPA achieves near-optimal quality at much lower cost, while EBA efficiently computes exact solutions. Flexi-clique thus provides a practical and scalable model for discovering large, meaningful subgraphs in complex networks. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_10459 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Efficient Computation of Maximum Flexi-Clique in Networks Kim, Song Kim, Hyewon Yu, Kaiqiang Han, Taejoon Kim, Junghoon Yoon, Susik Kim, Jungeun Social and Information Networks Discovering large cohesive subgraphs is a key task for graph mining. Existing models, such as clique, k-plex, and γ-quasi-clique, use fixed density thresholds that overlook the natural decay of connectivity as the subgraph size increases. The Flexi-clique model overcomes this limitation by imposing a degree constraint that grows sub-linearly with subgraph size. We provide the algorithmic study of Flexi-clique, proving its NP-hardness and analysing its non-hereditary properties. To address its computational challenge, we propose the Flexi-Prune Algorithm FPA, a fast heuristic using core-based seeding and connectivity-aware pruning, and the Efficient Branch-and-Bound Algorithm EBA, an exact framework enhanced with multiple pruning rules. Experiments on large real-world and synthetic networks demonstrate that FPA achieves near-optimal quality at much lower cost, while EBA efficiently computes exact solutions. Flexi-clique thus provides a practical and scalable model for discovering large, meaningful subgraphs in complex networks. |
| title | Efficient Computation of Maximum Flexi-Clique in Networks |
| topic | Social and Information Networks |
| url | https://arxiv.org/abs/2602.10459 |