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

Katharina Zweig

Sujets

• Mathematics

Informations

• Publié par: eberhard_karls_universitat_tubingen
• Publié le: 01 janvier 2007
• Nombre de lectures: 21
• Langue: English
• Poids de l'ouvrage: 9 Mo

Extrait

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 di