Structural properties of scale-free networks [Elektronische Ressource] / von Ramon Xulvi-Brunet

Xulvi-Brunet Ramon

Sujets

• Physik

Informations

• Publié par: humboldt-universitat_zu_berlin
• Publié le: 01 janvier 2006
• Nombre de lectures: 29
• Langue: Deutsch
• Poids de l'ouvrage: 8 Mo

Extrait

Structural properties of scale-free networks
DISSERTATION
zur Erlangung des akademischen Grades
doctor rerum naturalium
(Dr. rer. nat.)
im Fach Physik
eingereicht an der
Mathematisch-Naturwissenschaftlichen Fakultät I
der Humboldt-Universität zu Berlin
von
Ramon Xulvi-Brunet
Präsident der Humboldt-Universität zu Berlin:
Prof. Dr. Christoph Markschies
Dekan der Mathematisch-Naturwissenschaftlichen Fakultät I:
Prof. Thomas Buckhout, Ph. D.
Gutachter:
1. Prof. Dr. Igor Sokolov
2. Prof. Dr. Bernd Blasius
3. Prof. Dr. Lutz Schimansky-Geier
eingereicht am: 28. April 2006
Tag der mündlichen Prüfung: 22. Juni 2006Zusammenfassung
Netzwerkesindüberall,vonderelektrischenStromversorgungüberdieBiochemiederZellen,das
Internet bis hin zu sozialen Netzen. Netzwerke als mathematisches Konzept haben sich in den
letzten Jahren zu einem wichtigen Werkzeug der Beschreibung komplexer Systeme entwickelt.
Ihre grundlegende Eigenschaft ist, dass sie aus einer grössen Anzahl dynamischer Elemente be-
stehen, die sich gegenseitig beeinflussen und dabei nicht linear gekoppelt sind. Die moderne
Netzwerkwissenschaft will die Wechselwirkung zwischen den einzelnen Untereinheiten erklären
unddavonausgehendverständlichmachen,aufwelcheWeiseProzesseaufeinemNetzwerkstatt-
finden können. Zum Beispiel wird untersucht, wie die Struktur sozialer Netze die Ausbreitung
von Information oder von Krankheiten beeinflusst, wie die Topologie des World Wide Web das
Surf-Verhalten oder die Funktionalität von Suchmaschinen beeinträchtigt oder welche Auswir-
kungendieHierarchieinökologischenNischenaufdiePopulationsdynamikdereinzelnenSpezies
hat. Darüber hinaus gilt es herauszufinden, welche grundlegenden Prinzipien der Evolution rea-
ler Netzwerke zugrunde liegen, das heißt nach welchen Regeln sich einerseits die Untereinheiten
entwickelnundwelchenEinflussandererseitsderenVernetzunghat.DievorliegendeDissertation
beschäftigt sich sowohl mit der Topologie verschiedener Netzwerke als auch mit den der Evoluti-
on zugrunde liegenden Prinzipien. Schwerpunkte liegen dabei auf den folgenden zwei Aspekten:
erstens dem Einfluss von so gennanten “vertex-pair correlations”, das heißt Korrelationen zwi-
schen den Untereinheiten, auf die Topologie und zweitens der Auswirkung der Geographie auf
die Netzwerkentwicklung. Es wird der bedeutende Einfluss aufgezeigt, den die Korrelationen auf
wichtige statistische Größen der Netzwerke haben. Weiterhin analysieren wir die Perkolations-
eigenschaften, die Aufschluss über die Empfindlichkeit gegenüber Störungen in der Vernetzung
geben. Damit können zum Beispiel Fragen aus der Epidemiologie diskutiert werden. Es zeigt
sich, dass die Topologie vieler Netzwerke und ihre Perkolationseigenschaften deutlich von Kor-
relationen beeinflusst werden. Schließlich untersuchen wir im letzten Teil dieser Arbeit, wie die
Einbettung von Netzwerken in eine endlich-dimensionale Geographie auf die Modellierung und
Entwicklung Web-ähnlicher Systeme Einfluss nimmt.
Schlagwörter:
Netzwerke, Graphentheorie, komplexe Systeme, PerkolationAbstract
Networks are all around us, from electrical power grids to the biochemistry of cells, from the
Internet to social webs. The mathematical concept of network has recently been turned into an
important tool for describing complex systems, whose principal characteristic is that they con-
sist of a large number of mutually interacting dynamical parts which are coupled in a nonlinear
fashion. Modern network science attempts to explain the structure of interactions between the
subunits of a system in order to understand their functioning and the processes taking place in
them. It tries, for instance, to grasp how the structure of social networks affects the spread of
information or human diseases, how the structure of the World Wide Web influences the search
enginesandsurfingbehavior, orhowthehierarchyofecologicalnichesaffectspopulationdynam-
ics. Beyond this, the ultimate goal of network science is to discover what generating principles
exist behind the evolution of real systems. It tries to find the fundamental principles under
which the subunits evolve, and the wiring of interactions. This thesis centres both on the study
of the topological structure of networks and the analysis of the underlying principles responsible
for their evolution. More specifically, it concentrates on the following aspects: the influence of
vertex-pair correlations on network topology, the network percolation problem, which is closely
related to the spreading of epidemics and the robustness of networks, and the effects of geog-
raphy as a generating element. We show that important topological and percolation properties
change considerably when modifying the connection probabilities between vertices, and that
geography as well plays a crucial role in the modeling of evolving real web-like systems.
Keywords:
networks, graph theory, complex systems, percolationContents
1 Introduction 1
1.1 Some preliminary words . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Concepts and measures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Networks in the real world . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.4 Classical models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2 Statistical properties of evolving networks 14
2.1 Beyond the Barabási-Albert construction . . . . . . . . . . . . . . . . . . . . . . 14
2.2 Properties of important scale-free constructions . . . . . . . . . . . . . . . . . . . 17
3 Vertex-pair correlations in scale-free networks 22
3.1 Properties of uncorrelated networks . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.2 Assortativity and dissortativity . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.3 Highly triangulated scale-free networks . . . . . . . . . . . . . . . . . . . . . . . . 43
3.4 Topological properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
4 Percolation 70
4.1 The percolation problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
4.2 Typical quantities and approaches . . . . . . . . . . . . . . . . . . . . . . . . . . 75
4.3 Phase transitions in lattices and random graphs . . . . . . . . . . . . . . . . . . . 77
4.4 Percolation on scale-free networks . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
5 Evolving networks under geographical constraints 107
5.1 Preferential attachment with disadvantaged long-range connections . . . . . . . . 108
5.2 Interdependence between geography and vertex attractiveness . . . . . . . . . . . 114
6 Conclusions 123
ivChapter 1
Introduction
1.1 Some preliminary words
In the last few years numerous real-world systems have been successfully described by networks.
The Internet and the World Wide Web are two typical examples of systems which are widely
considered man-made networks. Other examples of networked systems can be found in many
different fields, ranging from biology to communication systems: metabolic reactions in the
living cell, protein-protein interactions, electrical power grids, ecological food webs, electronic
circuits, airline routes, chains of historical events, sexual relations between groups of persons,
etc. In effect, networks surround us. More examples are protein folding and genetic regulatory
networks, networks in linguistics, scientists’ collaboration networks, road and railway networks,
neural networks, etc.
A network is a collection of entities, which we will call points, nodes or vertices, some of
which are joined pairwise. Connections between vertices are usually called lines, links or edges.
In this way, the Internet may certainly be modeled as a network. Here the vertices could be
the routers and the edges the physical connections between them. The representation of a
system by a network is, however, not unique, and depends on the level of abstraction that we
use. For instance, the Internet could also be considered a collection of subnetworks, which
could be composed of hundreds of routers and computers that are connected together. Both
representations are valid and depend on the properties that we want to study in the system
and on the level of simplification in our approach. In fact, the Internet has been studied at
both presented levels, the router level (where vertices represent routers) and inter-domain or
autonomous system level (where subnetworks are vertices). Another well-known network is the
World Wide Web. Here, web pages (documents) are the vertices of the network and the edges
representthehyperlinks(URLs)thatpointfromonepagetoanother. Metabolicreactionsinthe
cell are networks where vertices represent chemical substrates (such as ATP, ADP, or H O)2
and edges represent the predominantly directed chemical reactions in which these substrates
can participate. Social networks are persons or groups of people (vertices) showing a pattern of
contacts or interactions between them (edges). Thus, all systems capable of being modeled as
a set of entities which are somehow connected between them can be represented by a network.
Given that many physical structures can be described in this way, it is not surprising that
networks abound in the world.
Traditiona