Proseminar „Algorithmen auf Graphen“

Zufälliges Erzeugen von Graphen und Bayes-Netzen

Björn Schapitz, CV04, 20.06.2006

2

Gliederung

(1) Einleitung

(2) Geschichtliches

(3) Algorithmen / Beispiele(1) Anschauliches Vorgehen

(2) Zufällige Adjazenzmatrix

(3) Zufällige Kantenanordnung

(4) Rekursive Erzeugung

(5) One-Pass-Algorithm

(4) Zufällige Bayes-Netze

(5) Zusammenfassung

Einleitung3

Gründe zur Beschäftigung mit zufälligen Graphen

1. Beweise führen (Nachweise der Existenz von Graphen mit bestimmten Eigenschaften)

2. Modellierung von großen, unüberschaubaren Strukturen (z.B. Netzwerke, Internet)

4

Arten zufälliger Graphen

echt zufällige Graphen Oft bestimmte Eigenschaften benötigt:

– Begrenzt maximale Cliquen– Verhältnis Kanten/Knoten (Dichte)– Zusammenhängend ?

5

Geschichtliches

Paul Erdös – ungarischer Mathematiker– * 26.03.1913, † 20.09.96

Entwickelte die „Probabilistische Methode“ zum Beweis seines Satzes:„Es gibt Graphen, die gleichzeitig beliebig hohe Taillenweite und beliebig hohe chromatische Zahl haben.“

6

Anschauliches Vorgehen

Leeren Graphen mit n Knoten erzeugen Wahrscheinlichkeitszahl p mit 0 ≤ p ≤ 1erzeugen Für jedes Tupel (n1,n2) mit (n1≠n2) entscheiden, ob Kante

gesetzt wird Beispiel:

7

Zufällige Adjazenzmatrix

n Knoten: n x n Matrix erzeugen Mit Nullen füllen Wahrscheinlichkeitszahl p erzeugen: 0 ≤ p ≤ 1 Für jedes Element der oberen Dreiecksmatrix (ohne

Hauptdiagonale):– Zufallszahl x erzeugen: 0 ≤ x ≤ 1– Wenn x > p, Element auf 1 setzen

8

Beispiel 1

Zufallsgraph mit 5 Knoten 5 x 5 Matrix erzeugen

n1 n2 n3 n4 n5

n1 0 0 0 0 0

n2 0 0 0 0 0

n3 0 0 0 0 0

n4 0 0 0 0 0

n5 0 0 0 0 0

9

Beispiel 1

Wahrscheinlichkeit p erzeugen p = 0.5 Für jedes Element oberhalb

der Hauptdiagonalen Zufallszahl x erzeugen

falls x > p, Matrixelement anpassen

n1 n2 n3 n4 n5

n1 0 1 0 1 1

n2 0 0 1 1 0

n3 0 0 0 0 1

n4 0 0 0 0 1

n5 0 0 0 0 0

10

Beispiel 1

Graph anhand Adjazenzmatrix aufbauen

n1 n2 n3 n4 n5

n1 0 1 0 1 1

n2 0 0 1 1 0

n3 0 0 0 0 1

n4 0 0 0 0 1

n5 0 0 0 0 0

11

Eigenschaften so erzeugter Graphen

Erzeugt echt zufällige Graphen Anzahl der Kanten über p beeinflussbar Nicht immer zusammenhängend Komplexität: O(n2)

12

Zufällige Kantenanordnung

Leeren Graphen mit n Knoten erzeugen Anzahl der Kanten e zwischen 0 und emax wählen 1 bis e mal:

– p und q von 1..n wählen, so dass p<q– Kante von p nach q erzeugen

13

Beispiel 2

Leeren Graph mit 5 Knoten erzeugen emax = 10

