edoc-Server der Humboldt-Universität zu Berlin

Dissertation

Autor(en): Taral Guldahl Seierstad
Titel: The phase transition in random graphs and random graph processes
Gutachter: Hans Jürgen Prömel; Tomasz Luczak; Stefan Felsner
Erscheinungsdatum: 01.08.2007
Volltext: pdf (urn:nbn:de:kobv:11-10079795)
Fachgebiet(e): Informatik
Schlagwörter (ger): Zufallsgraphen, Phasenübergang, kritische Phase, größte Komponente
Schlagwörter (eng): random graphs, phase transition, critical phase, giant component
Einrichtung: Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II
Zitationshinweis: Seierstad, Taral Guldahl: The phase transition in random graphs and random graph processes; Dissertation, Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II , publiziert am 01.08.2007, urn:nbn:de:kobv:11-10079795
Metadatenexport: Um den gesamten Metadatensatz im Endnote- oder Bibtex-Format zu speichern, klicken Sie bitte auf den entsprechenden Link. Endnote   Bibtex  
print on demand: Wenn Sie auf dieses Icon klicken, können Sie ein Druckexemplar dieser Publikation bestellen.

Abstract (ger):
Zufallsgraphen sind Graphen, die durch einen zufälligen Prozess erzeugt werden. Ein im Zusammenhang mit Zufallsgraphen häufig auftretendes Phänomen ist, dass sich die typischen Eigenschaften eines Graphen durch Hinzufügen einer relativ kleinen Anzahl von zufälligen Kanten radikal verändern. Wir betrachten den Zufallsgraphen G(n,p), der n Knoten enthält und in dem zwei Knoten unabhängig und mit Wahrscheinlichkeit p durch eine Kante verbunden sind. Erdös und Rényi zeigten, dass ein Graph für p = c/n und c < 1 mit hoher Wahrscheinlichkeit aus Komponenten mit O(log n) Knoten besteht. Für p = c/n und c > 1 enthält G(n,p) mit hoher Wahrscheinlichkeit genau eine Komponente mit Theta(n) Knoten, welche viel größer als alle anderen Komponenten ist. Dieser Punkt in der Entwicklung des Graphen, an dem sich die Komponentenstruktur durch eine kleine Erhöhung der Anzahl von Kanten stark verändert, wird Phasenübergang genannt. Wenn p = (1+epsilon)/n, wobei epsilon eine Funktion von n ist, die gegen 0 geht, sind wir in der kritischen Phase, welche eine der interessantesten Phasen der Entwicklung des Zufallsgraphen ist. In dieser Arbeit betrachten wir drei verschiedene Modelle von Zufallsgraphen. In Kapitel 4 studieren wir den Minimalgrad-Graphenprozess. In diesem Prozess werden sukzessive Kanten vw hinzugefügt, wobei v ein zuällig ausgewählter Knoten von minimalem Grad ist. Wir beweisen, dass es in diesem Graphenprozess einen Phasenübergang, und wie im G(n,p) einen Doppelsprung, gibt. Die zwei anderen Modelle sind Zufallsgraphen mit einer vorgeschriebenen Gradfolge und zufällige gerichtete Graphen. Für diese Modelle wurde bereits in den Arbeiten von Molloy und Reed (1995), Karp (1990) und Luczak (1990) gezeigt, dass es einen Phasenübergang bezüglich der Komponentenstruktur gibt. In dieser Arbeit untersuchen wir in Kapitel 5 und 6 die kritische Phase dieser Prozesse genauer, und zeigen, dass sich diese Modelle ähnlich zum G(n,p) verhalten.
Abstract (eng):
Random graphs are graphs which are created by a random process. A common phenomenon in random graphs is that the typical properties of a graph change radically by the addition of a relatively small number of random edges. This phenomenon was first investigated in the seminal papers of Erdös and Rényi. We consider the graph G(n,p) which contains n vertices, and where any two vertices are connected by an edge independently with probability p. Erdös and Rényi showed that if p = c/n$ and c < 1, then with high probability G(n,p) consists of components with O(log n) vertices. If p = c/n$ and c>1, then with high probability G(n,p) contains exactly one component, called the giant component, with Theta(n) vertices, which is much larger than all other components. The point at which the giant component is formed is called the phase transition. If we let $p = (1+epsilon)/n$, where epsilon is a function of n tending to 0, we are in the critical phase of the random graph, which is one of the most interesting phases in the evolution of the random graph. In this case the structure depends on how fast epsilon tends to 0. In this dissertation we consider three different random graph models. In Chapter 4 we consider the so-called minimum degree graph process. In this process edges vw are added successively, where v is a randomly chosen vertex with minimum degree. We prove that a phase transition occurs in this graph process as well, and also that it undergoes a double jump, similar to G(n,p). The two other models we will consider, are random graphs with a given degree sequence and random directed graphs. In these models the point of the phase transition has already been found, by Molloy and Reed (1995), Karp (1990) and Luczak (1990). In Chapter 5 and 6 we investigate the critical phase of these processes, and show that their behaviour resembles G(n,p).
Zugriffsstatistik: Die Daten für die Zugriffsstatistik der einzelnen Dokumente wurden aus den durch AWStats aggregierten Webserver-Logs erstellt. Sie beziehen sich auf den monatlichen Zugriff auf den Volltext sowie auf die Startseite. Die Zugriffsstatistik wird nicht standardisiert erfasst und kann maschinelle Zugriffe enthalten.
 
