Posts mit dem Label Netzwerke werden angezeigt. Alle Posts anzeigen
Posts mit dem Label Netzwerke werden angezeigt. Alle Posts anzeigen

Mittwoch, 23. Juni 2010

23. Juni - Linked - The New Science of Networks


Es ist dem Siegeszug des "Internets" zu danken, dass Begriffe wie Netzwerk oder Vernetzung heute nicht mehr nur zum Fachvokabular von Informatik gehören, sondern in jüngster Zeit auch in den Kultur- und Sozialwissenschaften als Beschreibung bekannt geworden sind.

Das Buch “Linked - The New Science of Networks” von Albert-László Barabás habe ich nun durch und am Anfang jeder Netzwerk-Theorie stehen zwei Fragen. Zunächst ganz generell: Was sind Netzwerke überhaupt? Die Antwort hierauf fällt leicht: Netzwerke werden beschrieben als Systeme aus Knoten ("nodes"), die sich durch Verbindungen ("links") zu komplexen Strukturen vereinen. Man kann hier genauso gut an das Netz von Stromleitungen zwischen verschiedenen Kraftwerken denken oder aber auch an ein virtuelles Netz, mit welchem etwa der Infektionsweg ansteckender Krankheiten beschrieben wird.

Die zweite Frage nach dem spezifischen Aufbau, also nach der Struktur von Netzwerken ist ungleich schwerer zu beantworten. Traditionellerweise folgte man hier der These der beiden ungarischen Mathematiker Erdös und Rényi, wonach Netzwerke zufällig und ungeordnet entstehen und daher die Verteilungswahrscheinlichkeit der Links zwischen den Knoten im gesamten System gleich groß ist.

Dieser "random"-These widerspricht Barabási nun aber für die von ihm untersuchten natürliche Netze grundsätzlich: Verhielte es sich so, wie Erdös und Rényi behaupten, dann müßten alle Knoten eines bestimmten Netzes über eine jeweils berechenbare Zahl an Links mit allen anderen Knoten verbunden sein. Bekannt geworden ist diese Überlegung in den sechziger Jahren als "small world"-Phänomen: Alle Amerikaner seien über eine Kette von nur fünf oder sechs Bekanntschaften miteinander zusammengeschlossen.

Doch Barabásis genauer Blick auf solche Netze erweist, daß dieser Zufälligkeit im Aufbau des Netzes enge Grenzen gesetzt sind: So stehen im Internet zum Beispiel einer immensen Vielzahl nur schwach frequentierter Websites einige wenige gegenüber, die tatsöchlich jedermann kennt und nutzt. Eine solche klare Hierarchie führt zur Ausbildung von einigen wenigen Zentren ("hubs"), um die herum sich die gesamte Struktur des Netzes organisiert. Das heißt: Je entwickelter ein Netzwerk ist, umso deutlicher lässt sich zwischen Zentrum und Peripherie unterscheiden.

Der Faktor Zeit spielt hier eine wichtige Rolle: Je früher ein Knoten im System des Netzes bereits angelegt wurde, um so größer sind seine Chancen, sich selbst zu einem solchen machtvollen Zentrum auszubilden, denn neu hinzukommende Links siedeln sich nach dem Prinzip "rich get richer" vorzugsweise an bereits existierende Zentren an.
Der schöne Mythos vom demokratischen und durch grenzenlose Freiheit bestimmten Internet sollte angesichts dieser Neigung der Netze zur allmählichen und schleichenden Monopolbildung wohl noch einmal neu befragt werden. Unübersehbar sind Netze damit zugleich auch ein effizientes Instrument zur Verteilung von Einfluß und Macht.

Barabási zeigt im übrigen aber einleuchtend am Beispiel der Suchmaschine Google, daß man auch als "new kid on the block" in einem längst etablierten und in seinen Strukturen schon stark ausgeprägten Netz immer dann eine Chance hat, sich zu behaupten, wenn man auffallend attraktiver ist, als alle anderen es sind. Nur so konnte sich Google als spät gestartete und zunächst völlig unbekannte Website innerhalb kürzester Zeit gegenüber allen anderen Konkurrenten zu einem der populärsten und meistgenutzten "hubs" des Internets überhaupt mausern.

Freitag, 18. Juni 2010

18. Juni – Die Bacon-Zahl


Ich habe weiter im dem Buch „linked“ von Albert-Laszlo Barabasi gelesen und dabei bin ich auf die Bacon Zahl gestoßen.

