12 Algoritmos de Descoberta Causal

Algoritmo SGS

1. 1.
   ​

   Inicie um grafo não direcionado completo em ${\mathcal{V}}$.

2. 2.
   ​

   Para cada $V_{1},V_{2}\in{\mathcal{V}}$, se $H_{0}:V_{1}\perp\!\!\!\!\perp V_{2}|S$ é rejeitada para algum $S\subseteq{\mathcal{V}}-\{V_{1},V_{2}\}$, retire a aresta $\{V_{1},V_{2}\}$.

3. 3.
   ​

   Para todos $V_{1},V_{2},V_{3}\in{\mathcal{V}}$ tais que $\{V_{1},V_{2}\}$ e $\{V_{2},V_{3}\}$ são adjacentes, mas $\{V_{1},V_{3}\}$ não o são, caso exista $S\subseteq\{V_{2}\}\cup{\mathcal{V}}-\{V_{1},V_{3}\}$ tal que $H_{0}:V_{1}\perp\!\!\!\!\perp V_{2}|S$ não é rejeitada, direcione as arestas $V_{1}\rightarrow V_{2}\leftarrow V_{3}$.

4. 4.
   ​

   Repetir até que não haja mudanças:

   1. (a)
      ​

      Se $A\rightarrow B$, $B$ e $C$ são adjacentes e não direcionados e $A$ e $C$ não são adjacentes, direcione $B\rightarrow C$.

   2. (b)
      ​

      Se $B$ é descendente de $A$ e $\{A,B\}$ são adjacentes, direcione $A\rightarrow B$.

Algoritmo PC

1. 1.
   ​

   Inicie um grafo não direcionado completo em ${\mathcal{V}}$, ${\mathcal{G}}$.

2. 2.
   ​

   Inicialize $n=0$.

3. 3.
   ​

   Enquanto houver um vértice $X\in{\mathcal{V}}$ com $|Adj_{{\mathcal{G}}}(X)|>n+1$:

   1. (a)
      ​

      Para cada $X\in{\mathcal{V}}$ com $|Adj_{{\mathcal{G}}}(X)|\geq n+1$, cada $Y\in Adj_{{\mathcal{G}}}(X)$ e $S\subseteq Adj_{{\mathcal{G}}}(X)-\{Y\}$ em que $|S|=n$, se $H_{0}:X\perp\!\!\!\!\perp Y|S$ é rejeitada, então retire a aresta $\{X,Y\}$ de ${\mathcal{G}}$ e defina $Sep(\{X,Y\})=S$.

   2. (b)
      ​

      Defina $n=n+1$.

4. 4.
   ​

   Para cada $X,Y,Z\in{\mathcal{V}}$ tais que $\{X,Y\}$ e $\{Y,Z\}$ são adjacentes, mas $\{X,Z\}$ não o são e $Y\notin Sep(\{X,Z\})$, oriente $X\rightarrow Y\leftarrow Z$.

5. 5.
   ​

   Repetir até que não haja mudanças:

   1. (a)
      ​

      Se $A\rightarrow B$, $B$ e $C$ são adjacentes e não direcionados e $A$ e $C$ não são adjacentes, direcione $B\rightarrow C$.

   2. (b)
      ​

      Se $B$ é descendente de $A$ e $\{A,B\}$ são adjacentes, direcione $A\rightarrow B$.