Efficient Computation of Maximum Flexi-Clique in Networks
Song Kim, Hyewon Kim, Kaiqiang Yu, Taejoon Han, Junghoon Kim, Susik Yoon, Jungeun Kim, [0.8em] Department of Computer Science and Engineering, UNIST, Ulsan, South Korea · 2026
Read Efficient Computation of Maximum Flexi-Clique in Networks by Song Kim, Hyewon Kim, Kaiqiang Yu, Taejoon Han, Junghoon Kim, Susik Yoon, Jungeun Kim, [0.8em] Department of Computer Science and Engineering, UNIST, Ulsan, South Korea (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-10459.txt.
Description
Song Kim and six co-authors improve the search for tightly knit groups inside large networks in a 2026 paper. Classic models like cliques and quasi-cliques use fixed density thresholds, ignoring how connectivity naturally thins as a group grows. The flexi-clique model fixes this with a degree requirement that grows more slowly than group size.
The paper proves the maximum flexi-clique problem is computationally hard and studies its unusual non-hereditary structure. It then offers two recipes. One is a fast heuristic that seeds from network cores and prunes with connectivity awareness. The other is an exact branch-and-bound method with several pruning rules. Tests on real and mock networks show the heuristic nears optimal quality at far lower cost, while the exact method stays fast.
Catalog record
| CREATOR | Song Kim, Hyewon Kim, Kaiqiang Yu, Taejoon Han, Junghoon Kim, Susik Yoon, Jungeun Kim, [0.8em] Department of Computer Science and Engineering, UNIST, Ulsan, South Korea |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 68 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-10459