Modèle de bloc stochastique - Stochastic block model

Le modèle de bloc stochastique 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 le fait d'être connectés les uns aux autres avec des densités de bords particulières. Par exemple, les contours peuvent être plus fréquents au sein des communautés qu'entre les communautés. Sa formulation mathématique a été introduite pour la première fois en 1983 dans le domaine des réseaux sociaux par Holland et al. Le modèle de bloc stochastique est important dans les statistiques , l'apprentissage automatique et la science des réseaux , où il sert de référence utile pour la tâche de récupération de la structure de la communauté dans les données graphiques.

Définition

Le modèle de bloc stochastique prend les paramètres suivants :

• Le nombre de sommets ;${\style d'affichage n}$
• une partition de l'ensemble de sommets en sous - ensembles disjoints , appelés communautés ;${\displaystyle \{1,\ldots ,n\}}$${\displaystyle C_{1},\ldots ,C_{r}}$
• une matrice symétrique de probabilités d'arêtes.${\style d'affichage r\fois r}$${\style d'affichage P}$

L'ensemble d'arêtes est ensuite échantillonné au hasard comme suit : deux sommets quelconques et sont connectés par une arête avec une probabilité . Un exemple de problème est le suivant : étant donné un graphe avec des sommets, où les arêtes sont échantillonnées comme décrit, récupérez les groupes . ${\displaystyle u\in C_{i}}$${\displaystyle v\in C_{j}}$${\style d'affichage P_{ij}}$${\style d'affichage n}$${\displaystyle C_{1},\ldots ,C_{r}}$

Cas spéciaux

Si la matrice de probabilité est une constante, au sens où pour tout , alors le résultat est le modèle d'Erdős–Rényi . Ce cas est dégénéré – la partition en communautés devient sans objet – mais il illustre une parenté étroite avec le modèle Erdős-Rényi. ${\style d'affichage P_{ij}=p}$${\style d'affichage i,j}$ ${\style d'affichage G(n,p)}$

Le modèle de partition plantée est le cas particulier où les valeurs de la matrice de probabilité sont une constante sur la diagonale et une autre constante en dehors de la diagonale. Ainsi , deux sommets au sein de la même communauté partagent une arête avec probabilité , tandis que deux sommets de communautés différentes partagent une arête avec probabilité . Parfois, c'est ce modèle restreint qui est appelé modèle de bloc stochastique. Le cas où l' on appelle un assortatif modèle, alors que l'affaire est appelée disassortative . ${\style d'affichage P}$${\style d'affichage p}$${\style d'affichage q}$${\style d'affichage p}$${\style d'affichage q}$${\style d'affichage p>q}$${\style d'affichage p<q}$

