Skip to content
Retour aux résultats

Modèle de blocs stochastiques — Détection probabiliste de communautés dans les réseaux

Année
1983
Type
Probabilistic generative graph model

Ce texte est une traduction automatique et n’a pas encore été relu. Lire l’original en anglais

Taille de police

À quoi sert-elle ?

Le modèle de blocs stochastiques (SBM), introduit par Holland, Laskey et Leinhardt (1983), est un modèle génératif probabiliste pour les graphes qui attribue des nœuds à des blocs latents et estime paramétriquement les probabilités de connexion entre les blocs.

C'est l'approche fondamentale pour la détection de communautés, l'identification de structures cœur-périphérie et la découverte de structures hiérarchiques dans l'analyse de réseaux.

L’intuition derrière la méthode

Imaginez un réseau social où les gens se regroupent — collègues, famille, équipes sportives — et où les connexions au sein d'un groupe sont plus probables que les connexions entre les groupes. Le modèle de blocs stochastiques formalise cette intuition : il suppose qu'il existe une étiquette de groupe cachée pour chaque nœud, et que la probabilité d'une arête entre deux nœuds quelconques ne dépend que des groupes auxquels ces deux nœuds appartiennent. L'ajustement du modèle consiste à trouver les étiquettes cachées qui expliquent le mieux le motif d'arêtes observé. Le résultat est une partition du réseau en blocs, fondée sur des principes statistiques, sans nécessiter que les groupes soient des cliques denses — le modèle prend en compte les structures cœur-périphérie et même les motifs désassortatifs où les connexions inter-groupes dépassent les connexions intra-groupes.

Histoire

Le modèle de blocs stochastiques a été introduit par Holland, Laskey et Leinhardt dans leur article de 1983 dans Social Networks comme une généralisation probabiliste des travaux antérieurs de blocmodélisation en analyse de réseaux sociaux. Pendant deux décennies, il est resté principalement un outil théorique ; il a pris une importance pratique avec le développement d'algorithmes d'inférence évolutifs — EM variationnelle et MCMC — dans les années 2010. Le SBM corrigé en fonction du degré a été introduit par Karrer et Newman (2011) pour résoudre le problème de l'hétérogénéité des degrés. La revue de Lee et Wilkinson en 2019 dans Applied Network Science a consolidé la famille d'extensions, couvrant les modèles de partition plantée, le SBM à appartenances mixtes et les variantes hiérarchiques. Aujourd'hui, le SBM et ses descendants sont le cadre probabiliste de référence pour la détection de communautés et le clustering de graphes.

Quand l’utiliser

Utilisez le modèle de blocs stochastiques lorsque vous avez un réseau avec au moins 50 nœuds et que vous souhaitez découvrir une structure de groupe latente sans supposer que les groupes doivent être des cliques denses. Il convient aux graphes dirigés ou non dirigés, pondérés ou non pondérés, et convient aussi bien aux tâches exploratoires qu'aux tâches de classification. La variante DCSBM est préférée lorsque les degrés des nœuds varient considérablement. Si le graphe a moins de 20 nœuds, la structure communautaire ne peut pas être estimée de manière fiable et des métriques descriptives plus simples doivent être utilisées à la place. Hypothèses : les appartenances aux blocs sont latentes et non observées ; la matrice de connexion des blocs est supposée homogène au sein de chaque paire de blocs ; et K doit être sélectionné par BIC ou facteur de Bayes plutôt que fixé arbitrairement.

Limites et points d’attention

  • Nécessite au moins environ 50 nœuds pour une estimation fiable des blocs ; les graphes très petits donnent des solutions instables.
  • L'inférence est coûteuse en calcul pour les grands graphes : EM variationnelle ou MCMC est nécessaire, et la convergence n'est pas garantie.
  • L'hypothèse d'homogénéité du SBM de base au sein des paires de blocs échoue lorsque les taux de connexion intra-bloc varient — le DCSBM atténue mais n'élimine pas ce problème.
  • La sélection de blocs via BIC ou facteur de Bayes peut toujours sous-segmenter ou sur-segmenter si le graphe a des communautés faiblement séparées.

Les conditions de la source ne remplacent ni une revue scientifique indépendante ni la validation par un moteur d’analyse.

Points forts

  • Cadre probabiliste fondé sur des principes qui permet la sélection de modèles via BIC ou facteur de Bayes, évitant les choix de paramètres arbitraires.
  • Prend en charge un large éventail de structures — communautés, cœur-périphérie, bipartite et hiérarchique — au-delà de l'hypothèse de clique dense des méthodes algorithmiques.
  • La variante corrigée en fonction du degré gère les graphes avec des distributions de degrés hétérogènes et des hubs sans distordre les affectations de blocs.
  • Fournit des probabilités d'appartenance a posteriori, permettant des affectations de nœuds souples ou incertaines plutôt que des partitions rigides.

Applications

  • Détection de communautés de recherche dans les réseaux de citations et de collaborations dans les sciences sociales et naturelles.
  • Identification de modules fonctionnels dans les réseaux biologiques tels que les interactions protéine-protéine et les graphes de co-expression génique.
  • Découverte de segments de clientèle ou d'anneaux de fraude dans les réseaux transactionnels et financiers.
  • Caractérisation de la structure cœur-périphérie dans les réseaux commerciaux inter-organisationnels ou inter-pays.
  • Évaluation comparative et validation d'autres algorithmes de détection de communautés à l'aide de graphes synthétiques générés par SBM comme vérité terrain.

