Utilisateur:Aziz Kha/Modèle de blocs stochastiques

 

Le modèle de blocs stochastiques, ou stochastic block model en anglais, souvent abrégé en SBM est un modèle génératif pour les graphes aléatoires. Ce modèle tend à produire des graphes contenant des communautés, des sous-ensembles de nœuds caractérisés par leur connexion les uns aux autres avec des densités d'arêtes particulières. Sa formulation mathématique a été introduite pour la première fois en 1983 dans le domaine des réseaux sociaux par Paul W. Holland et al. Le modèle de blocs stochastiques est utilisé dans les statistiques, le machine learning et la science des réseaux, où il sert de référence utile pour déterminer des groupes dans des graphes.

Définition

Le modèle de blocs stochastiques prend les paramètres suivants :

• $n$, le nombre de sommets ;
• un ensemble de sommets $\{1,\ldots ,n\}$ en sous-ensembles disjoints $C_{1},\ldots ,C_{r}$, appelées communautés ;
• une matrice symétrique $P$ d'ordre $r$ de probabiltés de connexion des nœuds.

L'ensemble d'arêtes est ensuite échantillonné au hasard comme suit : deux sommets quelconques $u\in C_{i}$ et $v\in C_{j}$ sont reliés par une arête avec une probabilité $P_{ij}$.

Cas particuliers

Un exemple du cas assorti pour le modèle de bloc stochastique.

Si la matrice de probabilité est une constante, où $P_{ij}=p$ pour tous $i,j$, alors on obtient un modèle Erdős–Rényi $G(n,p)$.

[[Catégorie:Réseau de télécommunications]] [[Catégorie:Graphe aléatoire]] [[Catégorie:Apprentissage automatique]]