Die Bacon-Zahl (KBZ) ist die Länge der kürzesten Kette von Schauspielern, die gemeinsam in einem Film spielen, zu Kevin Bacon und dies stellt eine Veranschaulichung des entdeckten Kleine-Welt-Phänomens (small world phenomenon) dar.
Das Kleine-Welt-Phänomen ein von Stanley Milgram 1967 geprägter sozialpsychologischer Begriff, der innerhalb der sozialen Vernetzung in der modernen Gesellschaft den hohen Grad abkürzender Wege durch persönliche Beziehungen bezeichnet. Er bezeichnet eine Hypothese, nach der jeder Mensch (sozialer Akteur) auf der Welt mit jedem anderen über eine überraschend kurze Kette von ca, 6-7 Bekanntschaftsbeziehungen verbunden ist.

Bei der Bacon Zahl hat Kevin Bacon die KBZ 0, jeder Schauspieler, der mit ihm einen Film gedreht hat, hat die KBZ 1, ein Schauspieler, der mit einem dieser Schauspieler einen Film gedreht hat, jedoch nicht mit Kevin Bacon, hat die KBZ 2 usw.
Die Bacon-Zahl gibt einen Hinweis auf das Kleine-Welt-Phänomen „Ich kenne jemanden, der kennt jemanden, der wieder jemanden kennt, ...“, welches über recht wenige Zwischenstationen von jedem beliebigen Menschen zu jedem anderen führt. Bei über 800.000 eingetragenen Schauspielern ist die durchschnittliche Kevin-Bacon-Zahl kleiner als 3.

Bekannte Kleine Welten sind beispielsweise das amerikanische Stromnetz, nahezu alle Teilmengen von sozialen Netzwerken, eine Submenge der Seiten des WWW, sonstige Artikel, bspw. in einer Enzyklopädie, die miteinander durch Verweise verlinkt sind und auch die Router des Internets. Um die Störungsanfälligkeit dieser Netze zu beurteilen, ist dies ein bedeutsamer Ansatz, denn man kann eine Störung auch als eine 'Nachricht' auffassen.

Die spezielle Vernetzung eines skalenfreien Netzes macht ein solches robust gegen den zufälligen Ausfall einiger Knoten oder Kanten. Falls aber wichtige Knoten (hubs) gezielt entfernt werden, zerfällt das Netzwerk schnell in Teilnetze. Dies ist der Grund, warum der Ausfall nur weniger Router im Internet weitreichende Auswirkungen haben kann. Umgekehrt hat die skalenfreie Struktur des Internet auch die rasche Verbreitung von Computerviren zur Folge, falls diese einmal die Knoten erreicht haben.

Dienstag, 15. Juni 2010

15. Juni – Power Laws


Ich höre zurzeit das Buch „Linked“ von Albert-Laszlo Barabasi und dabei werden mit etwas das vollkommen neu für mich ist: „Power Laws“ (Potenzgesetze) und „Scale-free network“ (Skalenfreie Netzwerke).

Potenzgesetze (engl. power laws) gehören zu den Skalengesetzen und beschreiben die Skaleninvarianz vieler natürlicher Phänomene als polynomielle Abhängigkeiten zweier Größen y und x in der Form
Dabei ist a der Vorfaktor und b der Exponent des Potenzgesetzes, und die durch + ... angedeuteten Zusatzterme sind vernachlässigbar. Im Allgemeinen ist a irrelevant, d.h. man interessiert sich nur für den Exponenten des Potenzgesetzes.

Skalenfreie oder Skaleninvariante Netzwerke oder Netze sind Netzwerke, die keine typische Anzahl von Verbindungen pro Knoten aufweisen. Weil ihr Verlinkungsgrad keiner Skala folgt, bezeichnet man sie als skaleninvariant.

Die Verteilung von Knoten und der Anzahl k von Verbindungen folgt einem Potenzgesetz


wobei γ eine einheitslose Zahl ist. ALLES KLAR??!??



Skalenfreie Netzwerke werden in der Netzwerktheorie untersucht und gelten als relativ ausfallsicher. Die Robustheit solcher Netzwerke besteht allerdings nur bei zufälligen Ausfällen von Knoten. Durch strategisches Vorgehen beim Ausschalten einzelner Knoten (nämlich derjenigen mit hohem Verlinkungsgrad) kann ein skalenfreies Netzwerk schnell in kleine Einzelnetzwerke zerfallen.

