Code
IGFF NET 4103
Level
M1
Graduate
Graduate
Semester
Fall
Domain
Réseaux
Program
Programme Ingénieur
Language
Français/French,Anglais/English
ECTS Credits
3
Class hours
30
Workload
75
Program Manager(s)
Department
- Réseaux et Services de Télécom
Organisation
Cours/TD/TP/projet/examen : 10/0/15/5/0Learning objectives
À l’issue de la première partie du module
1. Les étudiants seront capables d’utiliser et de concevoir dans le langage python les différents algorithmes classiquement utilisés pour la manipulation de graphes :
1.a. Conception d’un algorithme de parcours de graphes
1.b. Conception des algorithmes pour le calcul des métriques suivantes :
1.b.i. Closeness,
1.b.ii. Betweeness
2. Les étudiants seront capables d’appliquer l'algorithme du PageRank pour indexer les pages web d'une base de données des pages des Wikipédia ainsi que concevoir algorithme dans le langage python
2.a. Expliciter la problématique de la classification des pages web
2.b. Représenté du web sous la forme d’un graphe dirigé
2.c. Présenter un graphe sous la forme d’une matrice stochastique
2.d. Résoudre le vecteur d’état stationnaire d’une chaîne de Markov
2.e. Définir les conditions d’applicabilités d’une chaîne de Markov dans le cadre du théorème de Perron–Frobenius
2.f. Transformer la matrice du graphe du web afin qu’il garantisse les conditions d’applicabilité du théorème de Perron–Frobenius
2.g. Concevoir un algorithme utilisant la sparcité du graphe du web pour résoudre le problème du PageRank pour les très grands graphes.
3. Les étudiants seront capables de distinguer et raisonner sur les différentes classes de graphes suivantes :
3.a. Les graphes Scale-free (sans échelle)
3.b. Les graphes petit monde
3.c. Les graphes aléatoires
4. Les étudiants seront capables d’analyser et d’identifier les critères qui définissent la robustesse et la résilience d’un graphe.
5. Les étudiants seront capables de modéliser les processus dynamiques en réseau suivant :
5.a. Mécanismes de diffusion, et cascade informationnelle dans les réseaux sociaux
5.b. Algorithmes de détection de communauté dans les graphes.
6. Lors de la dernière séance du module, les étudiants seront capables de formuler à l’oral la problématique d’un article scientifique, et interpréter la problématique décrite dans l’article scientifique par une/des notions développées durant ce module.
CDIO Skills
- 1.1.1 - Mathematics (including statistics)
- 2.1.2 - Modeling
- 2.3.1 - Thinking Holistically
- 2.3.2 - Emergence and Interactions in Systems
- 4.1.3 - Society's Regulation of Engineering
- 4.1.5 - Contemporary Issues and Values
- 4.4.5 - Multidisciplinary Design
- 4.5.3 - Software Implementing Process
- 4.5.5 - Test, Verification, Validation, and Certification
Prerequisites
Python, Algorithmique
Keywords
Grands Graphes, systèmes complexes, réseaux sociaux, graph du web, diffusion de l’information dans les grands graphes.
Content
Reseaux Complexes:
1) Lois de d’échelle
2) Rappel de théorie des graphes
3) Graphes aléatoires
4) Propriétés statistiques remarquables des grands graphes de terrain (graphe du web)
a) Effet petit monde
b) Lois d’échelle dans les grands graphes
c) Modélisation des grands graphes
d) Structure de l’internet
5) Détections de communautés dans les graphs graphes de terrain
a) Application aux réseaux sociaux en ligne
6) Navigation dans les graphes (Algorithme du PageRank)
7) Robustesse des grands systèmes
a) Panne en cascade
b) Robustesse de l’Internet
8) Mécanismes de diffusion de l’information dans les graphes (modélisation épidémie, Marketing virale dans les réseaux sociaux)
Assessment formula
● Devoir = D1
● Note finale = D1
References
1. Easley, D., Kleinberg, J. Networks, crowds, and markets: Reasoning about a highly connected world, Cambridge University Press (2010).
2. Newman, M. Networks: an introduction, Oxford University Press (2010).
3. Hiroki Sayama, Introduction to the Modeling and Analysis of Complex Systems (2015)