CLIQUE

In graph theory, a clique in a graph G is a subset of vertices such that every pair of distinct vertices in the subset is connected by an edge. The induced subgraph on the subset is complete. The size of a clique is its number of vertices. A clique is maximal if it cannot be enlarged by including any adjacent vertex, and maximum if no other clique is larger. The clique number ω(G) denotes the size of a largest clique.

Finding a maximum clique is NP-hard; the decision version is NP-complete. Exact algorithms include Bron–Kerbosch with pivoting to enumerate all maximal cliques; other methods use branch-and-bound or dynamic programming on special graph classes.

Applications include network analysis, where cliques identify tightly connected groups; in biology, they appear in protein interaction and gene co-expression networks; in social networks, they model close-knit groups and influence information flow; in data mining, clique-based methods detect dense patterns.

In sociology, a clique is a small, exclusive social group within a larger community, often formed by friends with shared interests or status. Cliques can shape behavior, norms, and information flow, and are studied to understand peer influence and social segregation.