Analyse de grands graphes aléatoires

Emilie Coupechoux

lundi 10 décembre 2012 à 10h30, salle du Conseil (4ème étage), antenne parisienne de l’INRIA, 23 avenue d’Italie, 75013 Paris

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 quils représentent sont amis; dans le World Wide Web, les arêtes représentent les liens hypertextes entre les pages Web. Comme il sagit 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 dun point de vue mathématique représente un challenge, cest 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 dune 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 cest le cas, on dit quune cascade est possible. La transition de phase de ce phénomène est étroitement liée à lapparition dune 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.