Clique
Topic of Graphical models, part of Statistical learning
Clique
| Type | Topic |
| Taught in | Graphical models |
| Part | Statistical learning |
A complete subset of a graph’s vertices, every pair joined by an edge, that cannot be enlarged. By the Hammersley–Clifford theorem a positive density is Markov with respect to a graph exactly when it factorises into functions of the cliques.
In Graphical models
From Graphical models
- Two connected vertices are adjacent. A graph is complete if every node is adjacent to every other node.
- If A\subseteq V, the subgraph G_A=(A,E_A) has E_A=E\cap(A\times A): keep every edge for which both vertices are in A. A subset is complete if it induces a complete subgraph. A complete subset that is maximal with respect to inclusion is a clique: a complete subset that cannot be made into a larger complete subset by adding any vertex.
- In an undirected graph, the boundary \mathrm{bd}(A) of a subset A is the set of vertices in V\setminus A that are adjacent to vertices in A. The closure of A is \mathrm{cl}(A)=A\cup\mathrm{bd}(A).
- A path X_1,\ldots,X_k is a sequence of vertices joined in a sequence: X_i is adjacent to X_{i+1} for i=1,\ldots,k-1. A subset C\subseteq V is a (j,k)-separator if all paths from j to k intersect C. The set C separates A from B if it is a (j,k)-separator for every j\in A and k\in B.
Used in
See also
Hammersley–Clifford · Undirected graph · A zero precision entry is conditional independence · Maximum likelihood for a known graph · Graphical lasso · Markov graphs · Graph terminology · Conditional independence