What are B-sets?
For a node \(v\) that has children,
the B-sets are the intersections of the parents sets of the children of
\(v\) with \(v\)’s own parents sets.
They can be obtained using the function
DAG = create_empty_DAG(6)
DAG = bnlearn::set.arc(DAG, 'U1', 'U5')
DAG = bnlearn::set.arc(DAG, 'U2', 'U5')
DAG = bnlearn::set.arc(DAG, 'U3', 'U5')
DAG = bnlearn::set.arc(DAG, 'U4', 'U5')
DAG = bnlearn::set.arc(DAG, 'U1', 'U6')
DAG = bnlearn::set.arc(DAG, 'U2', 'U6')
DAG = bnlearn::set.arc(DAG, 'U5', 'U6')
DAG |> bnlearn::as.igraph() |>
igraph::plot.igraph(size = 10, label.cex = 1, layout = igraph::layout_as_tree
)
find_B_sets_v(DAG, v = 'U5')
#> U1 U2 U3 U4
#> Empty B-set FALSE FALSE FALSE FALSE
#> U6 TRUE TRUE FALSE FALSE
#> Full B-set TRUE TRUE TRUE TRUE
This means that for v = U5, the B-sets corresponding to
U6 is made up of U1 and U2. By
convention, the empty set and the full set of parents of v
are always added. To obtain all the B-sets of the nodes of the graph,
the following code can be used:
B_sets = find_B_sets(DAG)
B_sets$B_sets
#> $U1
#>
#> [1,]
#> [2,]
#> [3,]
#> [4,]
#>
#> $U2
#>
#> [1,]
#> [2,]
#> [3,]
#> [4,]
#>
#> $U3
#>
#> [1,]
#> [2,]
#> [3,]
#>
#> $U4
#>
#> [1,]
#> [2,]
#> [3,]
#>
#> $U5
#> U1 U2 U3 U4
#> Empty B-set FALSE FALSE FALSE FALSE
#> U6 TRUE TRUE FALSE FALSE
#> Full B-set TRUE TRUE TRUE TRUE
#>
#> $U6
#> U1 U2 U5
#> Empty B-set FALSE FALSE FALSE
#> Full B-set TRUE TRUE TRUE
Interfering v-structures
An interfering v-structure is by definition a case when two B-sets of
the same node are not comparable (for the inclusion order, i.e. neither
of them is included in the other one).
Here is an example of a graph with interfering v-structures.
DAG = create_empty_DAG(5)
DAG = bnlearn::set.arc(DAG, 'U1', 'U3')
DAG = bnlearn::set.arc(DAG, 'U2', 'U3')
DAG = bnlearn::set.arc(DAG, 'U1', 'U4')
DAG = bnlearn::set.arc(DAG, 'U3', 'U4')
DAG = bnlearn::set.arc(DAG, 'U2', 'U5')
DAG = bnlearn::set.arc(DAG, 'U3', 'U5')
DAG |> bnlearn::as.igraph() |> igraph::plot.igraph()
find_B_sets_v(DAG, v = 'U3')
#> U1 U2
#> Empty B-set FALSE FALSE
#> U4 TRUE FALSE
#> U5 FALSE TRUE
#> Full B-set TRUE TRUE
To check automatically that the B-sets are not comparable (i.e. the
existence of a v-structure), we can do:
find_B_sets_v(DAG, v = 'U3') |>
B_sets_are_increasing()
#> [1] FALSE
More generally, the presence of v-structures can be automatically
checked using the following function:
has_interfering_vstrucs(DAG)
#> [1] TRUE
To find the interfering v-structures at a given node, we can use:
find_B_sets_v(DAG, v = 'U3') |>
find_interfering_v_from_B_sets() |>
print()
#> A B parents.A.but.not.parents.B parents.B.but.not.parents.A
#> 1 U4 U5 U1 U2
To fix this, we can add one of the missing arcs. This makes the
interfering v-structure disappear.
DAG = bnlearn::set.arc(DAG, 'U1', 'U5')
has_interfering_vstrucs(DAG)
#> [1] FALSE
In this case, the B-sets are:
find_B_sets_v(DAG, v = 'U3')
#> U1 U2
#> Empty B-set FALSE FALSE
#> U4 TRUE FALSE
#> U5 TRUE TRUE
#> Full B-set TRUE TRUE
B-sets cuts
If there are no interfering v-structures, the B-sets are sorted. We
can then get their increments as follows:
find_B_sets_v(DAG, v = 'U3') |>
B_sets_cut_increments()
#> [[1]]
#> [1] "U1"
#>
#> [[2]]
#> [1] "U2"
#>
#> [[3]]
#> character(0)
In this case, the B-sets of U5 and the full B-set are
identical. Therefore, the last increment is the empty character vector.
It can be nice sometimes to make the B-sets unique so as to avoid
this.
B_sets_unique = find_B_sets_v(DAG, v = 'U3') |>
B_sets_make_unique()
print(B_sets_unique)
#> nodes U1 U2
#> Empty B-set Empty B-set FALSE FALSE
#> U4 U4 TRUE FALSE
#> U5 U5, Full.... TRUE TRUE
B_sets_cut_increments(B_sets_unique)
#> [[1]]
#> [1] "U1"
#>
#> [[2]]
#> [1] "U2"
# Setting back the options to what they were before (following CRAN's policy)
options(old)