Accéder directement au contenu Accéder directement à la navigation
Article dans une revue

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

Résumé : La génération de graphes aléatoires vérifiant un ensemble de propriétés fixé est un problème majeur pour l’étude des réseaux d’interaction. Pourtant, il n’existe pas de solution générale qui soit satisfaisante dans les cas pratiques, où l’ensemble de propriétés à satisfaire est complexe. Nous proposons une méthode de génération permettant théoriquement d’obtenir un échantillon parfaitement aléatoire de n’importe quel ensemble de graphes, à condition que la distribution des degrés soit fixée et que l’on dispose d’un élément de cet ensemble. Cette méthode dite de k-échanges, généralise les procédures de Monte-Carlo par chaîne de Markov de la littérature, selon lesquelles on échange itérativement les extrêmités d’arêtes du graphe. Nous décrivons sa réalisation, les difficultés techniques à résoudre et comment il est possible de les surmonter. Nous appliquons cette méthode sur des réseaux de collaborations scientifiques, et montrons que l’on peut identifier un petit nombre de propriétés suffisantes pour expliquer des caractéristiques typiques du réseau.
Liste complète des métadonnées

https://hal-sciencespo.archives-ouvertes.fr/hal-02006124
Contributeur : Spire Sciences Po Institutional Repository <>
Soumis le : lundi 4 février 2019 - 14:07:55
Dernière modification le : dimanche 4 juillet 2021 - 03:25:18

Identifiants

Collections

Citation

Lionel Tabourier, Jean-Philippe Cointet, Camille Roth. Génération de graphes aléatoires par échanges multiples d’arêtes. Journal de la Société Française de Statistique, Société Française de Statistique et Société Mathématique de France, 2017, 158 (2), pp.118 - 134. ⟨hal-02006124⟩

Partager

Métriques

Consultations de la notice

15