Introduction - Bayesian Networks in R: With Applications in Systems Biology - page 3

Fig. 1.2 Parents, children, ancestors, descendants, and neighbors of node A in a directed graph

that the vertices u and v incident on each arc are distinct and that there is at most
one arc between them so that

uniquely identifies an arc. This definition also
implicitly excludes presence of a loop that can occur when u

( u , v )

v .
The simplest structure is an empty graph , i.e., a graph with no arcs. On the
other end of the spectrum are saturated graphs , in which each node is connected
to every other node. Real-world graphical abstractions usually fall between these
two extremes and can be either sparse or dense . While the distinction between
these two classes of graphs is rather vague, a graph is usually considered sparse
if O

=

.
The structure of a graph can reveal interesting statistical properties. Some of the
most important ones deal with paths . Paths are essentially sequences of arcs or edges
connecting two nodes, called end-vertices or end-nodes . Paths are denoted with the
sequence of vertices

( | E | + | A | )= O ( | V | )

( v 1 , v 2 ,..., v n ) incident on those arcs. The arcs connecting the

vertices v 1 , v n are assumed to be unique, so that a path passes through each

arc only once. In directed graphs it is also assumed that all the arcs in a path follow
the same direction, and we say that a path leads from v 1 (i.e., the tail of the first arc
in the path) to v n (i.e., the head of the last arc in the path). In undirected and mixed
graphs (and in general when referring to a graph regardless which class it belongs
to), arcs in a path can point in either direction or be undirected. Paths in which
v 1 =

v 2 ,...,

v n are called cycles and are treated with particular care in Bayesian network
theory.
The structure of a directed graph defines a partial ordering of the nodes if the
graph is acyclic , that is, if it does not contain any cycle or loop. This ordering is
called an acyclic or topological ordering and is induced by the direction of the
arcs. It is defined as follows: if a node v i precedes v j , there can be no arc from
v j to v i . According to this definition the first nodes are the root nodes , which have
no incoming arcs, and the last ones are the leaf nodes , which have at least one
incoming arc but no outgoing ones. Furthermore, if there is a path leading from v i
to v j , v i precedes v j in the sequence of the ordered nodes. In this case v i is called
an ancestor of v j and v j is called a descendant of v i . If the path is composed by a
single arc, by analogy x i is a parent of v j and v j is a child of v i .
Consider, for instance, node A in the directed acyclic graph shown in Fig. 1.2 .Its
neighborhood is the union of the parents and children; adjacent nodes necessarily
fall into one of these two categories. Its parents are also ancestors, as they necessar-
ily precede A in the topological ordering. Likewise, children are also descendants.