Beispiele für skalenfreie und partiell-skalenfreie Netzwerke sind:

  • Netz der Zusammenarbeit von Schauspielern in Filmen (γ = 3), siehe auch Bacon-Zahl
  • Stromnetz - z.B. der westlichen USA (γ = 4)
  • Der Zitationsgraph (Graph von Zitierungen) von wissenschaftlichen Artikeln (k ist die Zahl der erhaltenen Zitationen, γ = 3)
  • Verteilung Einwohnerzahlen von Städten (γ = 2,3)
  • Verlinkungsgrad der deutschsprachigen Wikipedia

Viele Kleine-Welt-Netzwerke sind auch skalenfrei bzw. umgekehrt, wobei zu beachten ist, dass normale Zufallsgraphen nicht skalenfrei sind.

Barabási und Albert schlugen ein vielbeachtetes Modell zur Erzeugung skalenfreier Netzwerke vor. Dabei wird mit einer kleinen Anzahl m0 von Knoten begonnen und in jedem Schritt ein weiterer Knoten hinzugefügt. Der neue Knoten wird jeweils mit m bereits vorhandenen Knoten verbunden, wobei die Verbindungs-Wahrscheinlichkeit proportional zur Anzahl von Kanten ist, die ein Knoten bereits besitzt. Dieses Prinzip wird auch als preferential attachment bezeichnet. Es lässt sich zeigen, dass in diesem Modell γ gegen den Wert 3 strebt.

Viele Netzwerkwahrscheinlichkeiten, z. B. finanzielle Verteilungen, bestehen aus nicht-Gauß'schen Verteilungen mit skalenfreien Ausläuferbereichen (sog. "fat tails"), die das erhöhte Risiko für extreme Gewinne bzw. Verluste(!) quantifizieren, während bei den Gaußverteilungen selbst, mit denen die üblichen Standardbeispiele für Zufallsprozesse formuliert werden, diese extremen Risikobereiche fatalerweise automatisch wegfallen.

Mittwoch, 9. Juni 2010

09. Juni – Burst von Albert-László Barabási


Ich habe nun das Buch „Burst- The Hidden Pattern Behind Everything We Do“ durch. Also auf Deutsch wäre die Übersetzung „Anhäufungen – die verstecken Mustern hinter alles was wir tun“ aber bisher gibt es das Buch noch nicht in Deutschland.

Der Author Albert-László Barabási ist eher für seinen Buch „Linked“ gekannt. Ein sehr gutes und leicht lesbares Buch zum Thema Netzwerke, ausgehend von den bekannten Small-World-Networks Untersuchungen von Milgram bis hin zu aktuellen Ergebnissen. Gespickt mit vielen kleinen Anekdoten ist das Buch nicht nur informativ, sondern macht auch noch Spaß.

Albert-László Barabási ist ein ungarischer Professor für Physik Der gebürtige Szekler studierte Ingenieurswesen in Rumänien und Ungarn bevor er in die USA zog, wo er seitdem lebt.

Barabásis wichtigster Beitrag ist die Einführung der Theorie skalenfreier Netzwerke im Rahmen der Netzwerktheorie, die er, in Zusammenarbeit mit Forschern aus den Bereichen der Physik, Mathematik und Informatik, seit Anfang der 1990er Jahre vorantreibt. Im Rahmen dieser Arbeit untersucht er unter anderem die komplexen Strukturen sozialer Netzwerke (u.a. epidemiologische Untersuchung von AIDS aber auch die Funktion von Terrornetzwerken), des World Wide Webs und biologischer Zellen. Hervorzuheben sind hier insbesondere seine Theorie über die bevorzugte Bindung (preferential attachment) neuer Knoten an bereits gut vernetzte Teilnehmer (sogenannte hubs) in einem Netzwerk.

Leider ist das Buch „Burst“ für meinen Geschmack ein bisschen zu verstreut. Forschungsergebnisse sind teilweise vergraben in sehr detaillierte Erzählung von einem ungarischen Bauernkrieg in Transsylvanien in 16. Jahrhundert und die Szekler.

Die Szekler sind eine ungarischsprachige (Szekler-Dialekt) Bevölkerung im Osten Siebenbürgens (in der Mitte Rumäniens). Da die Szekler als Grenzwächter seit dem Mittelalter über vom ungarischen König garantierte Privilegien verfügten, betonten sie stets ihre eigene Szekler-Identität. Diese Identität kam leider viel zu übermächtig in dem Buch durch.

Ich habe dennoch viel sehr gute Denkanstöße bekommen und ich freue mich darauf bald „Linked“ zu lesen.