Voir la notice de l'article provenant de la source Numdam
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 -é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.
Generating random graphs which verify a set of predefined properties is a major issue for the analysis of interaction networks. However, there is no general method available for practical cases, where the set of desired properties is complex. We propose a generation method which theoretically allows to obtain a uniform sample of any set of graphs, as long as we have an element of this set and the degree distribution is one of the required properties. This method, called -edge switching, is a generalization of Monte-Carlo Markov Chain methods of the literature which rely on iterating exchanges of edges ends. We describe its conception and implementation, as well as the technical difficulties encountered and how to overcome them. This method is applied on scientific collaboration networks, and we show that we can point out a small set of properties which can explain typical characteristics of the network.
@article{JSFS_2017__158_2_118_0,
author = {Tabourier, Lionel and Cointet, Jean-Philippe and Roth, Camille},
title = {G\'en\'eration de graphes al\'eatoires par \'echanges multiples d{\textquoteright}ar\^etes},
journal = {Journal de la soci\'et\'e fran\c{c}aise de statistique},
pages = {118--134},
publisher = {Soci\'et\'e fran\c{c}aise de statistique},
volume = {158},
number = {2},
year = {2017},
zbl = {1370.05193},
language = {fr},
url = {http://geodesic.mathdoc.fr/item/JSFS_2017__158_2_118_0/}
}
TY - JOUR AU - Tabourier, Lionel AU - Cointet, Jean-Philippe AU - Roth, Camille TI - Génération de graphes aléatoires par échanges multiples d’arêtes JO - Journal de la société française de statistique PY - 2017 SP - 118 EP - 134 VL - 158 IS - 2 PB - Société française de statistique UR - http://geodesic.mathdoc.fr/item/JSFS_2017__158_2_118_0/ LA - fr ID - JSFS_2017__158_2_118_0 ER -
%0 Journal Article %A Tabourier, Lionel %A Cointet, Jean-Philippe %A Roth, Camille %T Génération de graphes aléatoires par échanges multiples d’arêtes %J Journal de la société française de statistique %D 2017 %P 118-134 %V 158 %N 2 %I Société française de statistique %U http://geodesic.mathdoc.fr/item/JSFS_2017__158_2_118_0/ %G fr %F JSFS_2017__158_2_118_0
Tabourier, Lionel; Cointet, Jean-Philippe; Roth, Camille. Génération de graphes aléatoires par échanges multiples d’arêtes. Journal de la société française de statistique, Special issue : Humanities and Statistics, Tome 158 (2017) no. 2, pp. 118-134. http://geodesic.mathdoc.fr/item/JSFS_2017__158_2_118_0/