next | previous | forward | backward | up | top | index | toc | Macaulay2 web site
GraphicalModels :: localMarkov

localMarkov -- local Markov statements for a graph or a directed graph

Synopsis

Description

Given an undirected graph G, a local Markov statement is of the form {v, non-neighbours(v), neighbours(v)}. That is, every vertex v of G is independent of its non-neighbours given its neighbours.

For example, for the undirected 5-cycle graph G, that is, the graph on 5 vertices with a---b---c---d---e---a, we get the following local Markov statements:

i1 : G = graph({{a,b},{b,c},{c,d},{d,e},{e,a}})

o1 = Graph{a => {b, e}}
           b => {a, c}
           c => {b, d}
           d => {c, e}
           e => {a, d}

o1 : Graph
i2 : localMarkov G

o2 = {{{a}, {c, d}, {e, b}}, {{b, c}, {e}, {d, a}}, {{a, e}, {c}, {d, b}},
     ------------------------------------------------------------------------
     {{b}, {d, e}, {c, a}}, {{a, b}, {d}, {c, e}}}

o2 : List

Given a directed graph G, local Markov statements are of the form {v, nondescendents(v) - parents(v), parents(v)}. In other words, every vertex v of G is independent of its nondescendents (excluding parents) given its parents.

For example, given the digraph D on 7 vertices with edges 1 →2, 1 →3, 2 →4, 2 →5, 3 →5, 3 →6, 4 →7, 5 →7, and 6→7, we get the following local Markov statements:

i3 : D = digraph {{1,{2,3}}, {2,{4,5}}, {3,{5,6}}, {4,{7}}, {5,{7}},{6,{7}},{7,{}}}

o3 = Digraph{1 => {2, 3}}
             2 => {4, 5}
             3 => {5, 6}
             4 => {7}
             5 => {7}
             6 => {7}
             7 => {}

o3 : Digraph
i4 : netList pack (3, localMarkov D)

     +------------------------+------------------------+---------------------------+
o4 = |{{1, 3, 5, 6}, {4}, {2}}|{{1, 2, 4, 5}, {6}, {3}}|{{1, 2, 3}, {7}, {4, 5, 6}}|
     +------------------------+------------------------+---------------------------+
     |{{1, 4, 6}, {5}, {2, 3}}|{{2}, {3, 6}, {1}}      |{{2, 4}, {3}, {1}}         |
     +------------------------+------------------------+---------------------------+
This method displays only non-redundant statements. In general, given a set S of conditional independent statements and a statement s, then we say that s is a a redundant statement if s can be obtained from the statements in S using the semigraphoid axioms of conditional independence: symmetry, decomposition, weak union, and contraction as described in Section 1.1 of Judea Pearl, Causality: models, reasoning, and inference, Cambridge University Press. We do not use the intersection axiom since it is only valid for strictly positive probability distributions.

See also

  • pairMarkov -- pairwise Markov statements for a graph or a directed graph
  • globalMarkov -- global Markov statements for a graph or a directed graph

Ways to use localMarkov :

  • localMarkov(Digraph)
  • localMarkov(Graph)