quasiclique

Quasiclique, also spelled quasi-clique, is a relaxed notion of a clique in graph theory. It refers to a subset of vertices whose induced subgraph is densely connected, but not necessarily complete. The term is used in areas like network analysis and bioinformatics to identify dense regions in graphs where exact cliques may be rare due to noise or missing data.

Formal definitions: For a graph G=(V,E) and a subset S⊆V with k=|S|, S is a γ-quasi-clique if the induced subgraph G[S] has at least γ·C(k,2) edges, where γ∈(0,1]. Equivalently, the average internal degree in G[S] is at least γ(k−1). In some literature, a related notion is an ε-quasi-clique requiring every vertex in S have degree at least (1−ε)(k−1) within S; these two definitions are close but not identical.

Relation to cliques and variants: A clique corresponds to γ=1. Quasi-cliques can be defined with density or minimum-degree criteria, and the particular definition is chosen to suit application or algorithmic needs.

Algorithmic and practical considerations: The problem of finding the largest γ-quasi-clique or determining whether a graph contains one of size k above a threshold is computationally challenging (NP-hard) in many settings. As a result, practical approaches use heuristics, approximation algorithms, or focus on specific graph classes. Quasi-cliques are widely used in data mining to uncover dense subnetworks; they can be more robust to missing edges than strict cliques.