Bei Formatversionen eines Dokuments, die aus mehreren Dateien bestehen (insbesondere HTML), wird jeweils der monatlich höchste Zugriffswert auf eine der Dateien (Kapitel) des Dokuments angezeigt.
 
Um die detaillierten Zugriffszahlen zu sehen, fahren Sie bitte mit dem Mauszeiger über die einzelnen Balken des Diagramms.
Startseite: 4 Zugriffe PDF: 3 Zugriffe Startseite: 1 Zugriffe PDF: 2 Zugriffe Startseite: 3 Zugriffe PDF: 1 Zugriffe Startseite: 1 Zugriffe PDF: 6 Zugriffe Startseite: 3 Zugriffe PDF: 6 Zugriffe Startseite: 5 Zugriffe Startseite: 3 Zugriffe PDF: 5 Zugriffe PDF: 6 Zugriffe PDF: 10 Zugriffe Startseite: 6 Zugriffe PDF: 14 Zugriffe Startseite: 2 Zugriffe PDF: 7 Zugriffe Startseite: 6 Zugriffe PDF: 3 Zugriffe PDF: 1 Zugriffe PDF: 2 Zugriffe PDF: 6 Zugriffe PDF: 6 Zugriffe Startseite: 1 Zugriffe PDF: 9 Zugriffe Startseite: 3 Zugriffe PDF: 12 Zugriffe Startseite: 1 Zugriffe PDF: 20 Zugriffe Startseite: 6 Zugriffe PDF: 16 Zugriffe Startseite: 2 Zugriffe PDF: 10 Zugriffe Startseite: 3 Zugriffe PDF: 10 Zugriffe Startseite: 1 Zugriffe PDF: 13 Zugriffe PDF: 8 Zugriffe Startseite: 5 Zugriffe PDF: 5 Zugriffe Startseite: 2 Zugriffe PDF: 8 Zugriffe Startseite: 2 Zugriffe PDF: 11 Zugriffe Startseite: 2 Zugriffe PDF: 9 Zugriffe Startseite: 4 Zugriffe PDF: 18 Zugriffe Startseite: 1 Zugriffe PDF: 39 Zugriffe Startseite: 2 Zugriffe PDF: 14 Zugriffe Startseite: 3 Zugriffe PDF: 27 Zugriffe Startseite: 2 Zugriffe PDF: 38 Zugriffe Startseite: 1 Zugriffe PDF: 27 Zugriffe Startseite: 2 Zugriffe PDF: 10 Zugriffe Startseite: 1 Zugriffe PDF: 1 Zugriffe Startseite: 2 Zugriffe PDF: 1 Zugriffe
Jul
11
Aug
11
Sep
11
Oct
11
Nov
11
Dec
11
Feb
12
Apr
12
May
12
Jun
12
Jul
12
Aug
12
Sep
12
Oct
12
Nov
12
Dec
12
Jan
13
Feb
13
Mar
13
May
13
Jun
13
Jul
13
Aug
13
Sep
13
Oct
13
Nov
13
Dec
13
Jan
14
Feb
14
Mar
14
Apr
14
May
14
Jun
14
Jul
14
Aug
14
Sep
14
Oct
14
Monat Jul
11
Aug
11
Sep
11
Oct
11
Nov
11
Dec
11
Feb
12
Apr
12
May
12
Jun
12
Jul
12
Aug
12
Sep
12
Oct
12
Nov
12
Dec
12
Jan
13
Feb
13
Mar
13
May
13
Jun
13
Jul
13
Aug
13
Sep
13
Oct
13
Nov
13
Dec
13
Jan
14
Feb
14
Mar
14
Apr
14
May
14
Jun
14
Jul
14
Aug
14
Sep
14
Oct
14
Startseite 4 1 3 1 3 5 3     6 2 6         1 3 1 6 2 3 1   5 2 2 2 4 1 2 3 2 1 2 1 2
PDF 3 2 1 6 6   5 6 10 14 7 3 1 2 6 6 9 12 20 16 10 10 13 8 5 8 11 9 18 39 14 27 38 27 10 1 1

Gesamtzahl der Zugriffe seit Jul 2011:

  • Startseite – 80 (2.16 pro Monat)
  • PDF – 384 (10.38 pro Monat)
 
 
Generiert am 21.11.2014, 10:16:38