Skalenfreies Netzwerk

Skalenfreies Netzwerk

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.

Zufalls- vs. skalenfreies Netz

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

P \propto k^{-\gamma}

wobei γ eine einheitslose Zahl ist.

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 der westlichen USA (γ = 4)
  • Der Zitationsgraph (Graph von Zitierungen) von wissenschaftlichen Artikeln (k ist die Zahl von erhaltenen Zitationen, γ = 3)
  • Verteilung Einwohnerzahlen von Städten (γ = 2,3), Beispiel siehe Pareto-Verteilung
  • Verlinkungsgrad der deutschsprachigen Wikipedia

Viele Kleine-Welt-Netzwerke sind auch skalenfrei bzw. umgekehrt. Normale Zufallsgraphen sind nicht skalenfrei.

Barabási und Albert schlugen ein 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 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.

Siehe auch

Literatur

  • Albert-László Barabási, Eric Bonabeau: Skalenfreie Netze. In: Spektrum der Wissenschaft, Juli 2004, Seite 62-69
  • Albert-László Barabási, Réka Albert: Emergence of Scaling in Random Networks. In: Science, Vol. 286, 15. Oktober 1999
  • Barabási, Albert-László Linked: How Everything is Connected to Everything Else, Plume Book 2004 (Penguin) ISBN 0-452-28439-2
  • Paul Erdős, Alfréd Rényi: On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci., vol. 5, S. 17–61, 1960

Wikimedia Foundation.

Игры ⚽ Нужен реферат?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Skalenfreies Netz — Skalenfreie oder Skaleninvariante Netzwerke oder Netze sind komplexe Netzwerke, die keine typische Anzahl von Verbindungen pro Knoten aufweisen. Weil ihr Verlinkungsgrad nicht von der Wahl der Skala abhängt, bezeichnet man sie als skaleninvariant …   Deutsch Wikipedia

  • Netzwerk — Schematische Darstellung eines Netzes Als Netzwerke werden Systeme bezeichnet, deren zugrundeliegende Struktur sich mathematisch als Graph modellieren lässt und die über Mechanismen zu ihrer Organisation verfügen. Der Graph besteht aus einer… …   Deutsch Wikipedia

  • Kleine-Welt-Netzwerk — Das Kleine Welt Phänomen (engl. small world phenomenon, manchmal auch small world paradigm) ist ein von Stanley Milgram 1967 geprägter soziologischer Begriff, der innerhalb der sozialen Vernetzung in der modernen Gesellschaft den hohen Grad… …   Deutsch Wikipedia

  • Small-World-Netzwerk — Das Kleine Welt Phänomen (engl. small world phenomenon, manchmal auch small world paradigm) ist ein von Stanley Milgram 1967 geprägter soziologischer Begriff, der innerhalb der sozialen Vernetzung in der modernen Gesellschaft den hohen Grad… …   Deutsch Wikipedia

  • 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… …   Deutsch Wikipedia

  • Netzwerke — Schematische Darstellung eines Netzes. Als Netzwerke werden Systeme bezeichnet, deren zugrundeliegende Struktur sich mathematisch als Graph modellieren lässt und die über Mechanismen zu ihrer Organisation verfügen. Der Graph besteht aus einer… …   Deutsch Wikipedia

  • Netzwerkstruktur — Schematische Darstellung eines Netzes. Als Netzwerke werden Systeme bezeichnet, deren zugrundeliegende Struktur sich mathematisch als Graph modellieren lässt und die über Mechanismen zu ihrer Organisation verfügen. Der Graph besteht aus einer… …   Deutsch Wikipedia

  • HITS-Algorithmus — Als Hubs und Authorities lassen sich in der Netzwerktheorie herausragende Knoten anhand ihrer Verlinkung einteilen. Vereinfacht gesagt sind Hubs und Authorities dabei Knoten, die mit vielen anderen Knoten verbunden sind – beispielsweise bekannte… …   Deutsch Wikipedia

  • Hubs und Authorities — Als Hubs und Authorities lassen sich in der Netzwerktheorie herausragende Knoten anhand ihrer Verlinkung einteilen. Vereinfacht gesagt sind Hubs und Authorities dabei Knoten, die mit vielen anderen Knoten verbunden sind – beispielsweise bekannte… …   Deutsch Wikipedia

  • Kleine-Welt-Paradigma — Das Kleine Welt Phänomen (engl. small world phenomenon, manchmal auch small world paradigm) ist ein von Stanley Milgram 1967 geprägter soziologischer Begriff, der innerhalb der sozialen Vernetzung in der modernen Gesellschaft den hohen Grad… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”