Models and Methods for Random Networks

Spring 2012

Welcome to the Master-level course 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.

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 Friday 10:15-12:00 in room INM 201, with exercise sessions 12:15-13:00. The tentative calendar below is subject to changes.
 
W1 24.02.2012 Course Introduction, Tree Percolation, Branching Processes PT
W2 02.03.2012 Random Graphs 1: Models, Threshold Functions, Appearance of Subgraphs MG
W3 09.03.2012 Random Graphs 2: Giant Component and Connectivity MG
W4 16.03.2012 Random Graphs 3: The Random Regular Graph PT
W5 23.03.2012 Percolation 1: Lattice Percolation, Subcritical and Supercritical Phases PT
W6 30.03.2012 Percolation 2: Site and Continuum Percolation Models PT
W7 06.04.2012 Official holiday
W8 20.04.2012 Random Graphs 4: Small World Networks, Scale-Free Networks MG
W9 27.04.2012 Evolution and Dynamics 1: Network Navigation MG
W10 04.05.2012 Evolution and Dynamics 2: Epidemics and Gossip Algorithms PT
W11 11.05.2012 Evolution and Dynamics 3: Network and Source Discovery MG
W12 20.05.2012 Applications 1: Social, Information, and Wireless Networks PT
W13 25.05.2012 Applications 2: Social, Information, and Wireless Networks MG
W14 01.06.2011 Project presentations All

Project, Homeworks, Exam

  • The course will have a set of 5 howework sets (one every two weeks).
  • A term paper will be due at the end of the course in June. 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: 10% homeworks (between 4 and 6) + 40% term paper (project) + 50% final exam.

Instructors

Teaching Assistants

Support Documents

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).
  • D. Easley, J. Kleinberg. Networks, Crowds, and Markets: Reasoning About a Highly Connected World, Cambridge University Press, 2010 (electronic version).
  • G. Grimmett, Percolation (2nd edition), Springer, 1999.
  • S. Janson, T. Luczak, A. Rucinski, Random Graphs, Wiley, 2000.
  • R. Meester and R. Roy, Continuum Percolation, Cambridge University Press, 1996.