Graph terminology
Section of Graphical models, part of Statistical learning
Graph terminology
| Type | Section |
| Taught in | Graphical models |
| Part | Statistical learning |
Definition 1 (Undirected graph) A graph G=(V,E) is a set of vertices, or nodes, V along with a set of edges E\subseteq V\times V joining pairs of vertices. Self-edges are excluded, and only undirected edges are considered: (j,k)\in E implies (k,j)\in E. Edges are listed in any convenient order of the pair, with the reverse understood to be present.
- 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.
In a graphical model each vertex represents a random variable, and an edge permits conditional dependence between its endpoints. In a minimal Gaussian concentration graph with nonzero precision entries on edges, the edge represents conditional dependence given all remaining variables. The absence of an edge indicates that the two variables are conditionally independent given the values of all the other variables. For many models the conditioning set is smaller than the full remainder, and the graph says which set.
The six-vertex graph used below has edges 12, 13, 23, 24, 34, 45, 46 and 56. Its cliques are \{1,2,3\}, \{2,3,4\} and \{4,5,6\}. Vertex 4 separates the left group \{1,2,3\} from vertices 5 and 6.
Used in
See also
Undirected graph · Hammersley–Clifford · A zero precision entry is conditional independence · Maximum likelihood for a known graph · Graphical lasso · Markov graphs · Conditional independence · Markov properties and factorisation