Comment ça marche

Comment ça marche

1

L'analyste spécifie une plage candidate pour le nombre de blocs K et choisit une variante : le SBM de base suppose une distribution de degrés homogène au sein des blocs, tandis que le SBM corrigé en fonction du degré (DCSBM) ajoute des paramètres de degré au niveau du nœud pour gérer les hubs et les séquences de degrés hétérogènes. Le choix de la variante est guidé par la distribution des degrés du graphe observé.

2

Étant donné la matrice d'adjacence, le modèle estime les appartenances aux blocs et une matrice K×K de probabilités de connexion à l'aide d'un algorithme d'inférence. Pour les graphes de petite à moyenne taille, une maximisation exacte est réalisable ; pour les grands graphes, l'espérance-maximisation variationnelle (EM variationnelle) ou l'échantillonnage par chaîne de Markov (MCMC) est utilisé pour rendre l'inférence traitable.

3

Le nombre de blocs K n'est pas connu à l'avance et doit être choisi à partir des données. Les critères de sélection préférés sont le critère d'information bayésien (BIC) et le facteur de Bayes, qui pénalisent tous deux la complexité du modèle et sélectionnent le K qui équilibre le mieux l'ajustement et la parcimonie. Le principe de la longueur minimale de description (MDL) sous-tend l'implémentation de graph-tool.

4

Une fois le K optimal et les affectations de blocs déterminés, la matrice de connexion des blocs est inspectée pour caractériser la structure : les blocs assortatifs correspondent à des communautés, les blocs désassortatifs à des motifs de type biparti, et les profils mixtes à des arrangements cœur-périphérie. Les appartenances des nœuds sont rapportées avec des probabilités a posteriori lorsque l'algorithme d'inférence les fournit.

Pièges courants

  • Fixer K arbitrairement plutôt que de le sélectionner par BIC ou facteur de Bayes produit des partitions peu fiables — utilisez toujours un critère de sélection de modèle fondé sur des principes.
  • Appliquer le SBM de base à un graphe avec une séquence de degrés hétérogène (hubs, distribution de degrés de loi de puissance) gonfle les estimations du nombre de blocs ; utilisez plutôt le DCSBM.
  • Traiter l'appartenance à un bloc comme certaine lorsque la probabilité a posteriori est diffuse surestime la confiance — rapportez l'incertitude lorsqu'elle est disponible.
  • Confondre la sortie du SBM avec des communautés réelles : le modèle trouve une structure latente statistiquement plausible, pas nécessairement des groupes socialement significatifs. Validez par rapport aux connaissances du domaine.
  • Exécuter le SBM sur moins de 20 nœuds donne des solutions dégénérées — revenez aux métriques descriptives du réseau ou à une détection de communauté simple pour les petits graphes.

Questions fréquentes

En quoi le modèle de blocs stochastiques diffère-t-il de la détection de communautés basée sur la modularité ?

La maximisation de la modularité (par exemple, Louvain, Leiden) optimise un objectif heuristique qui suppose implicitement des communautés assortatives de taille à peu près égale et a une limite de résolution connue qui empêche la détection de petites communautés. Le SBM est un modèle génératif probabiliste avec des hypothèses explicites ; le nombre de blocs est choisi par sélection de modèle (BIC ou facteur de Bayes) plutôt que par optimisation heuristique, et il peut détecter des structures désassortatives et cœur-périphérie que les méthodes basées sur la modularité manquent.

Quand dois-je utiliser le DCSBM au lieu du SBM de base ?

Utilisez le DCSBM lorsque la distribution des degrés des nœuds est hétérogène — par exemple, lorsqu'un petit nombre de hubs représente une grande fraction des arêtes, ou lorsque la séquence de degrés suit une loi de puissance approximative. Le SBM de base traite tous les nœuds d'un bloc comme échangeables, ce qui amène les hubs à être regroupés dans leurs propres blocs fallacieux. Le DCSBM ajoute un terme de correction de degré qui sépare la position structurelle du degré, produisant des affectations de blocs plus interprétables dans de tels graphes.

Comment choisir le nombre de blocs K ?

Ajustez des modèles pour une plage de valeurs K et sélectionnez celui qui minimise le BIC ou maximise le facteur de Bayes (ou minimise de manière équivalente la longueur de description). Ne choisissez pas K en fonction de l'inspection visuelle du graphe ou des attentes a priori. La plupart des implémentations (graph-tool, blockmodels dans R) automatisent cette recherche. Une analyse de sensibilité — vérifiant si la structure qualitative des blocs change lorsque K est varié de un — est également recommandée.

Quelle est la taille minimale du réseau pour que le SBM soit fiable ?

Le registre spécifie un minimum de 50 nœuds pour une inférence fiable. Avec moins de 20 nœuds, le modèle ne peut pas identifier de structure communautaire significative et s'ajustera au bruit — utilisez des statistiques descriptives du réseau ou une détection de communauté simple à la place. Entre 20 et 50 nœuds, les résultats doivent être considérés comme exploratoires et interprétés avec prudence.

Méthodes associées

Sources

  1. Holland, P.W., Laskey, K.B. & Leinhardt, S. (1983). Stochastic Blockmodels: First Steps. Social Networks, 5(2), 109-137.

    Ouvrir la référence DOI
    Copié.
  2. Lee, C. & Wilkinson, D.J. (2019). A Review of Stochastic Block Models and Extensions for Graph Clustering. Applied Network Science, 4(1), 122.

    Ouvrir la référence DOI
    Copié.