On Local Behavior and Global Structures in the Evolution of Complex Networks

Abstract

In this work we focus on the interplay of local behavior of agents building a network and the global structures they can achieve in this way. The first subproject was dedicated to defining the small-world phenomenon and an analysis of the maximal number of edges needed to produce it. The second subproject aimed to find out whether real-world networks contain a random graph (as stated by the small-world model) and to bound the number of edges in this part of the graph. To do so, we developed a method to find a so-called backbone, a special type of spanning tree, that describes the structure of the network. It turned out that backbones are deeply related to another graph theoretic structure, namely cycle bases. We found out that in many real-world networks it is easy to find a cycle base with a weight in O(m log n), a finding that is important for the efficient executions of some algorithms. In a third subproject we tried to find out how myopic and selfish agents can build a global network topology with a desired global feature and how long it will take to build it, given the locality and selfishness of the agents. We found out that the running time to build a certain topology is very much depending on the design of local attachment rules, ranging from expectedly exponential running time to polynomial running time for very rules that differ only very little.

Diese Arbeit nähert sich dem Verständnis von lokalem Verhalten von Agenten, die gemeinsam ein Netzwerk aufbauen, und der Topologie des Netzwerkes in Abhängigkeit von diesem Verhalten. Das erste Teilprojekt beschäftigt sich mit der Definition des sogenannten Kleinwelten-Phänomens und der theoretischen Analyse, wieviele Zufallskanten höchstens benötigt werden, um es zu erzeugen. Das zweite Teilprojekt beschäftigt sich mit der Frage, ob reale Netzwerke wirklich einen Zufallsgraphen enthalten (wie das Kleinweltenmodell besagt) und wenn ja, wie hoch der Anteil dieses Graphens ist. Für dieses Ziel haben wir eine Methode entwickelt, die ein "Rückgrat" des Netzwerkes findet, eine besondere Art von Spannbaum, der die Struktur des Netzwerkes beschreibt. Es stellte sich heraus, dass das Rückgrat eines Netzwerkes gleichzeitig auch eine sogenannte strikt fundamentale Kreisbasis beschreibt. Eine empirische Untersuchung realer Netzwerke zeigte, dass die meisten dieser Netzwerke eine leichtgewichtige Kreisbasis in O (m log n) enthalten, was elementar für die Effizienz bestimmter Algorithmen ist. Im dritten Teilprojekt haben wir uns mit der Frage beschäftigt, wie lokal eingeschränkte und eigennützige Agenten Netzwerke mit einer bestimmten globalen Struktur aufbauen können and wie lange es dauert, bis sie diese Struktur aufgebaut haben. Wir konnten zeigen, dass die erwartete Laufzeit bis zum Erreichen dieser Struktur sehr stark von der genauen Formulierung der lokalen Netzwerkbildungsregel abhängt. An einem simplen Beispiel konnten wir zeigen, dass eine bestimmte Bildungsregel zu einer exponentiellen Laufzeit führt, die durch eine geringfügige Änderung zu einer polynomiellen Laufzeit reduziert werden kann ohne dass die eigentliche Regel dadurch komplexer würde.