Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 22 Mai 2012

Épidémies sur des graphes aléatoires avec clustering

par Émilie Coupechoux (INRIA-ENS)

Motivés par l'analyse des réseaux sociaux, nous considérons un modèle de graphe aléatoire dont la distribution des degrés est fixée, et le clustering (probabilité pour que deux sommets soient connectés entre eux, sachant qu'ils ont un voisin commun) varie. Sur ce graphe aléatoire, nous étudions deux types d'épidémies: un processus de diffusion, dans lequel chaque voisin d'un sommet peut lui transmettre l'épidémie indépendamment (avec une probabilité donnée), et un processus de contagion, dont le modèle provient de la théorie des jeux. Alors que des résultats ont déjà été obtenus pour des graphes aléatoires sans clustering, le but ici est de souligner l'impact du clustering sur la propagation de l'épidémie (plus précisément, nous étudions le nombre de sommets infectés à la fin de la propagation, lorsque l'épidémie part initialement d'un seul individu). Alors que le clustering rend la propagation plus difficile pour le modèle de diffusion, son impact sur le modèle de contagion dépend du degré moyen du graphe: à faible degré, le clustering limite la propagation, alors que le contraire se produit à fort degré.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr