Komplexes Netzwerk
Ein komplexes Netzwerk ist im Rahmen der Netzwerkforschung bzw. Graphentheorie ein Netzwerk (Graph) mit nicht-trivialen topologischen Eigenschaften, d. h. mit Eigenschaften, die nicht in einfachen Netzwerken wie Gittern oder zufälligen Graphen auftreten. Die Untersuchung von Komplexen Netzwerken ist ein junges und aktives Gebiet in der aktuellen wissenschaftlichen Forschung, welches hauptsächlich durch die empirischen Untersuchungen von realen Netzwerken wie Rechnernetzen oder sozialen Netzwerken inspiriert ist.
Definition
Viele soziale, biologische und Rechnernetze weisen wesentliche nicht-triviale topologische Eigenschaften auf, das heißt die Verbindungen (Kanten) zwischen ihren Elementen (Knoten) sind weder rein regulär noch rein zufällig.[1][2][3][4] Stattdessen sind derartige Netzwerke durch spezielle Verteilungen im Auftreten ihrer Elemente gekennzeichnet (Gradverteilung, englisch: degree distribution), durch einen hohen Clusterkoeffizienten, eine bestimmte Gemeinschaftsstruktur (community structure) oder eine ausgeprägte hierarchische Struktur. Viele bisher studierte mathematische Modelle von Netzwerken bzw. Graphen weisen hingegen keine dieser Eigenschaften auf.
Zwei typische Klassen von komplexen Netzwerken wurden in der Vergangenheit intensiv studiert: Skalenfreie Netzwerke,[5] und die sogenannten small world Netzwerke[6] deren Entdeckung und Definition kanonische Fallstudien auf diesem Gebiet sind.
In skalenfreien Netzwerken haben die Knoten keine typische Anzahl von Verbindungen, sondern die Verteilung der Verbindungen pro Knoten folgt einem Potenzgesetz.
In small-world Netzwerken treten hingegen viele sehr kurze Verbindungen zwischen allen Elementen auf und sie haben einen hohen Clusterkoeffizienten. Durch die raschen Fortschritte in der aktuellen Forschung zu komplexen Netzwerken sind auch weitere wichtige neue Aspekte und Erkenntnisse gefunden worden, wie sich zeitliche ändernde Netzwerke: Diese Netzwerke können sich mit der Zeit verändern (sogenannte ‘evolving networks’[7][8]), wobei Knoten und Kanten mit der Zeit neu entstehen oder auch verschwinden können. Dadurch entsteht eine komplexe Dynamik, die zu Selbstorganisation und stabilen Zuständen führen kann. Ein weiterer wichtiger Aspekt ist hier das Auftreten von Synchronisation.[9]
Die Erforschung von komplexen Netzwerken ist ein lebhaftes und sehr aktuelles Forschungsgebiet und verbindet verschiedene Disziplinen wie Mathematik, Physik, Biologie, Klimaforschung, Informatik, Soziologie, Epidemiologie und viele weitere. Die Konzepte aus der Netzwerktheorie haben Eingang in die Analyse von metabolischen und regulatorischen Netzwerken, in das Design von robusten und skalierbaren Kommunikationsnetzwerken, in die Entwicklung von Impfstrategien oder in die Analyse von Klimaphänomenen gefunden. Entsprechende Forschungsresultate werden regelmäßig in einigen der bekanntesten wissenschaftlichen Zeitschriften veröffentlicht,[1][6][3][4][10] sind Thema auf speziellen Fachtagungen und haben auch zu einigen populärwissenschaftlichen Artikeln und Büchern[11][12][13] geführt.
Aus der Erforschung von komplexen Netzwerken können wichtige Aussagen zu Informations- und Stoffflüssen bzw. deren Optimierung sowie über kritisches Verhalten und Stabilität des Gesamtsystems gelernt werden. Als Beispiel sei auf den Austausch von Banknoten hingewiesen, welcher von Dirk Brockmann mit Hilfe der Theorie komplexer Netzwerke untersucht wurde, was weltweite Beachtung fand.[10][14]
Analysemethoden
Um ein Netzwerk resp. einen Graphen zu analysieren, ist in vielen Fällen die Wichtigkeit der Knoten von Interesse. Neben naiven Metriken wie Analyse des Knotengrades sind auch komplexere Methoden vorgeschlagen worden. Ein bekanntes Beispiel ist der PageRank, die Methode, die die Basis für moderne Suchmaschinen bildet. Sie ist eng verwandt mit der Eigenvektor-Zentralität.
Weitere Maße für Graphen sind:
- Grad (degree centrality) – Ein früh entwickeltes, einfaches Maß, um die Zentralität eines Knotens zu bemessen, ist die Untersuchung der Menge aller inzidenten Kanten.
- Nähe (closeness centrality) – Die Entfernung eines Knotens zu allen anderen ist die Basis für dieses Maß. Dadurch können Knoten (automatisch) identifiziert werden, welche sich im „Zentrum“ eines Netzwerks befinden. Normalerweise wird der reziproke Wert der Summe aller Distanzen zu anderen Knoten genommen, um zu erreichen, dass der Wert umso höher wird, je höher die wahrgenommene Zentralität des Knotens ist.
- Betweenness-Zentralität (betweenness centrality) – Ein Knoten hat einen hohen Betweenness-Wert, wenn dieser Knoten Bestandteil besonders vieler kürzester Wege ist und die jeweiligen Paare wenige andere kürzeste Wege haben, auf der der Knoten nicht enthalten ist. Für jedes Paar von Knoten wird daher der Anteil an kürzesten Wegen zwischen ihnen berechnet, die v enthalten. Diese Anteile werden für alle Paare von Knoten aufsummiert um die Betweennesszentralität von v zu berechnen.
- Eigenvektorzentralität (eigenvector centrality) – Nach der Methode der Eigenvektorzentralität ist ein Knoten umso wichtiger, je wichtiger seine Nachbarknoten sind.
Siehe auch
Literatur
- Füllsack, Manfred (Hrsg.): Networking Networks. Origins, Applications, Experiments. Proceedings of the multi-disciplinary network for the Simulation of Complex Systems - Research in the Von-Neumann-Galaxy. Turia + Kant: Wien/Berlin 2014, ISBN 978-3-85132-725-0.
Einzelnachweise
- S. H. Strogatz: Exploring Complex Networks. In: Nature. 410, 2001, S. 268–276.
- R. Albert, A.-L. Barabási: Statistical mechanics of complex networks. In: Reviews of Modern Physics. 74, 2002, S. 47.
- M. E. J. Newman: The structure and function of complex networks. In: SIAM Review. 45, 2003, S. 167–256.
- S. Boccaletti et al.: Complex Networks: Structure and Dynamics. In: Physics Reports. 424, 2006, S. 175–308.
- A.-L. Barabási, E. Bonabeau: Scale-Free Networks. In: Scientific American. Mai, 2003, S. 50–59.
- D. J. Watts, S. H. Strogatz: Collective dynamics of ‘small-world’ networks. In: Nature. 393, 1998, S. 440–442.
- S. N. Dorogovtsev, J.F.F. Mendes: Evolution of Networks. In: Advances in Physics. 51, 2002, S. 1079.
- R. Albert, A.-L. Barabási: Topology of evolving networks: local events and universality. In: Physical Review Letters. 85, 2000, S. 5234–5237.
- A. Arenas, A. Díaz-Guilera, J. Kurths, Y. Moreno, C. Zhou: Synchronization in complex networks. In: Physics Reports. 469, 2008, S. 93–153.
- Brockmann et al.: The scaling laws of human travel. In: Nature. 439, 2006, S. 462–465.
- D. J. Watts: Six Degrees: The Science of a Connected Age. W. W. Norton & Company, 2003, ISBN 0-393-04142-5.
- A.-L. Barabási, Eric Bonabeau: Skalenfreie Netze. In: Spektrum der Wissenschaft. Juli, 2004, S. 62–69.
- Malte Landwehr: Graphzentralität in Autor-Zitate Netzwerken. Graphzentralitäten als Alternativen zu h-Index und PageRank bei der Bewertung von Wissenschaftlern. GRIN Verlag, München 2011, ISBN 978-3-656-00775-3, urn:nbn:de:101:1-201109192114.
- Money-Circulation Science (englisch), The New York Times Magazine – The 6th Annual Year in Ideas. Abgerufen am 10. Dezember 2006.