Pour en revenir au modèle de bloc stochastique général, un modèle est appelé fortement assortatif si à chaque fois : toutes les entrées diagonales dominent toutes les entrées hors diagonale. Un modèle est appelé faiblement assortatif si à chaque fois : chaque entrée diagonale n'est requise que pour dominer le reste de sa propre ligne et colonne. Des formes disassorties de cette terminologie existent, en inversant toutes les inégalités. La récupération algorithmique est souvent plus facile contre des modèles de blocs avec des conditions assortatives ou disassorties de cette forme. ${\style d'affichage P_{ii}>P_{jk}}$${\style d'affichage j\neq k}$${\style d'affichage P_{ii}>P_{ij}}$${\style d'affichage i\neq j}$

Tâches statistiques typiques

Une grande partie de la littérature sur la détection de communauté algorithmique aborde trois tâches statistiques : la détection, la récupération partielle et la récupération exacte.

Détection

Le but des algorithmes de détection est simplement de déterminer, à partir d'un graphe échantillonné, si le graphe a une structure de communauté latente. Plus précisément, un graphe peut être généré, avec une certaine probabilité a priori connue, à partir d'un modèle de bloc stochastique connu, et sinon à partir d'un modèle Erdos-Renyi similaire . La tâche algorithmique consiste à identifier correctement lequel de ces deux modèles sous-jacents a généré le graphe.

Récupération partielle

Dans la récupération partielle, l'objectif est de déterminer approximativement la partition latente en communautés, dans le sens de trouver une partition qui est corrélée à la vraie partition de manière significativement meilleure qu'une supposition aléatoire.

Récupération exacte

Dans la récupération exacte, l'objectif est de récupérer exactement la partition latente en communautés. La taille des communautés et la matrice de probabilité peuvent être connues ou inconnues.

Limites inférieures statistiques et comportement de seuil

Les modèles de blocs stochastiques présentent un effet de seuil marqué rappelant les seuils de percolation . Supposons que nous permettions à la taille du graphique d'augmenter, en gardant les tailles de communauté dans des proportions fixes. Si la matrice de probabilité reste fixe, des tâches telles que la récupération partielle et exacte deviennent réalisables pour tous les réglages de paramètres non dégénérés. Cependant, si l'on réduit la matrice de probabilité à un rythme convenable au fur et à mesure qu'augmente, on observe une transition de phase brutale : pour certains réglages des paramètres, il deviendra possible d'obtenir une récupération avec une probabilité tendant à 1, alors qu'à l'opposé de la seuil du paramètre, la probabilité de récupération tend vers 0 quel que soit l'algorithme utilisé. ${\style d'affichage n}$${\style d'affichage n}$

Pour la récupération partielle, la mise à l'échelle appropriée est de prendre pour fixed , ce qui donne des graphiques de degré moyen constant. Dans le cas de deux communautés de taille égale, dans le modèle de partition plantée associative avec matrice de probabilité ${\displaystyle P_{ij}={\tilde {P}}_{ij}/n}$${\displaystyle {\tilde {P}}}$

la récupération partielle est réalisable avec probabilité à chaque fois , alors que tout estimateur échoue à la récupération partielle avec probabilité à chaque fois . ${\style d'affichage 1-o(1)}$${\displaystyle ({\tilde {p}}-{\tilde {q}})^{2}>2({\tilde {p}}+{\tilde {q}})}$${\style d'affichage 1-o(1)}$${\displaystyle ({\tilde {p}}-{\tilde {q}})^{2}<2({\tilde {p}}+{\tilde {q}})}$

Pour une récupération exacte, la mise à l'échelle appropriée est de prendre , ce qui donne des graphiques de degré moyen logarithmique. Ici, un seuil similaire existe : pour le modèle de partition plantée assortative avec des communautés de taille égale, le seuil se situe à . En fait, le seuil de récupération exact est connu pour le modèle de bloc stochastique entièrement général. ${\displaystyle P_{ij}={\tilde {P}}_{ij}\log n/n}$${\style d'affichage r}$${\displaystyle {\sqrt {\tilde {p}}}-{\sqrt {\tilde {q}}}={\sqrt {r}}}$

Algorithmes

En principe, la récupération exacte peut être résolue dans sa plage de faisabilité en utilisant le maximum de vraisemblance , mais cela revient à résoudre un problème de coupe contraint ou régularisé tel que la bissection minimale qui est typiquement NP-complet . Par conséquent, aucun algorithme efficace connu ne calculera correctement l'estimation du maximum de vraisemblance dans le pire des cas.

Cependant, une grande variété d'algorithmes fonctionnent bien dans le cas moyen, et de nombreuses garanties de performances à haute probabilité ont été prouvées pour les algorithmes dans les paramètres de récupération partielle et exacte. Les algorithmes réussis incluent le regroupement spectral des sommets, la programmation semi -

définie , les formes de propagation de croyances et la détection de communauté, entre autres.

Variantes

Plusieurs variantes du modèle existent. Un ajustement mineur alloue les sommets aux communautés de manière aléatoire, selon une distribution catégorielle , plutôt que dans une partition fixe. Des variantes plus importantes incluent le modèle de bloc stochastique à degré corrigé, le modèle de bloc stochastique hiérarchique, le modèle de bloc géométrique, le modèle de bloc censuré et le modèle de bloc à membres mixtes.

Modèles thématiques

Le modèle de bloc stochastique a été reconnu comme un modèle de sujet sur les réseaux bipartites. Dans un réseau de documents et de mots, le modèle de bloc stochastique permet d'identifier des sujets : groupe de mots ayant un sens similaire.

Voir également

• modélisation de blocs
• Algorithme de Girvan-Newman  – Algorithme de détection communautaire
• Benchmark Lancichinetti–Fortunato–Radicchi  – Algorithme de génération de réseaux de référence avec les communautés

Les références