Motiviert durch strukturelle Eigenschaften molekularer Ähnlichkeitsnetzwerke werden die Evolution der größten Komponente eines Netzwerkes in zwei verschiedenen stochastischen Modellen, zufälligen Hypergraphen und zufälligen Schnittgraphen, untersucht. Zuerst wird bewiesen, dass die Anzahl der Knoten in der größten Komponente d-uniformer Hypergraphen einer Normalverteilung folgt. Der Beweis nutzt dabei ausschließlich probabilistische Argumente und keine enumerative Kombinatorik. Diesem grundlegenden Resultat folgen weitere Grenzwertsätze für die gemeinsame Verteilung von Knoten- und Kantenzahl sowie Sätze zur Zusammenhangswahrscheinlichkeit zufälliger Hypergraphen und zur asymptotischen Anzahl zusammenhängender Hypergraphen. Da das Hypergraphenmodell einige Eigenschaften der Realweltdaten nur unzureichend abbildet, wird anschließend die Evolution der größten Komponente in zufälligen Schnittgraphen, die Clustereigenschaften realer Netzwerke widerspiegeln, untersucht. Es wird gezeigt, dass zufällige Schnittgraphen sich von zufälligen (Hyper-)Graphen dadurch unterscheiden, dass (bei einer durchschnittlichen Nachbaranzahl von mehr als eins) weder die größte Komponente linear noch die zweitgrößte Komponente logarithmisch groß in Abhängigkeit von der Knotenzahl ist. Weiterhin wird ein Polynomialzeitalgorithmus zur Überdeckung der Kanten eines Graphen mit möglichst wenigen Cliquen (vollständigen Graphen) beschrieben und seine asymptotische Optimalität im Modell der zufälligen Schnittgraphen bewiesen. Anschließend wird die Entwicklung der chromatischen Zahl untersucht und gezeigt, dass zufällige Schnittgraphen mit hoher Wahrscheinlichkeit mittels verschiedener Greedystrategien optimal gefärbt werden können. Letztendlich zeigen Experimente auf realen Netzen eine Übereinstimmung mit den theoretischen Vorhersagen und legen eine gegenseitige Zertifizierung der Optimalität von Cliquen- und Färbungszahl durch Heuristiken nahe. / Motivated by structural properties of molecular similarity networks we study the behaviour of the component evolution in two different stochastic network models, that is random hypergraphs and random intersection graphs. We prove gaussian distribution for the number of vertices in the giant component of a random d-uniform hypergraph. We provide a proof using only probabilistic arguments, avoiding enumerative methods completely. This fundamental result is followed by further limit theorems concerning joint distributions of vertices and edges as well as the connectivity probability of random hypergraphs and the number of connected hypergraphs. Due to deficiencies of the hypergraph model in reflecting properties of the real--world data, we switch the model and study the evolution of the order of the largest component in the random intersection graph model which reflects some clustering properties of real--world networks. We show that for appropriate choice of the parameters random intersection graphs differ from random (hyper-)graphs in that neither the so-called giant component, appearing when the average number of neighbours of a vertex gets larger than one, has linear order nor is the second largest of logarithmic order in the number of vertices. Furthermore we describe a polynomial time algorithm for covering graphs with cliques, prove its asymptotic optimality in a random intersection graph model and study the evolution of the chromatic number in the model showing that, in a certain range of parameters, these random graphs can be coloured optimally with high probability using different greedy algorithms. Experiments on real network data confirm the positive theoretical predictions and suggest that heuristics for the clique and the chromatic number can work hand in hand proving mutual optimality.

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. / 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).

No description available.