# Fiches de cours 2018-2019

## Networks out of control

English

#### Remarque

Pas donné en 2018-19 - Cours biennal donné les années impaires

#### Summary

The goal of this class is to acquire mathematical tools and engineering insight about networks whose structure is random, as well as decentralized processes that take place on these networks.

#### Content

• Course Introduction: Tree Percolation, Branching Processes
• Random Graphs 1: Models, Threshold Functions, Appearance of Subgraphs
• Random Graphs 2: Giant Component and Connectivity
• Random Graphs 3: Other models: the Random Regular Graph, Small World Networks, Scale-Free Networks.
• Random Geometric Graphs: Introduction to Percolation Theory.
• Evolution, Dynamics and Inference 1: Epidemics, Network and Source Discovery.
• Evolution, Dynamics and Inference 2: Information Cascades.
• Evolution, Dynamics and Inference 3: Network Navigation and Price of Anarchy.
• Applications 1: Network Formation Games.
• Applications 2: Homophily, Structural Balance.

#### Keywords

Random graphs, percolation theory, social networks, communication networks.

#### Learning Prerequisites

##### Required courses

Stochastic models in communication (COM-300), or equivalent.

##### Important concepts to start the course

Basic probability and stastistics; Markov chains; basic combinatorics.

#### Learning Outcomes

By the end of the course, the student must be able to:
• Analyze social and communication systems
• Model such systems as stochastic models
• Compute key properties of these models

#### Teaching methods

Ex cathedra lectures, exercises, mini-project

#### Expected student activities

Attending lectures, bi-weekly homeworks, mini-project incl. student presentation at the end of semester, final exam.

#### Assessment methods

1. Homeworks 10%
2. Mini-project 40%
3. Final exam 50%.

#### Supervision

 Office hours Yes Assistants Yes Forum No

#### Resources

##### Bibliography

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

##### Notes/Handbook

Class notes will be available on the course website.

### Semaine de référence

LuMaMeJeVe
8-9
9-10
10-11
11-12
12-13
13-14
14-15
15-16
16-17
17-18
18-19
19-20
20-21
21-22
En construction

Cours
Exercice, TP
Projet, autre

### légende

• Semestre d'automne
• Session d'hiver
• Semestre de printemps
• Session d'été
• Cours en français
• Cours en anglais
• Cours en allemand