Flexi-clique: Exploring Flexible and Sub-linear Clique Structures

Identifying cohesive subgraphs within networks is a fundamental problem in graph theory, relevant to various domains. The traditional clique problem, which finds fully connected subgraphs, often faces limitations due to its strict connectivity requirements. This paper introduces a novel degree-based relaxation model called Flexi-clique, where the degree constraint is adjusted sub-linearly based on the subgraph size. We establish that the maximum Flexi-clique problem is NP-hard and propose an efficient and effective peeling algorithm to address it. Our extensive experimental evaluation of real-world datasets demonstrates the effectiveness and efficiency of our approach in discovering large, cohesive subgraphs in networks.