Weekly outline

  • Networks out of control

    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 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. 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.
    • 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


    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.

  • 19 February - 25 February

    Course Introduction

    • Tree Percolation
    • Branching Processes

    Instructor: Patrick Thiran

    Exercise set 1 (due in class on March 5)
    • Tree Percolation
    • Branching Processes


  • 26 February - 4 March

    Random Graphs 1

    • Models
    • Threshold Functions
    • Appearance of Subgraphs

    Instructor: Patrick Thiran

  • 5 March - 11 March

    Random Graphs 2

    • Giant Component

    Instructor: Patrick Thiran

    Exercise Set 2 (due in class on March 19).

  • 12 March - 18 March

    Random Graphs 3

    • Connectivity of Random G(n,p)
    • Random Regular Graphs G(n,r) and the configuration model

    Instructor: Patrick Thiran


  • 19 March - 25 March

    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).

  • 26 March - 1 April

    Real World Networks 2

    • Clustering & Small World Networks (continued)
    • Homophily & Aggregation
    • Network Navigation & Decentralized Search

    Instructor: Elisa Celis


  • 2 April - 8 April

    Spring Break

  • 9 April - 15 April

    Real-World Networks 3

    • Network Navigation and Decentralized Search (continued)
    Instructor: Elisa Celis


    Exercise Set 4 (due in class on April 23).

  • 16 April - 22 April

    Real-World Networks 4

    • Scale-Free Networks & Preferential Attachment
    • Complex Networks: Affiliation Networks and Signed Networks
    Instructor: Elisa Celis


    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


  • 23 April - 29 April

    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.

  • 30 April - 6 May

    Evolution and Dynamics 2

    • Network Formation Games

    Instructor: Elisa Celis


  • 7 May - 13 May

    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).


  • 14 May - 20 May

    Percolation 2

    • Critical threshold
    • Epidemics

    Instructor: Patrick Thiran


  • 21 May - 27 May

    Official holiday

    • No Class
    • Project Report due on Friday May 25 at Noon


  • 28 May - 3 June

    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.