Zum Inhalt springen
Zurück zu den Suchergebnissen

Stochastic Block Model — Probabilistische Erkennung von Gemeinschaften in Netzwerken

Jahr
1983
Typ
Probabilistic generative graph model

Dieser Text ist eine maschinelle Übersetzung und wurde noch nicht geprüft. Original auf Englisch lesen

Schriftgröße

Was leistet sie?

Das Stochastic Block Model (SBM), eingeführt von Holland, Laskey und Leinhardt (1983), ist ein probabilistisches generatives Modell für Graphen, das Knoten latenten Blöcken zuordnet und die Verbindungswahrscheinlichkeiten zwischen Blöcken parametrisch schätzt.

Es ist der grundlegende Ansatz für die Erkennung von Gemeinschaften, die Identifizierung von Kern-Peripherie-Strukturen und die Entdeckung hierarchischer Strukturen in der Netzwerkanalyse.

Die Intuition hinter der Methode

Stellen Sie sich ein soziales Netzwerk vor, in dem sich Menschen in Gruppen – Kollegen, Familie, Sportteams – zusammenfinden und Verbindungen innerhalb einer Gruppe wahrscheinlicher sind als Verbindungen zwischen Gruppen. Das Stochastic Block Model formalisiert diese Intuition: Es wird angenommen, dass jeder Knoten eine versteckte Gruppenbezeichnung hat und die Wahrscheinlichkeit einer Kante zwischen zwei beliebigen Knoten nur davon abhängt, zu welchen Gruppen diese beiden Knoten gehören. Das Anpassen des Modells bedeutet, die versteckten Bezeichnungen zu finden, die das beobachtete Kantenmuster am besten erklären. Das Ergebnis ist eine prinzipienfeste, statistisch fundierte Partition des Netzwerks in Blöcke, ohne dass die Gruppen dichte Cliquen sein müssen – das Modell berücksichtigt Kern-Peripherie-Strukturen und sogar disassortative Muster, bei denen Verbindungen zwischen Gruppen die innerhalb von Gruppen übersteigen.

Geschichte

Das Stochastic Block Model wurde von Holland, Laskey und Leinhardt in ihrer Arbeit in Social Networks von 1983 als probabilistische Verallgemeinerung früherer Blockmodellierungsarbeiten in der sozialen Netzwerkanalyse eingeführt. Zwei Jahrzehnte lang blieb es hauptsächlich ein theoretisches Werkzeug; es gewann mit der Entwicklung skalierbarer Inferenzalgorithmen – variational EM und MCMC – in den 2010er Jahren an praktischer Bedeutung. Das Degree-Corrected SBM wurde von Karrer und Newman (2011) eingeführt, um das Problem der Gradheterogenität zu lösen. Lee und Wilkinsons Überprüfung von 2019 in Applied Network Science konsolidierte die Familie der Erweiterungen, einschließlich Planted Partition Models, Mixed-Membership SBM und hierarchischer Varianten. Heute sind SBM und seine Nachfolger der Referenzrahmen für die probabilistische Gemeinschaftserkennung und Graphenclusterung.

Wann wird sie eingesetzt?

Verwenden Sie das Stochastic Block Model, wenn Sie ein Netzwerk mit mindestens 50 Knoten haben und eine latente Gruppenstruktur entdecken möchten, ohne anzunehmen, dass Gruppen dichte Cliquen sein müssen. Es eignet sich für gerichtete oder ungerichtete Graphen, gewichtet oder ungewichtete, und ist sowohl für explorative als auch für Klassifizierungsaufgaben geeignet. Die DCSBM-Variante wird bevorzugt, wenn die Knotengrade erheblich variieren. Wenn der Graph weniger als 20 Knoten hat, kann die Gemeinschaftsstruktur nicht zuverlässig geschätzt werden und es sollten einfachere deskriptive Metriken verwendet werden. Annahmen: Blockmitgliedschaften sind latent und nicht beobachtet; die Blockverbindungsmatrix wird als homogen innerhalb jedes Blockpaares angenommen; und K muss mittels BIC oder Bayes-Faktor gewählt werden und nicht willkürlich festgelegt werden.

