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

          List of assigned projects

          Presentation schedule

    • The final exam takes place on Monday 27.06.2016 from 08h15 until 11h15 (Room INJ218). The exam is open book, but only the official class notes 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.

  • 20 February - 26 February

    Course Introduction

    • Tree Percolation
    • Branching Processes

    Instructor: Patrick Thiran

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


  • 27 February - 4 March

    Random Graphs 1

    • Models
    • Threshold Functions
    • Appearance of Subgraphs

    Instructor: Patrick Thiran

  • 5 March - 11 March

    Random Graphs 2

    • Giant Component
    • Connectivity

    Instructor: Patrick Thiran

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

    • 12 March - 18 March

      Random Graphs 3

      • Connectivity (continued)
      • Random Regular Graphs

      Instructor: Patrick Thiran


    • 19 March - 25 March

      Real-World Networks 1

      • Scale-Free Networks & Preferential Attachment
      • Clustering & Small World Networks

      Instructor: Elisa Celis

    • 26 March - 1 April

      Spring break

      • 2 April - 8 April

        Real-World Networks 2

        • Network Navigation & Decentralized Search
        • Homophily

        Instructor: Elisa Celis

      • 9 April - 15 April

        Percolation 1

        • Lattice Percolation: existence of a phase transition
        • Lattice Percolation: Sub-critical Phase

        Instructor: Patrick Thiran


      • 16 April - 22 April

        Percolation 2

        • Lattice Percolation: Super-critical phase
        • Critical Threshold

        Instructor: Patrick Thiran


        • 23 April - 29 April

          Evolution and Dynamics 1

          • Epidemics
          • SI, SIR, SIS models

          Instructor: Patrick Thiran


        • 30 April - 6 May

          Evolution and Dynamics 2

          • Cascades due to Direct-Benefit Effects
          • Cascades due to Rational Effects

          Instructor: Elisa Celis

        • 7 May - 13 May

          Evolution and Dynamics 3

          • Network Formation Games

          Instructor: Elisa Celis

        • 14 May - 20 May

          Real-World Networks 3

          • Network Formation (continued -- Potential Games)
          • Complex Networks: Affiliation Networks and Signed Networks

          Instructor: Elisa Celis


        • 21 May - 27 May

          Project Presentations

          The project presentations will take place on May 24 and 25 according to the schedule published above.