Analyse de grands graphes aléatoires

Emilie Coupechoux, soutenance de thèse
lundi 10 décembre 2012 à 10h30, salle du Conseil (4ème étage), antenne parisienne de l'INRIA, 23 avenue d'Italie, 75013 Paris
Abstract

Plusieurs types de réseaux du monde réel peuvent être représentés par des graphes dont les sommets représentent des individus (dans le cas des réseaux sociaux) ou des pages Web (dans le cas du World Wide Web), pour ne citer que ces exemples. Chaque arête du graphe correspond à une interaction entre sommets: dans les réseaux sociaux, une arête est présente entre deux sommets si les individus qu’ils représentent sont amis; dans le World Wide Web, les arêtes représentent les liens hypertextes entre les pages Web. Comme il s’agit de réseaux de très grande taille, leur topologie détaillée est généralement inconnue, et nous les modélisons par de grands graphes aléatoires ayant les mêmes propriétés statistiques locales que celles des réseaux observés. Un exemple de telle propriété est la présence de regroupements dans les réseaux réels: si deux individus ont un ami en commun, ils ont également tendance à être amis entre eux. Étudier des modèles de graphes aléatoires qui soient à la fois appropriés et faciles à aborder d’un point de vue mathématique représente un challenge, c’est pourquoi nous considérons plusieurs modèles de graphes aléatoires possédant ces propriétés.

La propagation d’épidémies dans les graphes aléatoires peut être utilisée pour modéliser plusieurs types de phénomènes présents dans les réseaux réels, comme la propagation de maladies, ou la diffusion d’une nouvelle technologie. Le modèle épidémique que nous considérons dépend du phénomène que nous voulons représenter :

• un individu peut contracter une maladie par un simple contact avec un de ses amis (ces contacts étant indépendants),

• mais une nouvelle technologie est susceptible d’être adoptée par un individu lorsque beaucoup de ses amis ont déjà la technologie en question.

Nous étudions essentiellement ces deux différents cas de figure. Dans chaque cas, nous cherchons à savoir si une faible proportion de la population initialement atteinte (ou ayant la technologie en question) peut propager l’épidémie à une grande partie de la population: si c’est le cas, on dit qu’une ’cascade’ est possible. La transition de phase de ce phénomène est étroitement liée à l’apparition d’une composante géante dans un graphe aléatoire (il y a une ’composante géante’ dans un graphe aléatoire si la taille de sa plus grande composante connexe augmente de façon linéaire avec la taille totale du graphe).

L’étude des graphes aléatoires permet notamment la prédiction de propriétés globales (savoir dans quel cas une cascade est possible ou non) pour des grands réseaux sur lesquels nous ne disposons que de données locales.

This entry was posted in Events