Grenzen und Hinweise

  • Erfordert mindestens etwa 50 Knoten für eine zuverlässige Blockschätzung; sehr kleine Graphen ergeben instabile Lösungen.
  • Die Inferenz ist für große Graphen rechenintensiv: Es ist variational EM oder MCMC erforderlich, und die Konvergenz ist nicht garantiert.
  • Die Homogenitätsannahme des Basis-SBM innerhalb von Blockpaaren bricht zusammen, wenn die Raten von Verbindungen innerhalb von Blöcken variieren – das DCSBM mildert dies, beseitigt es aber nicht.
  • Die Blockauswahl mittels BIC oder Bayes-Faktor kann immer noch unter- oder übersegmentieren, wenn der Graph schwach getrennte Gemeinschaften aufweist.

Die Bedingungen der Quelle ersetzen weder eine unabhängige wissenschaftliche Prüfung noch die Validierung durch eine Analyse-Engine.

Stärken

  • Prinzipienfester probabilistischer Rahmen, der die Modellauswahl mittels BIC oder Bayes-Faktor ermöglicht und willkürliche Parameterwahlen vermeidet.
  • Ermöglicht eine breite Palette von Strukturmustern – Gemeinschaften, Kern-Peripherie, bipartite und hierarchische – über die dichte-Clique-Annahme algorithmischer Methoden hinaus.
  • Die Degree-Corrected Variante behandelt Graphen mit heterogenen Gradverteilungen und Hubs, ohne die Blockzuweisungen zu verzerren.
  • Liefert Posterior-Mitgliedschaftswahrscheinlichkeiten, die weiche oder unsichere Knotenzuweisungen anstelle von harten Partitionen ermöglichen.

Anwendungen

  • Erkennung von Forschungsgemeinschaften in Zitations- und Kollaborationsnetzwerken in den Sozial- und Naturwissenschaften.
  • Identifizierung von Funktionsmodulen in biologischen Netzwerken wie Protein-Protein-Interaktions- und Gen-Koexpressionsgraphen.
  • Entdeckung von Kundensegmenten oder Betrugsringen in Transaktions- und Finanznetzwerken.
  • Charakterisierung von Kern-Peripherie-Strukturen in interorganisatorischen oder internationalen Handelsnetzwerken.
  • Benchmarking und Bewertung anderer Algorithmen zur Gemeinschaftserkennung unter Verwendung von SBM-generierten synthetischen Graphen als Ground Truth.

So funktioniert es

So funktioniert es

1

Der Analyst gibt einen Kandidatenbereich für die Anzahl der Blöcke K an und wählt eine Variante: Das Basis-SBM nimmt eine homogene Gradverteilung innerhalb der Blöcke an, während das Degree-Corrected SBM (DCSBM) knotenspezifische Gradparameter hinzufügt, um Hubs und heterogene Gradsequenzen zu behandeln. Die Wahl der Variante wird durch die Gradverteilung des beobachteten Graphen informiert.

2

Gegeben die Adjazenzmatrix, schätzt das Modell Blockmitgliedschaften und eine K×K-Matrix von Verbindungswahrscheinlichkeiten mithilfe eines Inferenzalgorithmus. Für kleine bis mittelgroße Graphen ist eine exakte Maximierung machbar; für große Graphen werden varianzbasierte Erwartungsmaximierung (variational EM) oder Markov-Ketten-Monte-Carlo (MCMC)-Sampling verwendet, um die Inferenz handhabbar zu machen.

3

Die Anzahl der Blöcke K ist nicht im Voraus bekannt und muss aus den Daten gewählt werden. Die bevorzugten Auswahlkriterien sind der Bayesian Information Criterion (BIC) und der Bayes-Faktor, die beide die Modellkomplexität bestrafen und das K auswählen, das die Anpassung am besten mit der Parsimonie ausbalanciert. Das Minimum Description Length (MDL)-Prinzip liegt der Implementierung von graph-tool zugrunde.

4

Sobald das optimale K und die Blockzuweisungen bestimmt sind, wird die Blockverbindungsmatrix inspiziert, um die Struktur zu charakterisieren: assortative Blöcke entsprechen Gemeinschaften, disassortative Blöcke bipartite Mustern und gemischte Profile Kern-Peripherie-Anordnungen. Knotenzugehörigkeiten werden mit Posterior-Wahrscheinlichkeiten berichtet, wo immer der Inferenzalgorithmus sie liefert.

