Le cours traite des propriétés structurelles des grands réseaux rencontrés en pratique:

• Réseaux numériques : P2P, graphe du Web
• Réseaux physiques : routier, électrique, Internet
• Réseaux sociaux, graphes de co-citation, de co-tournage de film
• Réseaux issus de la biologie
• …

Il s'agit de comprendre quelles propriétés sont inattendues (par-rapport à l'aléatoire), comment elles apparaissent, comment calculer les paramètres de graphes correspondant, et l'intérêt pratique que l'on peut en tirer.

Le cours traitera de ces propriétés particulières :

• lois des degrés particulières
• distances courtes entre deux sommets
• forte densité des voisinages
• communautés, coeur plus connecté
• centralités et mesure de l'importance d'un sommet

Il présentera des modèles pour comparer à l'aléatoire et comprendre comment une propriété globale émerge de lois locales :

• graphes aléatoires d'Erdös-Rényi.
• grille de Kleinberg et modèles navigables
• anneaux de Watts et Strogatz et modèles petit-mondes
• attachement préférentiel et émergence de loi de puissnce

On présentera des algorithmes tels que le calcul de communautés ou le coefficient de clustering.

On parlera aussi de P2P (peer to peer) structuré ou non et de DHT (Distributed HasTable).

Bases de théorie des graphes; algorithmes de graphes de base : parcours, Diskstra, arbres couvrants. Avoir déjà entendu parler de probabilités et statistiques (on reviendra sur les lois normales, de puissance etc.) Programmation Java (langage des TPs)