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

DSpace Repository

Show simple item record

dc.contributor.advisor Kaufmann, Michael (Prof. Dr.) de_DE
dc.contributor.author Zweig, Katharina A. de_DE
dc.date.accessioned 2007-08-10 de_DE
dc.date.accessioned 2014-03-18T10:17:41Z
dc.date.available 2007-08-10 de_DE
dc.date.available 2014-03-18T10:17:41Z
dc.date.issued 2007 de_DE
dc.identifier.other 275447103 de_DE
dc.identifier.uri http://nbn-resolving.de/urn:nbn:de:bsz:21-opus-29787 de_DE
dc.identifier.uri http://hdl.handle.net/10900/49073
dc.description.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. en
dc.description.abstract 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. de_DE
dc.language.iso en de_DE
dc.publisher Universität Tübingen de_DE
dc.rights ubt-podok de_DE
dc.rights.uri http://tobias-lib.uni-tuebingen.de/doku/lic_mit_pod.php?la=de de_DE
dc.rights.uri http://tobias-lib.uni-tuebingen.de/doku/lic_mit_pod.php?la=en en
dc.subject.classification Dynamisches Netzwerk , Komplexes System , Netzwerkanalyse , Netzwerkmodell de_DE
dc.subject.ddc 004 de_DE
dc.subject.other Dynamic networks , network analysis , network modelling , small-world phenomenon en
dc.title On Local Behavior and Global Structures in the Evolution of Complex Networks en
dc.title Lokales Verhalten und Globale Strukturen in der Evolution komplexer Netzwerke de_DE
dc.type Dissertation de_DE
dcterms.dateAccepted 2007-07-18 de_DE
utue.publikation.fachbereich Informatik de_DE
utue.publikation.fakultaet 7 Mathematisch-Naturwissenschaftliche Fakultät de_DE
dcterms.DCMIType Text de_DE
utue.publikation.typ doctoralThesis de_DE
utue.opus.id 2978 de_DE
thesis.grantor 17 Fakultät für Informations- und Kognitionswissenschaften de_DE

Dateien:

This item appears in the following Collection(s)

Show simple item record