Models and Methods for Random Networks

2006-07

Welcome to the graduate school lecture on Models and Methods for Random Networks (informally a.k.a. Networks out of Control). This document is regularly updated to reflect the schedule of the course.

Please subscribe to the class mailing list class_ic36_2006@groupes.epfl.ch.

Goal of the course

The goal of this class is to acquire mathematical tools and engineering insight about networks whose structure is random.

Many communication networks, such as the global Internet and its multiple interconnected autonomous domains, mobile ad hoc and embedded sensor networks, social networks, and peer-to-peer overlay networks, usually evade detailed engineering and exhaustive measurement to rely instead on principles of self-organization. This new world of massive scale, lack of central control, and randomness requires new theoretical tools to reason about networks and their behavior, as well as new approaches to engineer for and measure aggregate properties. Most of these tools are borrowed from other fields, such as random graph theory, statistical physics, nonlinear dynamical systems, random algorithms, developmental biology, and game theory.

This course will bring together elements of these theories and their application to "large-scale, self-organized or uncontrolled" networks. It will provide an introduction to and perspective on this emerging field, and an opportunity to track and discuss new developments. The course will balance mathematical rigor with practical lessons for engineering.

Room and Tentative Calendar

The lecture is every Monday 14:15-17:00 in room INM 11. The tentative calendar below is subject to changes.
 
W1 23.10.2006 Introduction to percolation. Bond percolation: setting and basic tools (BK, FKG). PT
W2 30.10.2006 Bond percolation: the subcritical and supercritical phases. PT
W3 06.11.2006 Random Graphs: models, threshold functions, appearance of subgraphs. MG
W4 13.11.2006 Random Graphs: emergence of giant component, connectivity. MG
W5 20.11.2006 Bond Percolation: the critical threshold PT
W6 27.11.2006 Site and Tree Percolation. PT
W7 04.12.2006 Full Connectivity vs Partial Connectivity in Random Geometric Graphs. Continuum Percolation: the Boolean model, application to wireless multi-hop networks. PT
W8 11.12.2006 Random Regular Graphs MG
W9 18.12.2006 Small World Networks. MG
W10 08.01.2006 Capacity of Static Wireless Multi-Hop Networks. Throughput scaling laws. PT
W11 15.01.2006 Navigability. MG
W12 22.01.2006 Scale-Free Networks. MG
W13 29.01.2006 Mobile Networks: Capacity and routing. MG
W14 05.02.2006 Review, project presentations. MG,PT

Project, Homeworks, Exam

  • The course will have a set of 4 howework sets (one every two weeks).
  • A term paper will be due at the end of the course in February. The project develops one topic of the course you are most interested in. The topic can be one proposed by you or by us. It can be more theoretically or more practically oriented.
  • The final exam is written and takes place during the exam session.
  • Grade: 20% homeworks (best 3 of 4) + 30% term paper (project) + 50% final exam.

Instructors

Support documents

Slides

Homework sets

References

The following texts are relevant to the material covered in the class:
  • A. D. Barbour, L. Holst and S. Janson, Poisson Approximation, Oxford Science Publications, 1992.
  • B. Bollobas, Random Graphs (2nd edition), Cambridge University Press, 2001.
  • R. Durrett, Random Graph Dynamics, Cambridge University Press, 2006 (electronic version).
  • G. Grimmett, Percolation (2nd edition), Springer, 1999.
  • S. Janson, T. Luczak, A. Rucinski, Random Graphs, Wiley, 2000.