| Autor(en): |
Michael Behrisch |
Titel: |
Stochastical models for networks in the life sciences |
| Gutachter: |
Hans Jürgen Prömel; Anuschirawan Taraz; Amin Coja-Oghlan |
| Erscheinungsdatum: |
21.01.2008 |
| Volltext: |
pdf
(urn:nbn:de:kobv:11-10085374)
|
| Fachgebiet(e): |
Informatik |
| Schlagwörter (ger): |
zufälliger Graph, große Komponente, Schnittgraph, komplexes Netzwerk |
| Schlagwörter (eng): |
random graph, giant component, intersection graph, complex network |
| Einrichtung: |
Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II |
| Zitationshinweis: |
Behrisch, Michael:
Stochastical models for networks in the life sciences;
Dissertation,
Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II , publiziert am 21.01.2008, urn:nbn:de:kobv:11-10085374
|
Metadatenexport:
 Um
den gesamten Metadatensatz im Endnote- oder
Bibtex-Format zu speichern,
klicken Sie bitte auf den entsprechenden Link.
|
Endnote
Bibtex
|
| print on demand:
Wenn
Sie auf dieses Icon klicken, können Sie
ein Druckexemplar dieser Publikation bestellen.
|
|
| Diese Seite taggen:
Diese
Icons führen auf so genannte Social-Bookmark-Systeme, auf denen Sie
Lesezeichen anlegen, persönliche Tags vergeben und Lesezeichen anderer Nutzer
ansehen können.
|
|
| Abstract (ger): |
| Motiviert durch strukturelle Eigenschaften molekularer Ähnlichkeitsnetzwerke
werden die Evolution der größten Komponente eines Netzwerkes in zwei verschiedenen
stochastischen Modellen, zufälligen Hypergraphen und zufälligen
Schnittgraphen, untersucht.
Zuerst wird bewiesen, dass die Anzahl der Knoten in der größten Komponente
d-uniformer Hypergraphen einer Normalverteilung folgt. Der Beweis nutzt dabei ausschließlich probabilistische
Argumente und keine enumerative Kombinatorik. Diesem grundlegenden Resultat folgen
weitere Grenzwertsätze für die gemeinsame Verteilung von Knoten- und
Kantenzahl sowie Sätze zur Zusammenhangswahrscheinlichkeit zufälliger
Hypergraphen und zur asymptotischen Anzahl zusammenhängender Hypergraphen.
Da das Hypergraphenmodell einige Eigenschaften der Realweltdaten nur unzureichend
abbildet, wird anschließend die Evolution der größten Komponente in
zufälligen Schnittgraphen, die Clustereigenschaften
realer Netzwerke widerspiegeln, untersucht. Es wird gezeigt,
dass zufällige Schnittgraphen sich von
zufälligen (Hyper-)Graphen dadurch unterscheiden, dass
(bei einer durchschnittlichen Nachbaranzahl von
mehr als eins) weder die größte Komponente linear
noch die zweitgrößte Komponente logarithmisch groß in Abhängigkeit von
der Knotenzahl ist.
Weiterhin wird ein Polynomialzeitalgorithmus zur Überdeckung der
Kanten eines Graphen mit möglichst wenigen Cliquen (vollständigen Graphen) beschrieben
und seine asymptotische Optimalität im Modell der zufälligen Schnittgraphen bewiesen.
Anschließend wird die Entwicklung der chromatischen Zahl untersucht
und gezeigt, dass zufällige Schnittgraphen
mit hoher Wahrscheinlichkeit mittels verschiedener Greedystrategien
optimal gefärbt werden können.
Letztendlich zeigen Experimente auf realen Netzen eine Übereinstimmung
mit den theoretischen Vorhersagen und legen eine gegenseitige Zertifizierung
der Optimalität von Cliquen- und Färbungszahl durch Heuristiken nahe.
|
| Abstract (eng): |
| Motivated by structural properties of molecular similarity networks we study the behaviour
of the component evolution in two different stochastic network models, that is random
hypergraphs and random intersection graphs.
We prove gaussian distribution for the number of vertices in the giant component of a random
d-uniform hypergraph. We provide a
proof using only probabilistic arguments, avoiding enumerative methods completely.
This fundamental result is followed by further limit theorems concerning joint distributions
of vertices and edges as well as the connectivity probability of random hypergraphs
and the number of connected hypergraphs.
Due to deficiencies of the hypergraph model in reflecting properties
of the real--world data, we switch the model and study the evolution of the order of the largest
component in the random intersection graph model which reflects some
clustering properties of real--world networks. We show that for appropriate
choice of the parameters random intersection graphs differ from random (hyper-)graphs in
that neither the so-called giant component, appearing when the average number of neighbours
of a vertex gets larger than one, has linear order nor is the second largest of
logarithmic order in the number of vertices.
Furthermore we describe a polynomial time algorithm for covering graphs with
cliques, prove its asymptotic optimality in a random intersection graph
model and study the evolution of the chromatic number in the model showing
that, in a certain range of parameters,
these random graphs can be coloured optimally with high probability using different greedy
algorithms.
Experiments on real network data confirm the positive theoretical predictions and
suggest that heuristics for the clique and the chromatic number can work hand in hand
proving mutual optimality.
|
Zugriffsstatistik:
Die Daten für die Zugriffsstatistik der einzelnen Dokumente
wurden aus den durch AWStats aggregierten Webserver-Logs erstellt.
Sie beziehen sich auf den monatlichen Zugriff auf den Volltext sowie
auf die Startseite. Die Zugriffsstatistik wird nicht standardisiert erfasst und kann maschinelle Zugriffe enthalten.
Bei Formatversionen eines Dokuments, die aus mehreren Dateien bestehen
(insbesondere HTML), wird jeweils der monatlich höchste Zugriffswert
auf eine der Dateien (Kapitel) des Dokuments angezeigt.
Um die detaillierten Zugriffszahlen zu sehen,
fahren Sie bitte mit dem Mauszeiger
über die einzelnen Balken des Diagramms.
|
  | | | | | | | | | | | | | | | | | | | Jun
11 | Jul
11 | Aug
11 | Sep
11 | Oct
11 | Nov
11 | Dec
11 | Feb
12 | Apr
12 | May
12 | Jun
12 | Jul
12 | Aug
12 | Sep
12 | Oct
12 | Nov
12 | Dec
12 | Jan
13 | Apr
13 |
| Monat | Jun
11 | Jul
11 | Aug
11 | Sep
11 | Oct
11 | Nov
11 | Dec
11 | Feb
12 | Apr
12 | May
12 | Jun
12 | Jul
12 | Aug
12 | Sep
12 | Oct
12 | Nov
12 | Dec
12 | Jan
13 | Apr
13 | | Startseite | 5 | 5 | 3 | 4 | | 3 | | 1 | | | 5 | 8 | 5 | | | | | 2 | 1 | | PDF | 4 | | 5 | 2 | 4 | 4 | 6 | 5 | 5 | 5 | 3 | 11 | 4 | 6 | 14 | 7 | 4 | 16 | 15 |
Gesamtzahl der Zugriffe seit Jun 2011: - Startseite – 42 (2.21 pro Monat)
- PDF – 120 (6.32 pro Monat)
|