(max. Anzahl Kanten ohne Loops = (n(n-1))/2 e zufällig aus 1 bis 10: e = 8

14

Beispiel 2

1 bis 8 mal p und q aus 1..n wählen (mit p<q):p=2 q=3; p=4 q=5; p=1 q=2; p=1 q=3;

p=1 q=4; p=3 q=5; p=1 q=5; p=2 q=5;

Kante von np nach nq setzen

15

Eigenschaften so erzeugter Graphen

gezieltes Setzen von e = feste Kantenanzahl Durch geeignete Wahl von p und q kann die

max. Anzahl der Eltern und Kinder beeinflusst werden

Sind nicht immer zusammenhängend Laufzeit: abhängig von e Komplexität: bis zu O(n2)

16

Rekursive Erzeugung

Basiert auf der Formel von R.W. Robinson, Anzahl möglicher Graphen mit n Knoten und k

Wurzeln ist an(k), mit

Wiederholte rekursive Zerlegung in Wurzeln und Rest-Knoten

Für alle möglichen Wurzel-Anzahlen s des Teilgraphen alle Kombinationen aufsummieren

17

Rekursive Erzeugung - Algorithmus

- Umkehrung der Berechnungsformel zur Berechnung eines Graphen (benötigt Knotenmenge V und Wurzelanzahl k)

1. Zufällig k Wurzeln wählen: K V, |K| = k

2. Zufällig s aus 1..(n-k) wählen, dabei beachten:

(s wird für die Erzeugung von S V\K benötigt)

18

Rekursive Erzeugung - Algorithmus

3. Wähle zufällig und unabhängig voneinander s nichtleere Teilmengen aus K Eltern für jedes Element aus S

4. Wähle zufällig und unabhängig voneinander (n-k-s) Teilmengen (dürfen leer sein) aus K Eltern für Elemente aus V\K\S

5. Benutze diesen Algorithmus rekursiv, um aus V \ K als Knotenmenge und s als Anzahl der Wurzeln einen azyklischen Graphen mit den Wurzel-Knoten S zu erzeugen

Bei zufälliger Bestimmung von k muss P(k)=an(k)/an gelten.

19

Rekursive Erzeugung - Eigenschaften

Vorteile:– Variation von k und s hoher/breiter Graph– Rekursive topologische Aufspaltung einfacheres

Ermitteln von Attribut-Abhängigkeiten

Nachteile:– Nicht immer zusammenhängend– an

(k) müssen für alle Kombinationen von k und n berechnet und zwischengespeichert werden (a1=1, a2=3, a3=25, … , a7=1.138.779.265!!!)

– Komplexität: O(n2)

20

One-Pass-Algorithm

Erzeugt in einem Schritt einen zusammenhängenden Graphen

Anzahl Knoten n und Wurzeln r muss bekannt sein

Maximaler Eingangsgrad m ist begrenzt

21

One-Pass-Algorithm

Notwendige Bedingungen:– n ≥ 2 sinnvoller Graph muss mindestens 2

Knoten haben– 1 ≤ r < n mindestens eine Wurzel– 1 ≤ m < n zusammenhängender Graph

22

One-Pass-Algorithm

Einschränkungen von n, r und m:– wenn r ≥ m, dann m(n-r) ≥ n-1– sonst m(n-r) + m(m-1)-r(r-1) ≥ n-1

2

Eingabe: Knoten n, Wurzeln r und maximaler Eingangsgrad m

Ausgabe: zusammenhängender azyklischer gerichteter Graph

Komplexität: O(mn)

23

One-Pass-Algorithm

Maximale Kantenanzahl berechnen:– emax = m(n-r) falls r ≥ m

– emax = m(n-r)+½(m(m-1)-r(r-1)) sonst

Kantenanzahl e zufällig aus Intervall [n, emax] bestimmen

Für alle Wurzelknoten (v0…vr-1) Eingangsgrad d-(vi)=0 setzen

Für restliche Knoten d-(vi) = [1,min(i,m)] setzen

dabei beachten, dass ∑i=r d-(vi)=e sein muss

24

One-Pass-Algorithm

Für alle Knoten Anzahl zu verbindender Eltern p(vi)=d-(vi)

Für i=r bis n-1:– Kante von vj zu vi setzen (j [r-1,i-1])

Für i=0 bis r-2– Kante von vi zu x setzen (x {vj | p(vj)≥1})

Für i=r bis n-1:– Solange p(vi) ≥ 1 wiederhole:

Kante von x zu vi setzen (x {vj | 0 ≤ j ≤ i-1, (vj,vi) є E})

25

Beispiel 3

Graph mit 5 Knoten, 2 Wurzeln und maximalem Eingangsgrad 2

Bedingungen:– n ≥ 2 erfüllt– 1 ≤ r < n erfüllt– 1 ≤ m < n erfüllt

Einschränkung: da r ≥ m, muss m(n-r) ≥ n-1 gelten

2(5-2) ≥ 5-1 6 ≥ 4

26

Beispiel 3

1. emax = m(n-r) = 62. e=6

3. d-(n0)=0, d-(n1 )=04. restliche Knoten:

– n2=[1,min(2,2)]=2– n3=[1,min(3,2)]=2– n4=[1,min(4,2)]=2

5. p(n2)=2 p(n3)=2 p(n4)=2

27

Beispiel 3

6. i=2 bis 4– nj ni, j[1,1] n1 n2

– nj ni, j[1,2] n1 n3

– nj ni, j[1,3] n1 n4

7. i=0 bis 0– Kante von ni zu x, wobei

x={nj | p(nj)≥1} n0 n2

28

Beispiel 3

8. i=2 bis 4- p(n2) ≥ 1 ? nein- p(n3) ≥ 1 ? ja, x zu n3, x {nj | 0 ≤ j ≤ 2, (nj,n3) nicht Element von E nj=n0, n0n3

- p(n4) ≥ 1 ? ja, x zu n4, x {nj | 0 ≤ j ≤ 3, (nj,n4) nicht Element von E nj=n0, n0n4

29

Bayes-Netze

Bayessches Netz:– Gerichteter azyklischer Graph– Jeder Knoten besitzt Variable mit Angabe über

ihre statistische Verteilung– Meistens zusammenhängend

30

Erweitern zum Bayesschen-Netz

Jedem Knoten vi Variable Vi zuordnen Anzahl der möglichen Zustände für Vi bestimmen: Ni=|Vi| Für jeden Wurzelknoten: Ni Zufallswerte erzeugen und zu ∑=1

normieren Für alle anderen Knoten in topologischer Reihenfolge: für jede

Belegung der Elternknoten Ni Zufallswerte erzeugen und zu ∑=1 normieren

Bei Bedarf beliebig viele Einzelbelegungen des Netzes entsprechend den Verteilungen erzeugen

Komplexität: abhängig von Elternknoten-Anzahl, ≈ O(mn)

31

Zusammenfassung

Zufällige Graphen verwendet zur Beweisführung und zur Modellierung unübersichtlicher Strukturen

Algorithmen:– Zufällige Adjazenzmatrix: kaum Variationen möglich– Zufällige Kantenzuordnung: Variationen bedingt über

Parameter möglich– Rekursive Erzeugung: Struktur variierbar, aber komplex

und langsam– One-Pass-Algorithm: zusammenhängend, wenige Kanten

gut für Bayessche-Netze Bayessche Netze:

– Erweiterungen obiger Algorithmen mit Zustandsvariablen für Knoten

32

Quellen

Reinhard Diestel: „Graphentheorie“, 1996, Springer Svante Janson, Tomasz Luczak, Andrzej Rucinski:

„Random Graphs“, 2000, John Wiley & Sons Inc. Lothar Wenzel: „Wie klein ist doch die Welt“, in:

Toolbox, Ausgabe 6/2002, S. 6 ff. Ansgar Voigt: „Mathe-Tricks in der Biologie“, in:

RUBIN, 2003 Peter Eichelsbacher: „Die Steinsche Methode“, 2003