Vorlesung: Komplexe Netzwerke 2014/15
Dozent: Dr. Anton Klimovsky Contact
Zeit und Ort: Do, 16:15-18:00 @ WSC-N-U-2.04
Beginn: Do, 16.10.2014
Voraussetzungen: Wahrscheinlichkeitstheorie I
Zielgruppe: Master Mathematik.
Umfang: 2 SWS
In den letzten Jahren haben sich Netzwerke zu einem äußerst beliebten Modellierungsparadigma entwickelt. Dabei versucht man in jedem komplexen System ein Netzwerk zu finden, das die Wechselwirkungen zwischen den Systemkomponenten kodiert. Solche komplexen Netzwerken können natürlicher oder künstlicher Ursprungs sein, wie zum Beispiel:
- die Verbindungen von Nervenzellen im menschlichen Gehirn,
- das Stromnetz,
- die soziale Netzwerke,
- die Handelsnetze,
- die Wechselwirkungen zwischen den Genen, Proteinen, usw.
Also, wie modellieren wir die komplexe Netzwerke? Und wie modellieren wir die Prozesse, die auf den Netzwerken verlaufen?
In diesem Kurs werden wir probabilistische Modelle von komplexen Netzwerken und stochastische Prozesse auf den Netzwerken studieren.
Inhalt
- Zufallsgraphen: Erdős–Rényi Graphen, Configuration-Modell, Preferential-Attachment-Modell.
- Graphische Modelle, Exponentielle Graphen.
- Grenzwerte von Graphen.
- Lokale schwache Konvergenz.
- Austauschbarkeit.
- Dichte Graphen.
- Dünne Graphen.
Die Vorlesung kann in englischer Sprache angeboten werden.
Course: Complex Networks
Recently, networks become an extremely popular modeling paradigm. Here, behind each complex system, one often tries to find a network which encodes the interactions between the system's components. Such complex networks can be natural or engineered, e.g.,
- interconnections of neurons in the human brain,
- power grid,
- social networks,
- trade networks,
- interactions between genes, proteins, etc.
So, how do we model networks? How do we model processes that happen on the networks?
In this course, we will study probabilistic models of complex networks and (time-permitting) stochastic processes on them.
Topics:
- Random graphs: Erdős–Rényi Graphs, Configuration Model, Preferential Attachment Model.
- Graphical Models, Exponential Graphs.
- Graph Limits.
- Local weak convergence.
- Exchangeability.
- Dense Graphs.
- Sparse Graphs.
Class by class topics:
- Introduction, examples and some stylized facts about complex networks: Small-worlds, hubs, scale-freeness.
- Degree distribution, sparse graphs, scale-free graphs, clustering coefficient.
- Erdős–Rényi random graphs.
- Local weak convergence.
- Galton-Watson process. Phase transition: Survival vs. extinction.
- Subcritical cluster growth: comparison/coupling with a Galton-Watson process.
- Supercritical cluster growth: comparison/coupling with a random walk.
- Preferential attachment: heuristics, continuum approximation, power law, scale-freeness.
The course is followed by a concentrated seminar.
Seminar:
N.B. The talks will be in Besprechungsraum WSC-N-3.31 on 05.03.2015 at 14:00.
- Configuration model of complex networks.
- Introduction: The configuration model. Lecture Notes. Clauset. 2014.
- Chapter 3 from Random graph dynamics. Durrett. 2007.
- Chapter 7 from Random Graphs and Complex Networks. van der Hofstad. 2014.
- PageRank on complex networks. Theodora Vakouftsi.
- Degree-Degree Dependencies in Random Graphs with Heavy-Tailed Degrees. van der Hofstad, Litvak. 2014. Cheng Cheng.
- Contact process on random graphs. Tim Schönberger.
- Some features of the spread of epidemics and information on a random graph. Durrett. 2010.
- Random graph dynamics. Durrett. 2007, Sections 5.5, 1.6.
- Introduction: Probability on Graphs. Grimmett. 2010, Chapter 6.
Literature
Books:
-
Physics:
- The structure and function of complex networks. Newman. 2003.
- Networks: An introduction. Newman, M. Oxford University Press, 2010.
- Statistical mechanics of complex networks. Albert, R., & Barabási, A.-L. Reviews of modern physics, 74(1), 47. 2002.
-
Math:
- Random Graphs and Complex Networks. van der Hofstad. 2014.
- Probability on Graphs. Grimmett. 2010.
- Random graph dynamics. Durrett. 2007.
- Statistical Mechanics and Algorithms on Sparse and Random Graphs. Montanari. 2013.
- The Sherrington-Kirkpatrick model. Panchenko. Springer. 2013.
- Large networks and graph limits. Lovász. 2012.
Research articles:
- Graph limits and exchangeable random graphs. Diaconis, Janson. 2007.
- Convergent sequences of sparse graphs: A large deviations approach. Borgs, Chayes, Gamarnik. 2013.
- An L^p theory of sparse graph convergence I: limits, sparse random graph models, and power law distributions. Borgs, Chayes, Cohn, Zhao.
- An L^p theory of sparse graph convergence II: LD convergence, quotients, and right convergence.
- Estimating and understanding exponential random graph models. Chatterjee, Diaconis. 2013.