Accueil

 

Analyse des réseaux (Complex Networks)

Informations pratiques


Discipline :

Informatique

Niveau :

Master 2

Semestre :

S3

Crédits ECTS :

4

Volume Horaire :

22h Cours

6h de TD

Responsable :

Marton Karsai

Ecole Normale Supérieure de Lyon

UMR 5668 Laboratoire de l'informatique du parallélisme

Intervenants :

Eric Fleury

Marton Karsai

 

La Formation

Dans de nombreux contextes, les grands graphes jouent un rôle essentiel; citons par exemple la topologie d'Internet, les graphes du Web ou les échanges Pair-à-Pair, mais aussi les réseaux sociaux, réseaux de contact, biologiques ou linguistiques. La disponibilité de données massives, de capacités de traitement adéquates, et l'observation de diverses propriétés en commun ont récemment donné naissance à un vaste effort de recherche sur ces objets. Son originalité réside dans le fait qu'on part de graphes issus d'observations, et non définis formellement. C'est en ce sens qu'on les qualifie de "graphes de terrain".

Ce cours abordera les différentes problématiques soulevées par ce domaine que l'on peut regrouper en quatre familles complémentaires:

- Mesure et métrologie: mener des mesure fiables, de qualité et à grande échelle est une problématique de recherche en soi, qu'il ne faut pas ignorer. Savoir ce que l'on mesure, comment et pourquoi est l'un des points de départ crucial de l'analyse des grands graphes de terrain.

- Analyse: on abordera les outils et le formalisme pour décrire les grands graphes de terrain afin d'en extraire les principales propriétés.

- Modélisation: une fois les principales propriétés des graphes de terrain identifiées, les capturer dans un modèle formel est crucial, notamment pour les expliquer, obtenir des résultats formels, et mener des simulations.

- Algorithmique: la taille des graphes considérés interdit l'utilisation d'algorithmes quadratiques ou plus; de nombreux problèmes pour lesquels des solutions habituellement satisfaisantes sont connues doivent donc être retravaillés. Par ailleurs, la présence de propriétés caractéristiques des graphes de terrain ouvre la voie au développement d'algorithmes efficaces dans ces cas.

Plus d'information :  http://perso.ens-lyon.fr/marton.karsai/Marton_Karsai/complexnet.html


Pré-requis

 

 

Introduction to Computer Science.

 

Background in graph theory, statistical analysis, and computer algorithms is an advantage but is not mandatory, as the course intends to be accessible for students coming from any scientific discipline.

Modalité de l'examen

Ecrit.

Mots-clés

-