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

CREATORSong 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
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE68 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-10459

Browse the full library · About the Tower of Babel