Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

On local behavior and global structures in the evolution of complex networks [Elektronische Ressource] / vorgelegt von Katharina A. Zweig, geb. Lehmann

De
168 pages
Ajouté le : 01 janvier 2007
Lecture(s) : 21
Signaler un abus

On Local Behavior and Global Structures in the Evolution of
Complex Networks
Dissertation
der Fakult¨at fur¨ Informations- und Kognitionswissenschaften
der Eberhard-Karls-Universit¨at Tubi¨ ngen
zur Erlangung des Grades eines
Doktors der Naturwissenschaften
(Dr. rer. nat.)
vorgelegt von
Katharina A. Zweig, geb. Lehmann
aus Hamburg
Tubi¨ ngen
2007Tag der mundl¨ ichen Qualifikation: 18.7.2007
Dekan: Prof. Dr. Michael Diehl
1. Berichterstatter: Prof. Dr. Michael Kaufmann
2. Berichterstatter: Prof. Dr. Roger Wattenhofer, ETH Zur¨ ich
3. Berichterstatter: Prof. Dr. Tama´s Vicsek, Eo¨tv¨os L´orand University, Budapest3
This work is dedicated to my parents, Ursula Lehmann-Buss and
Peter-Hannes Lehmann, who always supported me in everything
I did, and Winfried Zweig, who is all to me.CONTENTS
1. Acknowledgement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2. Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.1 Complex Networks in Complex Systems Science . . . . . . . . . . . . . . . . . . . . 10
2.2 Network Modeling - An Approach to Reduce Complexity
in Complex Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.3 Computer Science and Complex Network Science . . . . . . . . . . . . . . . . . . . 19
2.4 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3. Definitions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.1 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.2 Graphs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.3 Partition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.4 Graph Families . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.5 Spanning and Minimal Spanning Trees . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.6 Isomorphism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.7 Stochastic Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.8 Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4. The Small–World Phenomenon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4.1 The Classic Small–World Network Model . . . . . . . . . . . . . . . . . . . . . . . 30
4.2 Finding a General Definition of Small–World Network Models: The Dependency
Between Regularity, Locality, and a High Clustering Coefficient . . . . . . . . . . . 34
4.3 Hybrid Graphs Showing the Small–World Phenomenon. . . . . . . . . . . . . . . . 46
4.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5. Network–Generating Systems and Processes . . . . . . . . . . . . . . . . . . . . . . . . . 59
5.1 Network–Generating Systems: Processes vs. Structural Properties . . . . . . . . . 60
5.2 Bounding the Number of Random Edges in a Graph . . . . . . . . . . . . . . . . . 66Contents 5
5.3 The Relative and Absolute Tree Distance Distribution of Real–World Networks . . 71
5.4 A Quality Measure for Spanning Trees . . . . . . . . . . . . . . . . . . . . . . . . . 80
5.5 BFS Trees as an Approximation of Optimal Backbones . . . . . . . . . . . . . . . . 86
5.6 Problems Related to Finding the Optimal Backbone . . . . . . . . . . . . . . . . . 92
5.7 Local Optimization of the Backbone . . . . . . . . . . . . . . . . . . . . . . . . . . 95
5.8 VisualizationofLargeandComplexNetworkswithHeuristicallyOptimizedBackbones100
5.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
6. The Principle of Locality in the Evolution of Complex Networks . . . . . . . . . . . . . 107
6.1 Observing, Modeling, and Analyzing Dynamic Networks . . . . . . . . . . . . . . . 108
6.2 Evolution of Complex Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
6.3 A Generalized Evolutionary Network Model for Singular Networks . . . . . . . . . 118
6.4 The Design of Efficient Changing Rules - A First Example . . . . . . . . . . . . . . 123
6.5 Reducing the Number of Edges in an Ad-Hoc Communication Network . . . . . . 134
6.6 Self-AdaptingNetworkStructuresforPeer-to-PeerNetworksinRandomFailureand
Attack Scenarios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
6.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
7. Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
8. Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
8.1 Data sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
9. Publications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
9.1 Graph Drawing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
9.2 Centrality Indices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
9.3 Sensor Networks and Peer-to-Peer Systems . . . . . . . . . . . . . . . . . . . . . . 165
9.4 Network and Structural Analysis of SAT problems . . . . . . . . . . . . . . . . . . 165
9.5 C-max Tolerance Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1661. ACKNOWLEDGEMENT
Iloved thetime ofscientific research, andthefreedomI was given to explorewhatever topic Iliked
in my graduate studies. However, the last few months of this time were overshadowed by fears
whether the work is adequate and sheds at least some light on an interesting topic. In this time,
many of my friends, my family, and my fiance Winni have supported me with all of their love.
Thus, I want to thank my family and Winni for their never-ending prayers and care. Winni has
done everything one can do, from listening to alien mathematical problems, to providing excellent
food and endless coffee supply, and enduring my nervousness. I also want to thank my second
family, Familie Zweig, who heartily welcomed me in their family, and I am happy to be Katharina
Zweig in only a few weeks!
Theworkthatispresentedinthisthesisisinspiredbynumerousworksofothers, andoftenworked
outincollaborationwithothersduetotheinterdisciplinarityofthefield. Iwanttothankallofmy
co-authors for our journey into the world of complex systems. Among these the most prominent
is of course my advisor, Michael Kaufmann, who was willing to let me go into this adventure in
a land of the unknown for both of us, with lots of drawbacks until we found the niche in which
this new kind of computer scientist based network analysis was welcomed. I am grateful to have
been part of the DFG SPP 1126, a strong community of mostly computer scientists concerned
with new aspects of algorithms on complex networks with annual, fruitful meetings. Thanks to
my colleagues, Martin Siebenhaller for all the fun and ”Ha!”, Markus Geyer for his humor and
the long hours sitting on an—up to now—untractable problem. Thanks to the students that took
part in the work, Hendrik Post (Small Worlds), Sonja Boldt (Simulation of Complex Networks),
Karin Zimmermann (Robustness of Networks), Jan Vitense (Network Analysis), Andreas Gerasch
(Amazon Crawler), Volker Menrad and Stephan Kottler (Backbones), Valentin Schwamberger
(Clustering Algorithms), Ulrike Sch¨ock (c-max Tolerance Graphs), and to my ’Dynamics of Com-
plex Networks’-reading group, Michael, Timo, and Martin. In summary, all our students, the
colleagues, and Michael as the head of the group have provided a beautiful working environment
with lots of laughter, thank all of you! Thanks also to Marc Begin who has read and corrected,
always with a sense of humor, my English (remaining mistakes ’go on my cap’, as we say ;-)).
Starting as a biochemist in 1996, I am grateful to this day that I discovered that computer sci-
entists are actually paid for solving the mysteries of mathematics and nature I had always been
interested in. I thank God for this beautiful life of mine.ZUSAMMENFASSUNG
DieseArbeitbesch¨aftigtsichmitnetzwerkerzeugendenProzesseninkomplexenSystemenundihrer
Bedeutung fur¨ die Struktur des resultierenden Netzwerkes.
Beginnend 1998 mit einem Artikel von Duncan Watts und Steven Strogatz ub¨ er sogenannte
Kleinwelten [242], haben sich Wissenschaftler aus dem Gebiet der Analyse komplexer Systeme
zunehmend mit der empirischen Untersuchung von realen Netzwerken besch¨aftigt. In vielen Pub-
likationenkonntegezeigtwerden, dasssichdieserealenNetzwerke, alsobeispielsweisedasInternet,
das soziale Netzwerk bestehend aus Verwandten, Bekannten und Kollegen aller Menschen, aber
auch biologische Netzwerke wie beispielsweise das Netzwerk von miteinander interagierenden Hor-
monenimmenschlichenK¨orper,inihrerStrukturstarkvondenbis1998haupts¨achlichverwendeten
Netzwerkmodellen, den sogenannten Zufallsgraphen, unterscheiden. Im Zuge dieser Untersuchun-
gen wurden zahlreiche strukturelle Maße eingefuhr¨ t, deren Werte in realen Netzwerken stark von
denen in den genannten Modellen abweichen, selbst wenn die Anzahl der Knoten und Kanten in
dem zu untersuchenden Netzwerk und dem Modellnetzwerk gleich sind. Zu diesen Maßen geh¨oren
der Clusteringkoeffizient [242], die Gradverteilung [21] und die Assortativita¨t [177], um nur die
bekanntesten zu nennen. Es wurde in verschiedenen Publikationen nahegelegt, dass Netzwerke
mit den gleichen strukturellen Eigenschaften vermutlich auch durch den gleichen Prozess erzeugt
wurden: so wurde beispielsweise fur¨ die Kleinwelten, die gleichzeitig einen hohen Clusteringko-
effizienten und einen kleinen Durchmesser aufweisen, von Watts und Strogatz ein einfacher Neu-
verdrahtungsprozess vorgeschlagen, der aus einem gitter¨ahnlichen Netzwerk einen Graphen mit
den Kleinwelt-Eigenschaften herstellt; fur¨ die sogenannten skalenfreien Netzwerke, in denen die
−γWahrscheinlichkeit P(k) einen Knoten mit Grad k zu finden proportional zu k ist, wurde der
preferential attachment-Prozess vorgeschlagen, der zu Netzwerken mit ebendieser Gradverteilung
fuhr¨ t [21]. Fur¨ die meisten Netzwerke ist es schwierig zu verifizieren, ob sie wirklich mit einem
der genannten Prozesse erzeugt wurden, fur¨ das preferential attachment-Modell konnte es aber
fur¨ die Entwicklung des Internets gezeigt werden [254]. Es wurden teilweise aber auch Prozesse
vorgeschlagen,diezwarzueinemNetzwerkmiteinergewuns¨ chtenStrukturfuhr¨ enko¨nnen,dieaber
ganz offensichtlich in dem System, das zu dem zu analysierenden Netzwerk gefuhr¨ t hat, niemals
abgelaufenseinko¨nnen. ZudiesenModellengeh¨ortbeispielsweisedervonRavaszetal. vorgeschla-
geneProzesszurModellierungderEvolution vonmetabolischen Netzwerken[201]. Dievorliegende
Arbeit stellt die These auf, dass der netzwerkerzeugende Prozess fur¨ das Verst¨andnis komplexer
Netzwerke von großer Bedeutung ist, und zwar haupts¨achlich wegen folgender Aspekte:
1. In den letzten Jahren wurden von Informatikern, Soziologen und anderen Wissenschaftlern
verschiedene analytische Algorithmen entwickelt, die durch Analyse eines komplexen Netz-
werkes eine Aussage ub¨ er ein durch es beschriebenes komplexes System treffen sollen. Zu
diesenAlgorithmengeh¨oreninsbesonderedieBerechnungvonsogenanntenZentralita¨tsindizes
und die Berechnung von Clustern, das sind dichte Teilgraphen, in denen die Knoten stark
miteinander vernetzt sind. Diese Algorithmen haben einen bestimmten Kontext, in dem sie
angewandtwerdendur¨ fen,n¨amlichnurdann,wenndiemeistenKanteneineskomplexenNet-
zwerkes nicht-zuf¨allig erstellt sind, sondern bevorzugt solche Objekte miteinander verbinden,1. Acknowledgement 8
dieineinerklarenBeziehungzueinanderstehen. Stelltsichalsoheraus, dasseinNetzwerkzu
50% aus zuf¨allig vorhandenen Kanten zusammensetzt, ist die Anwendung solcher analytis-
cher Algorithmen nicht mehr angeraten. Die Frage, ob diese Art von netzwerkanalytischen
AlgorithmenaufeingegebenesNetzwerkangewendetwerdendarf,kannalsonurdanngekla¨rt
werden, wenn der netzwerkerzeugende Prozess bekannt ist.
2. Wir postulieren, dass in der Informatik in den n¨achsten Jahrzehnten Soft- und Hardware fur¨
solche Kommunikationsnetzwerke entwickelt werden mus¨ sen, die sich aus mehreren autarken
und egoistischen Akteuren zusammensetzen, sei es im Bereich Sensornetzwerke [49], Peer-to-
Peer-Netzwerke [224] oder dem Internet. Diese Akteure ko¨nnen nicht zu einer bestimmten,
fur¨ alle im Netzwerk befindlichen Teilnehmer guns¨ tigen Handlungsweise gezwungen werden;
stattdessenmus¨ senwirannehmen,dassdieseAkteureimmerversuchenwerden,dasNetzwerk
durch das Knupf¨ en neuer und das L¨oschen alter Kanten in einer fur¨ sie selbst im Moment
guns¨ tigen Weise zu vera¨ndern. Um ein solches komplexes System aus egoistischen und teil-
weiseauchfur¨ denGesamtzusammenhangunddielangfristigeEntwicklungblindenAkteuren
trotzdem steuern zu ko¨nnen, ist es notwendig, die Beweggrunde¨ der Akteure zu verstehen,
und ihnen dann im Gesamtsystem Anreize zu bieten, die automatisch das fur¨ alle guns¨ tigste
Verhalten belohnen und damit f¨ordern. Hier ist es also notwendig, den netzwerkerzeugenden
Prozess im Gesamtsystem zu verstehen, und dann die richtigen Anreize zu liefern, so dass
das lokale Verhalten der Akteure eine global erwuns¨ chte Struktur erzeugt.
In dieser Arbeit haben wir uns mit den folgenden Aspekten von strukturbildenden, netzwerkerzeu-
genden Prozessen besch¨aftigt:
¨1. InKapitel2gebenwireineEinleitungindieThemenderArbeitundeinenUberblickub¨ erdie
bisher publizierten Resultate im Bereich komplexe Systeme, Netzwerkanalyse und komplexe
Netzwerke, soweit sie fur¨ das Verst¨andnis der Arbeit notwendig sind. Dieses Kapitel wird
gefolgt von allgemeinen mathematischen Definitionen im Kapitel 3.
2. In Kapitel 4 besch¨aftigen wir uns mit einem allgemeinen netzwerkerzeugenden Prozess, der
die oben genannten Kleinwelten produziert. Dazu haben wir aus den bisher anerkannten
Kleinwelt-Modellen, die alle auf leicht unterschiedlichen Definitionen dieser Netzwerkfamilie
basieren,einegemeinsameBasisextrahiert,dasvonunssogenannteKleinweltpha¨nomen. Fur¨
dieFamilievonNetzwerken,diediesesPh¨anomenzeigt,beschreibenwirdanneinallgemeines
Netzwerkmodell, das es dem Designer von Netzwerken erm¨oglicht Kleinwelten mit weiteren
gewuns¨ chten strukturellen Eigenschaften flexibel zu gestalten. Der wichtigste Aspekt dieser
Teil der Arbeit ist, dass wir die maximale Anzahl von Zufallskanten, die n¨otig sind um den
Kleinweltcharakter zu erhalten, in diesem Modell leicht berechnen ko¨nnen.
3. Das in Kapitel 4 entwickelte Modell weicht von anderen Kleinweltmodellen insofern ab, als
dasswirfur¨ einzelnerealeNetzwerkekeineAussagedarub¨ ertreffenko¨nnen,obsieKleinwelten
sindodernicht,sondernnurfur¨ netzwerkerzeugendeProzessedarub¨ erurteilenko¨nnen,obsie
Netzwerke mit Kleinweltcharakter generieren oder nicht. In Kapitel 5 fuhr¨ en wir daher den
Begriff des netzwerkerzeugenden Systems und des ihm innewohnenden netzwerkerzeugenden
Prozesses ein. Die Kleinweltenmodelle, die in Kapitel 4 eingefuhr¨ t wurden, gehen davon aus,
dass die meisten realen Netzwerke zumindestens teilweise von einem Zufallsprozess erzeugt
werden. In Kapitel 5 pr¨asentieren wir eine neue Technik, mit der der maximale Anteil von
zuf¨alligen Kanten beschr¨ankt werden kann, und wir zeigen an mehreren realen Netzwerken,
dass dieser Anteil sehr unterschiedlich groß sein kann. Interessanterweise zeigt diese Technik
auch, dass reale Netzwerke eine Struktur haben, die fur¨ verschiedene theoretische Probleme,
beispielsweise die Berechnung von Zeitpla¨nen [159] oder beim L¨osen einer bestimmten Art1. Acknowledgement 9
von linearen Gleichungssystemen [222], eine bessere worst-case-Laufzeit garantiert. Unseres
Wissens ist dies die erste bekannte Struktur von realen Netzwerken, die die Laufzeiten von
Algorithmen verbessert, und wir hoffen, dass diese Entdeckung zu weiteren effizienten Algo-
rithmenaufrealenNetzwerkenfuhr¨ t. DieTechnikbasiertdarauf,indemgegebenenGraphen
einen Spannbaum zu finden, so dass auch die Knoten derjenigen Kanten, die nicht Teil des
Spannbaums sind, in dem gegebenen Baum nur eine kleine Distanz haben, so dass also die
durchschnittlicheDistanzallerKnoten, dieimGesamtgraphendurcheineKantemiteinander
verbunden sind, auch im Spannbaum klein ist. Wir werden zeigen, dass es NP-hart ist, den
nach diesem Kriterium optimalen Baum zu finden, daher werden wir Heuristiken vorstellen,
die zumindestens in den von uns untersuchten realen Netzwerken zufriedenstellende Ergeb-
nisse liefern. In einem letzten Abschnitt dieses Kapitels werden wir kurz skizzieren, wie wir
mit Hilfe eines heuristisch optimierten Spannbaumes reale Netzwerke mit mehr als 1.000
Knoten visualisieren, um mehr ub¨ er die Struktur dieser Netzwerke zu lernen.
4. Kapitel 6 greift dann die oben skizzierte Idee auf, dass sich die Informatik in den n¨achsten
Jahren viel mit dem Design von komplexen Kommunikationsnetzwerken besch¨aftigen wird,
in denen keine direkte Kontrolle auf das Verhalten der einzelnen Akteure ausgeubt¨ werden
kann. Wir besch¨aftigen uns in diesem Gebiet vor allen Dingen mit grundlegenden Fragen,
n¨amlich zuerst mit einem allgemeinen Modell fur¨ die Evolution solcher Netzwerke. Da sich
schon viele verschiedene Gebiete mit der Frage nach netzwerkerzeugenden Prozessen und
deren Modellierung besch¨aftigt haben, stellen wir hier die wichtigsten dieser Modelle vor,
und kombinieren sie zu einem allgemeinen Modell fur¨ die Erzeugung der von uns sogenan-
nten singula¨ren, selbstzentrierten und selbst-organisierten Netzwerke. Wir zeigen an einem
Beispiel, dass die Entwicklung von netzwerkerzeugenden Prozessen fur¨ diese Netzwerke sehr
schwierig sein kann, da unter Umst¨anden die genaue Formulierung einer netzwerkbildenden
RegeldenUnterschiedzwischeneinerexponentiellenundeinerpolynomiellenLaufzeitbisdie
gewuns¨ chte Netzwerkstruktur erreicht ist ausmachen kann. Wir zeigen aber auch, dass diese
¨selbstzentrierten Netzwerke, in denen kein Akteur einen globalen Uberblick hat, in der Lage
ist,zwischenzweiglobalenNetzwerkstrukturennachBedarfzuwechseln,n¨amlichsolchenmit
einerGradverteilungdiePoisson-verteiltist,undeinerskalenfreienGradverteilung. W¨ahrend
erstere Struktur in einem normalen Szenario von Vorteil ist, in dem die bestvernetzten Ak-
teure gezielt attackiert werden, ist die zweitere Struktur immer dann von Vorteil, wenn
Akteure nur zuf¨allig ausfallen. Wir zeigen, dass auch diese dezentralen, lokalen Netzwerke
ihre Struktur je nach Szenario wechseln ko¨nnen, wenn sie sich in einem Netzwerk befinden,
dass es erlaubt, Kanten zu geringen Kosten neu zu knupf¨ en, falls Nachbarn ausfallen.
InsgesamtweisenwirindieserArbeitaufdiegroßeBedeutungvonnetzwerkerzeugendenProzessen
hin, sei es um festzustellen, welche Art von analytischen Methoden angewendet werden kann, oder
um netzwerkerzeugende Prozesse in komplexen Systemen in eine gewuns¨ chte Richtung steuern
zu ko¨nnen. Natur¨ lich ist dieses Feld sehr weit, und sowohl in der Frage, wie wir herausfinden
ko¨nnen, welcher netzwerkerzeugende Prozess zu einem bestimmten Netzwerk gefuhr¨ t hat, als auch
in der Frage, mit welchen Regeln wir ein komplexes System ausstatten sollten, damit ein Net-
zwerk mit einer gewuns¨ chten Struktur entsteht, haben wir in dieser Arbeit erst einige wenige
Beispiele grundlegend bearbeitet. Wir hoffen aber, dass dieser neue Ansatz zum Verst¨andnis und
zur Manipulation komplexer Netzwerke in naher Zukunft Fruc¨ hte tr¨agt, und neue Algorithmen
und Techniken liefert, mit der die steigende Komplexit¨at unserer Umwelt gemeistert werden kann.2. INTRODUCTION
In the last decade a new interest in network analysis has arisen under the name complex network
science. By now, the field is quite dominated by empirical observations and model–building with
questions such as: What is the structure of real–world networks and how can they be modeled?
These questions have mainly been posed and naturally can be very well answered by physicists
and other natural scientists using their large arsenal of methods. At first sight, it may seem that
this new field that is so strongly empirical and often follows only loosely defined questions, has
not much to tell computer scientists, and vice versa. Because this is a doctoral thesis in computer
science,wewilldiscussandexplorewherethisnewfieldofcomplexnetworkscienceopensproblems
that are both interesting for the theoretical computer scientist, and that can be solved with the
methods developed in this field, and also where computer scientists can contribute to the field of
complex systems science.
Complex network science has developed within complex systems science, a field that has rapidly
grown in the last decades [156, 181, 236]. Articles from this field have explained or at least
shed light on topics as different as the rise and fall of stock market indices [156], earth-quake
and snow avalanche analysis [115], the behavior of certain chemical reactions [246], neural network
patternsinneuroscience[131],functionandstructureofbiologicalnetworks[7,168,221],automatic
categorization of web sites [124], and swarm behavior [190, 36], to name but a few.
Sincecomplexnetworkscienceisasubfieldofcomplexsystemsscience,wewillfirstgivearoughidea
of the term complex system in 2.1, together with a short history of the subfield of complex network
science, which is the main topic of this thesis. In 2.2 we discuss network modeling as an approach
for reducing complexity in complex systems and its importance for several applications. In 2.3 we
explorethemainfieldsofinterestforcomputerscientistsintherealmofcomplexnetworkanalysis,
fromanalysis andmodeling oftheWWWto thecorrectuseofso–called contextual algorithms. We
conclude the introduction in 2.4 by an overview of the topics addressed in this thesis.
2.1 Complex Networks in Complex Systems Science
In order to understand the current interest in complex networks, it is easiest to take a short detour
tothehistoryandnotionofcomplexsystemsscience. Forcenturies,itseemedthebestapproachto
understandingnaturalphenomenabydissectingthemintoassmallpartsaspossible,andanalyzing
these parts in isolation, neglecting the interactions they might have with each other. A typical
example of this reductionism can be observed in the analysis of the behavior of falling objects.
Although the behavior of falling objects seems to be complicated to describe, it became much
easier to understand after it was recognized that the fall of any object is subject to two different
forces—namely, gravity and friction. With this discovery it was easy to think of experiments that
could reveal the nature of both forces in isolation. By reducing the whole system to two parts,
beautiful and simple laws to describe gravity and friction emerged that could then be combined to