Information Technology Reference
In-Depth Information
Clique
Rank
{
A
,
C
}
max{
(
A
),
(
C
)}
= 2
C
1
{
C
,
D
,
F
}
max{
(
C
),
(
D
),
(
F
)}
= 4
C
2
{
D
,
E
,
F
}
max{
(
D
),
(
E
),
(
F
)}
= 5
C
3
{
B
,
D
,
E
}
max{
(
B
),
(
D
),
(
E
)}
= 6
C
4
{
F
,
E
,
H
}
max{
(
F
),
(
E
),
(
H
)}
= 7
C
5
{
F
,
G
}
max{
(
F
),
(
G
)}
= 8
C
6
Tabelle 23.4: Ableitung einer Cliquenordnung mit RIP aus der perfekten Knotenord-
nung
aus Abbildung 23.7.
gerichteten oder ungerichteten Graphen zu kodieren, um dann allein unter Ausnut-
zung graphentheoretischer Kriterien auf wahrscheinlichkeitstheoretische Zustände
zu schließen. Der Umstand, dass innerhalb einer Menge von Attributen bestimmte
Unabhängigkeiten herrschen, soll durch Knoten im Graphen repräsentiert werden,
die in bestimmter Weise von einander getrennt, d. h. separiert werden. Wir werden
für beide Graphenarten (ungerichtet und gerichtet) je ein Separationskriterium ken-
nenlernen.
Beginnen wir mit der Betrachtung eines ungerichteten Graphen
G
=(
V
,
E
)
,in
dessen Knotenmenge drei disjunkte Teilmengen
X
,
Y
und
Z
ausgezeichnet sind. Die
Menge
Z
soll die Mengen
X
und
Y
genau dann u-separieren
9
,wennjederPfadeines
Knotens in
X
zu jedem Knoten in
Y
blockiert ist. Ein Pfad sei genau dann blockiert,
wenn er einen blockierenden Knoten enthält. Ein Knoten ist genau dann blockierend,
wenn er in
Z
liegt. Diese etwas umständliche Definition der u-Separation wird uns
später bei der Definition der d-Separation für gerichtete Graphen helfen.
Definition 23.42 (u-Separation, u-Trennung)
Sei G
=(
V
,
E
)
ein ungerichteter Graph
und X, Y und Z drei disjunkte Teilmengen von V. X und Y werden in G durch Z genau
dann
u-separiert
,wennjederPfadeinesKnotensinXzueinemKnoteninYmindestens
einen Knoten aus Z enthält. Dies wird als
X
G
Y
|
X
notiert. Ein Pfad, der mindestens einen Knoten aus Z enthält heißt
blockiert
,ansonsten
aktiv
.
Betrachten wir ein Beispiel in Abbildung 23.13. Die Menge
Z
= {
E
,
F
}
separiert
die Knotenmengen
{
A
,
B
,
C
,
D
}
und
{
G
,
H
,
J
}
,dasämtlichePfadevondereinenin
die andere Menge durch
Z
verlaufen, wie am Pfad
A
B
E
G
H
exemplarisch
gezeigt ist.
Eine alternative aber äquivalente Möglichkeit auf u-Separation zu testen ist die
folgende: Man entfernt die Knoten der Menge
Z
(und alle Kanten, die mit diesen
Knoten verbunden sind) aus demGraphen. Wenn es keinen Pfad mehr zwischen den
Mengen
X
und
Y
gibt, so sind beide durch
Z
u-separiert. Abbildung 23.14 illustriert
dies anhand des Beispiels aus Abbildung 23.13.
Für gerichtete Graphen müssen aus (später erläuterten) semantischen Gründen
die Kantenrichtungen zur Bestimmung der Blockierung eines Pfades berücksichtigt
9
Das
u
steht für
u
ndirected.
