From random graphs to complex networks : a modelling approach

Abstract

In den vergangenen Jahren hat die Erforschung so-genannter Komplexer Netzwerke begonnen. Grund dafür ist, dass durch Computer riesige Datenbanken (z.B. Netzwerke von Zitaten, das Internet) nicht nur existieren, sondern auch untersuchbar (Rechnerleistung!) sind. Diese Datenbanken werden dann zur Analyse als Netzwerke (Graphen) aufgefasst.<br />Viele dieser Netzwerke haben sehr ähnliche Eigenschaften: Sie sind sehr groß, sie haben viele Dreiecke (einen hohe Maß an "Clustering"), sie haben durchschnittlich sehr geringe Distanzen zwischen zwei verschiedenen Knoten (kleiner oder gleich log(n), wobei n die Anzahl der Knoten ist) und die Verteilung der Grade der Knoten weist ein Potenzgesetz auf.<br />Meine Diplomarbeit beschäftigt sich mit Modellen, die entstanden sind, um diese Netzwerke zu erklären: In den ersten Kapiteln werden Grundlagen erklärt und motivierende Beispiele gebracht. Dann wird im vierten Kapitel auf das "klassische" Modell von Zufallsgraphen von Erdoes und Renyi eingegangen, Resultate und rigorose Beweise werden gebracht. Im nächsten Kapitel wird das "Small-world" Model von Strogatz und Watts vorgestellt, und auch einige Arbeiten oder Erweiterungen dazu. Im nächsten Kapitel wird auf das Model von Barabasi und Albert eingegangen, dass preferenzielles Vernetzen untersucht, und einige Fortsetzungen dieses Modells (LCD Modell, Modell von Osthus und Buckley) werten vorgestellt. Im abschließenden Kapitel werden noch die fast schon "classischen" Modelle (Copying Modell bzw. Cooper und Frieze Modell) vorgestellt, und zwei sehr neue Arbeiten.<br />

The past years have seen an upsurge in the study of so-called complex networks. The reason for this was that, through computers, vast data bases were now not only availible, but could also be analyzed, for example citation networks or the world wide web. These data bases were then interpreted as networks (graphs).<br />Most of these networks have very similar properties: They are very big, have a large number of triangles (a high "clustering coefficient"), and on average have a very small distance between two randomly chosen vertices (where small means smaller than log(n), where n is the number of vertices in the graph). They also exhibit a power law degree distribution. My diploma thesis treats the subject of models trying to explain these networks. After three introductory chapters where the basics are explained and motivating examples are given, I present the "classical" random graph model by Erdoes and Renyi. Results are given, as well as rigorous proofs. The next chapter treats the "small-world" model by Strogatz and Watts, as well as some works that extended it. Afterwards, I present the Barabasi and Albert Model, that takes preferential linking into account. I then proceed to present some other models with preferential attachment, such as the LCD model or the Model by Osthus and Buckley. In the last chapter, I mention some other models that were very important in the forming of the theory of complex networks, as well as some newer models.