Bachelor thesis – Robert Jonsson
Robert Jonsson
Characterisation of Lattice Triangulations Complex Networks and their Metric Structure
finished 2010-08
supervised by Klaus Mecke and Johannes Reinhard
Abstract
In der Physik werden periodische Gitter zur diskreten Modellierung von Raum und Zeit seit der Arbeit von Ernst Ising (1925) und spätestens seit Kenneth Wilsons Formulierung einer Gittereichtheorie in 1974 verwendet. Im Gegensatz zu diesen regelmäßigen Graphen werden Zufallsgraphen seit den Arbeiten von Solomonoff und Rapoport (1951) und von Erdős und Rényi (1956) intensiv studiert, um Netzwerke in Physik und Biologie zu beschreiben, insbesondere um topologische Eigenschaften, Skalenverhalten und ‚Small-World-Effekte‘ zu verstehen. Zufällige Gittertriangulierungen stellen eine Kombination beider Ideen dar, die eine reguläre Diskretisierung des Raumes mit zufällig gewählten Verbindungen versieht, so dass stets Dreiecke gleichen Flächeninhalts entstehen. Während Algorithmen zur Bestimmung des Konfigurationsraumes aller möglichen Gittertriangulierungen mittlerweile vorhanden sind, ist deren metrische und topologische Charakterisierung noch nicht durchgeführt worden. Insbesondere der Abstand zweier Gitterpunkte – definiert als die minimale Anzahl von Kanten eines verbindenden Pfades – ist von Interesse, da daran sowohl Small-World-Effekte (Skalierung mit Systemgröße) als auch Anisotropien (Richtungsabhängigkeit) zu identifizieren sind. — Die Aufgabe von Robert Jonsson war, einen Algorithmus zu implementieren, der eine geeignet definierte Metrik auf diesen Gittertriangulierungen berechnet, sowie für diese die gängigen topologischen Charakterisierungen von zufälligen Graphen bestimmt. Die wichtigsten Ergebnisse sind: * Während maximale Triangulierungen einen ’small-world-effect‘ mit einem mittleren Abstand l=2.8 zweier beliebiger Vertizes zeigen, ist dies für zufällige und reguläre Triangulierungen nicht der Fall, bei denen der Abstand linear mit der Systemgröße anwächst. * Maximale Triangulierungen zeigen eine Skalierung der Kantenzahl am Vertex sowie der Korrelation des Vertexgrades nächster Nachbarn. * Die Oberfläche einer ‚Kugel‘ in einer zufälligen Triangulierung skaliert wie ~ R1.42 mit ihrem Radius R, d.h. Gittertriangulierungen zeigen eine fraktale Geometrie.
In der Physik werden periodische Gitter zur diskreten Modellierung von Raum und Zeit seit der Arbeit von Ernst Ising (1925) und spätestens seit Kenneth Wilsons Formulierung einer Gittereichtheorie in 1974 verwendet. Im Gegensatz zu diesen regelmäßigen Graphen werden Zufallsgraphen seit den Arbeiten von Solomonoff und Rapoport (1951) und von Erdős und Rényi (1956) intensiv studiert, um Netzwerke in Physik und Biologie zu beschreiben, insbesondere um topologische Eigenschaften, Skalenverhalten und ‚Small-World-Effekte‘ zu verstehen. Zufällige Gittertriangulierungen stellen eine Kombination beider Ideen dar, die eine reguläre Diskretisierung des Raumes mit zufällig gewählten Verbindungen versieht, so dass stets Dreiecke gleichen Flächeninhalts entstehen. Während Algorithmen zur Bestimmung des Konfigurationsraumes aller möglichen Gittertriangulierungen mittlerweile vorhanden sind, ist deren metrische und topologische Charakterisierung noch nicht durchgeführt worden. Insbesondere der Abstand zweier Gitterpunkte – definiert als die minimale Anzahl von Kanten eines verbindenden Pfades – ist von Interesse, da daran sowohl Small-World-Effekte (Skalierung mit Systemgröße) als auch Anisotropien (Richtungsabhängigkeit) zu identifizieren sind. — Die Aufgabe von Robert Jonsson war, einen Algorithmus zu implementieren, der eine geeignet definierte Metrik auf diesen Gittertriangulierungen berechnet, sowie für diese die gängigen topologischen Charakterisierungen von zufälligen Graphen bestimmt. Die wichtigsten Ergebnisse sind: * Während maximale Triangulierungen einen ’small-world-effect‘ mit einem mittleren Abstand l=2.8 zweier beliebiger Vertizes zeigen, ist dies für zufällige und reguläre Triangulierungen nicht der Fall, bei denen der Abstand linear mit der Systemgröße anwächst. * Maximale Triangulierungen zeigen eine Skalierung der Kantenzahl am Vertex sowie der Korrelation des Vertexgrades nächster Nachbarn. * Die Oberfläche einer ‚Kugel‘ in einer zufälligen Triangulierung skaliert wie ~ R1.42 mit ihrem Radius R, d.h. Gittertriangulierungen zeigen eine fraktale Geometrie.