Networks out of control
Weekly outline
-
Welcome to the Master-level course Networks Out of Control (informally a.k.a. Models and Methods for Random Networks).
Course Description
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.
Projects, homework, exam
- The course will have a set of homework sets (one every two weeks); you may discuss the homework problems with other students but may not use online resources and must write up your solutions on your own.
- A term paper will be due at the end of the course in May. 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. A short report has to be handed in, and a presentation in front of the class is done at the end of the semester. The report has to be turned in one week before the presentation, and is maximum 4 pages (double column) long. We suggest to write the report in Latex with this template. If you want to use another text editor, try to use a template whose output is the closer possible to that of the given template.
List of proposed papers (sent by email)
Presentation schedule (sent by email)
- The final exam takes place on Thursday June 21, 8h15am (Room CM 1104). The exam No homework or former exam, nor their solutions, are allowed. No computing device of any kind is allowed. You will be asked questions to show your level of understanding of the concepts and material covered in class, as well as exercises similar but different from those given as homework. is open book, but only the official class notes, slides posted on moodle and your own personal notes are allowed. In particular, no textbook, no article nor any other document are allowed.
- Grade: 10% homework (between 4 and 6) + 40% term paper (project) + 50% final exam.
- The homeworks are individual, you may discuss some problems and approaches with your fellow students, but must complete the solutions for all problems by yourself.
Instructors
Teaching assistant
- Farnood Salehi (BC 250)
Support documents
Class notes (See under weekly schedule)References
The following texts are relevant to the material covered in the class:- B. Bollobas, Random Graphs (2nd edition), Cambridge University Press, 2001.
- D. Easley, J. Kleinberg. Networks, Crowds, and Markets: Reasoning About a Highly Connected World, Cambridge University Press, 2010.
- R. Durrett, Random Graph Dynamics, Cambridge University Press, 2006.
- M. Jackson, Social and Economic Networks, Princeton University Press, 2008.
- G. Grimmett, Percolation (2nd edition), Springer, 1999.
- A. D. Barbour, L. Holst and S. Janson, Poisson Approximation, Oxford Science Publications, 1992.
- S. Janson, T. Luczak, A. Rucinski, Random Graphs, Wiley, 2000.
- R. Meester and R. Roy, Continuum Percolation, Cambridge University Press, 1996.
-
Course Introduction
- Tree Percolation
- Branching Processes
Instructor: Patrick Thiran
Exercise set 1 (due in class on March 5)- Tree Percolation
- Branching Processes
- Tree Percolation
-
Random Graphs 1
- Models
- Threshold Functions
- Appearance of Subgraphs
Instructor: Patrick Thiran
-
Random Graphs 2
- Giant Component
Instructor: Patrick Thiran
Exercise Set 2 (due in class on March 19). - Giant Component
-
Random Graphs 3
- Connectivity of Random G(n,p)
- Random Regular Graphs G(n,r) and the configuration model
Instructor: Patrick Thiran
- Connectivity of Random G(n,p)
-
Random Graphs 4
- Connectivity of Random Regular Graphs
Instructor: Patrick Thiran
Real-World Networks 1
- Clustering & Small World Networks
Instructor: Elisa Celis
Exercise Set 3 (due in class on April 9). -
Real World Networks 2
- Clustering & Small World Networks (continued)
- Homophily & Aggregation
- Network Navigation & Decentralized Search
Instructor: Elisa Celis
-
Spring Break
-
Real-World Networks 3
- Network Navigation and Decentralized Search (continued)
Exercise Set 4 (due in class on April 23).
-
Real-World Networks 4
- Scale-Free Networks & Preferential Attachment
- Complex Networks: Affiliation Networks and Signed Networks
Email Farnood with project details by Friday 20 April:
- team members
- top-3 preferred papers in order
- availability to present in the 2pm-4pm time slot
-
Evolution and Dynamics 1
- Cascades due to Direct-Benefit Effects
- Cascades due to Rational Effects
Instructor: Elisa Celis
Homework 5 -- due May 9th in class.
- Cascades due to Direct-Benefit Effects
-
Evolution and Dynamics 2
- Network Formation Games
Instructor: Elisa Celis
-
Percolation 1
- Lattice Percolation: existence of a phase transition
- Lattice Percolation: Sub-critical Phase
- Lattice Percolation: Super-critical Phase
Instructor: Patrick Thiran
Homework 6 -- due May 28th in class (just before your presentation).
- Lattice Percolation: existence of a phase transition
-
Percolation 2
- Critical threshold
- Epidemics
Instructor: Patrick Thiran
-
Official holiday
- No Class
- Project Report due on Friday May 25 at Noon
-
Project Presentations
Project presentations to be scheduled on Monday 28 May from 2pm-7pm.
Following popular request, we posted (below) the final that was given in 2014. Important: Note that the class material has changed quite significantly compared to 2014, and therefore the questions of this past exam are NOT necessarily representative of the questions that will be asked for the final 2018, and which will bear on the material covered in class and exercises in 2018.
Reminder: The exam is open book, but only the official class notes posted on this moodle site and your own personal notes are allowed. No textbook, no article nor any other document are allowed. No homework or former exam, nor their solutions, are allowed.