Komplexe Netzwerke - Komplexe Systeme

Netzwerke sind vielfältig und universell einsetzbare Abstraktionen realer (komplexer) Systeme. Als "komplex" versteht man dabei Systeme aus vielen oft sehr einfach gebauten Teilchen oder Agenten.  Aus deren spezifischem Zusammenspiel entspringt ein für das System charakteristisches emergentes Verhalten. Das klassische Beispiel ist sicherlich unser Gehirn. Aufgebaut aus Milliarden relativ einfacher und gut verstandener Synapsen bringt es durch deren Verschaltung die unglaublichsten, allerdings weitgehend unverstandenen, Leistungen wie Lernen, Vergessen, Fühlen und Bewußtsein hervor. Die chemischen Reaktionen vieler Enyzme, Promotoren, Regulationsfaktoren etc. in lebenden Organismen sind auf er Ebene einzelner Reaktionen ebenfalls gut erklärt. Wie aus dem Zusammenspiel sehr vieler dieser Elemente Leben entsteht bleibt jedoch nach wie vor ein Rätsel. Genauso sind die Handlungen einzelner Agenten in Märkten oder Gesellschaften relativ gut bekannt. Wie aus deren Wechselwirkungen Aufschwung oder Rezession, Spekulationsblasen oder Börsenralleys werden, ist allerdings weitgehend unverstanden.

Offenbar spielt die Verknüpfung der einzelnen Elemente eine entscheidenden Rolle für das Verhalten des Gesamtsystems. Weniger entscheidend scheinen die individuellen Eigenschaften der Einzelelemente. Deshalb ist es sinnvoll, zunächst nur die Eigenschaften der als Netzwerke abstrahierten Systeme zu untersuchen. Anhand von realen Daten werden also die topologischen Strukturen der Wechselwirkung in den als Netzwerken oder Graphen abstrahierten komplexen Systemen untersucht.

Eine besondere Herausforderung ist es, zwischen Strukturen die als Ergebnis von zufälligen Fluktuationen entstehen und echten "funktionellen" Strukturen, also solchen, die tatsächlich das Verhalten des Gesamtsystems beeinflussen, zu unterscheiden. Hierbei leisten die Methoden der Statistischen Mechanik einen entscheidenden Beitrag.

Community Detection

Principle Problem of Community Detection

Eine oft beobachtete Eigenschaft vieler Netzwerke ist ihre modulare Struktur. Bestimmte Gruppen von Knoten sind untereinander dichter Verbunden sind als mit dem Rest des Netzwerkes. In Anlehnung an Soziale Netzwerke nennt man solche Cluster auch “Communities”. Diese zu finden stellt ein schwieriges Problem der kombinatorische Optimierung dar. Der “Suchraum”, also die Menge der möglichen Einteilungen in Gruppen, ist die Menge aller Teilmengen der Knoten und wächst damit schneller als exponentiell mit der Anzahl der Knoten. Zum Glück hilft eine Analogie zu aus der Festkörperphysik bekannten Magnetischen Systemen, sogenannten Spingläsern. Betrachtet man die Verbindungen im Netzwerk als Kopplungen von Spins und sucht den Grundzustand, also den mit kleinster Energie, so richten sich jene Spins auf dicht verbundenen Knoten in die gleiche Richtung aus, während Spins auf untereinander locker verbundenen Knoten in unterschiedliche Richtungen zeigen. Damit lassen sich Netzwerke mit hundert Tausenden von Knoten untersuchen, z.B. um die stabilen Konfigurationen eines Proteins zu finden, Gruppen von miteinander konkurrierenden Konsumenten auf eBay aufzuspüren oder das Netzwerk der Koautoren wissenschaftlicher Publikationen zu untersuchen.  

Mehr Informationen finden Sie in diesen Fachartikeln:

oder in diesen populärwissenschaftlichen Artikeln:

Graph Partitioning and Graph Clustering

Graph Partitioning und Graph Clustering

Ein Problem aller Methoden die in Daten,seien dies nun Netzwerke oder nicht, nach Strukturen suchen, ist folgendens: Auch wenn die Daten völlig zufällig sind wird ein Algorithmus in der Lage sein, etwas zu finden, das aussieht wie eine echte Struktur. Der Grund dafür liegt in dem riesigen Suchraum der oft zur Verfügung steht. Klassische Tests zu Signifikanzanalye wie z.B. ein Chi-Quadrat-Test sind jedoch nicht anwendbar, da diese eine Aussage darüber liefern, mit welcher Wahrscheinlichkeit z.B. eine gegebene Verteilung in Gruppen das Ergebnis einer rein zufälligen Einteilung ist. Über speziell auf eine Qualitätsfunktion oder Teststatistik optimierte Einteilungen kann man deshalb keine Aussage treffen. Im Fall der oben beschriebenen modularen Strukturen oder Communities wird ein Algorithmus immer in der Lage sein Gruppen von Knoten zu finden, die untereinander dicht und mit dem Rest des Netzes nur locker verbunden sind.

Zum Glück erlaubt die Statistische Mechanik Aussagen darüber, was man findet wenn man in rein zufälligen Daten sucht. Community Detection ist dabei eng verwandt mit dem klassischen und in der Statistischen Mechanik oft behandelten Problem der Graph-Partitionierung. Für beide lassen sich Erwartungswerte angeben, d.h. bei gegebenem rein zufälligem Netzwerk Antworten auf Fragen wie: Wie viele Kanten muss man mindestens schneiden, damit das Netzwerk in gleichgroße nicht verbundene Teile zerfällt? Wie viele Cluster finde ich in einem rein zufälligen Netzwerk und wie gut sind diese voneinander getrennt?

Damit versetzt uns die Statistische Mechanik in die Lage zu entscheiden, ob eine gefundene Einteilung in Gruppen allein das Ergebnis des Suchprozesses ist, oder eine tatsächlich vorhandene Gruppenstruktur repräsentiert. Sie erlaubt so Aussagen über die statistische Signifikanz der Ergebnisse.

Weitere Informationen finden Sie in diesen Fachartikeln: