Bayesian Networks in the Absence of Temporal Information - Bayesian Networks in R: With Applications in Systems Biology - page 16

Generalizing this simple example, it can be shown that the only arcs whose di-
rection is needed to identify an equivalence class are those belonging to at least
one v-structure ( Chickering , 1995 ). 2 Equivalence classes are usually represented by
completed partially directed acyclic graphs (CPDAGs), where only arcs belonging
to v-structures and those that would introduce additional v-structures or cycles are
directed. Such arcs are called compelled , since their direction is determined by the
equivalence class even though they are not part of any v-structure. Changing the
direction of any other, non-compelled arc results in another network in the same
equivalence class as long as it does not introduce any new v-structure or in any
cycle.

2.1.4 Markov Blankets

Another fundamental quantity that is closely related to Definitions 2.1 and 2.2 is the
Markov blanket ( Pearl , 1988 ). It essentially represents the set of nodes that com-
pletely d-separates a given node from the rest of the graph.

Definition 2.3 (Markov blanket). The Markov blanket of a node A ∈ V is the min-

imal subset S of V such that

A ⊥ P V − S − A | S . (2.9)

In any Bayesian network, the Markov blanket of a node A is the set of the parents of
A , the children of A , and all the other nodes sharing a child with A .

Markov blankets facilitate the comparison of Bayesian networks with graphi-
cal models based on undirected graphs, which are known as Markov networks or
Markov random fields ( Whittaker , 1990 ; Edwards , 2000 ). On a related note, a DAG
can be transformed in the undirected graph of the corresponding Markov networks
by following the steps below.

1. Connect the nonadjacent nodes in each v-structure with an undirected arc. This is
equivalent to adding an undirected arc between any node in the Markov blanket
and the node the Markov blanket is centered on.
2. Ignore the direction of the other arcs. This effectively replaces the arcs with
edges.

The above transformation is called moralization since it “marries” nonadja-
cent parents sharing a common child. The resulting graph is called a moral graph
( Castillo et al. , 1997 ).

2 Note that the two parents in a v-structure ( A and B in Fig. 2.1 ) cannot be connected by an arc,
while this is not necessarily the case in a convergent connection.