Häufige Fallstricke

  • Die willkürliche Festlegung von K anstelle der Auswahl mittels BIC oder Bayes-Faktor führt zu unzuverlässigen Partitionen – verwenden Sie immer ein prinzipienfestes Kriterium zur Modellauswahl.
  • Die Anwendung des Basis-SBM auf einen Graphen mit einer heterogenen Gradsequenz (Hubs, Potenzgesetz-Gradverteilung) bläht die Schätzungen der Blockanzahl auf; verwenden Sie stattdessen DCSBM.
  • Die Behandlung der Blockmitgliedschaft als sicher, wenn das Posterior diffus ist, übertreibt die Zuversicht – berichten Sie Unsicherheit, wenn verfügbar.
  • Verwechslung von SBM-Ergebnissen mit tatsächlichen Gemeinschaften: Das Modell findet statistisch plausible latente Strukturen, nicht unbedingt soziologisch bedeutsame Gruppen. Validieren Sie anhand von Domänenwissen.
  • Die Ausführung von SBM auf weniger als 20 Knoten ergibt degenerate Lösungen – greifen Sie stattdessen auf deskriptive Netzwerkstatistiken oder einfache Gemeinschaftserkennung für kleine Graphen zurück.

Häufig gestellte Fragen

Wie unterscheidet sich das Stochastic Block Model von modularitätsbasierten Gemeinschaftserkennungen?

Die Modulariätsmaximierung (z. B. Louvain, Leiden) optimiert ein heuristisches Ziel, das implizit assortative, annähernd gleich große Gemeinschaften annimmt und eine bekannte Auflösungsgrenze hat, die die Erkennung kleiner Gemeinschaften verhindert. Das SBM ist ein generatives probabilistisches Modell mit expliziten Annahmen; die Blockanzahl wird durch Modellauswahl (BIC oder Bayes-Faktor) anstelle von heuristischer Optimierung gewählt, und es kann disassortative und Kern-Peripherie-Strukturen erkennen, die von modularitätsbasierten Methoden übersehen werden.

Wann sollte ich DCSBM anstelle des Basis-SBM verwenden?

Verwenden Sie DCSBM, wenn die Knotengradverteilung heterogen ist – zum Beispiel, wenn eine kleine Anzahl von Hubs einen großen Teil der Kanten ausmacht oder wenn die Gradsequenz einer ungefähren Potenzgesetzverteilung folgt. Das Basis-SBM behandelt alle Knoten innerhalb eines Blocks als austauschbar, was dazu führt, dass Hubs in eigene, falsche Blöcke gezogen werden. DCSBM fügt einen Gradkorrekturterm hinzu, der die strukturelle Position vom Grad trennt und in solchen Graphen interpretierbarere Blockzuweisungen liefert.

Wie wähle ich die Anzahl der Blöcke K?

Passen Sie Modelle für eine Reihe von K-Werten an und wählen Sie dasjenige, das BIC minimiert oder den Bayes-Faktor maximiert (oder äquivalent die Beschreibungslänge minimiert). Wählen Sie K nicht basierend auf visueller Inspektion des Graphen oder Erwartungen. Die meisten Implementierungen (graph-tool, blockmodels in R) automatisieren diese Suche. Eine Sensitivitätsanalyse – die Prüfung, ob sich die qualitative Blockstruktur ändert, wenn K um eins variiert wird – wird ebenfalls empfohlen.

Was ist die minimale Netzwerkgröße für eine zuverlässige SBM-Schätzung?

Das Verzeichnis gibt eine Mindestanzahl von 50 Knoten für eine zuverlässige Inferenz an. Bei weniger als 20 Knoten kann das Modell keine aussagekräftige Gemeinschaftsstruktur identifizieren und passt Rauschen an – verwenden Sie stattdessen deskriptive Netzwerkstatistiken oder einfache Gemeinschaftserkennung. Zwischen 20 und 50 Knoten sollten die Ergebnisse als explorativ behandelt und mit Vorsicht interpretiert werden.

Verwandte Methoden

Quellen

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

    DOI-Referenz öffnen
    Kopiert.
  2. Lee, C. & Wilkinson, D.J. (2019). A Review of Stochastic Block Models and Extensions for Graph Clustering. Applied Network Science, 4(1), 122.

    DOI-Referenz öffnen
    Kopiert.