Génération de graphes aléatoires par échanges multiples d’arêtes

La generation de graphes aleatoires verifiant un ensemble de proprietes fixe est un probleme majeur pour l’etude des reseaux d’interaction. Pourtant, il n’existe pas de solution generale qui soit satisfaisante dans les cas pratiques, ou l’ensemble de proprietes a satisfaire est complexe. Nous proposons une methode de generation permettant theoriquement d’obtenir un echantillon parfaitement aleatoire de n’importe quel ensemble de graphes, a condition que la distribution des degres soit fixee et que l’on dispose d’un element de cet ensemble. Cette methode dite de k-echanges, generalise les procedures de Monte-Carlo par chaine de Markov de la litterature, selon lesquelles on echange iterativement les extremites d’aretes du graphe. Nous decrivons sa realisation, les difficultes techniques a resoudre et comment il est possible de les surmonter. Nous appliquons cette methode sur des reseaux de collaborations scientifiques, et montrons que l’on peut identifier un petit nombre de proprietes suffisantes pour expliquer des caracteristiques typiques du reseau.