Ein Netz ohne Skalen ist ein Netz, dessen Grad-Vertrieb einem Macht-Gesetz mindestens asymptotisch folgt. D. h. der Bruchteil P (k) Knoten im Netz, das k Verbindungen zu anderen Knoten hat, geht für große Werte von k als

:

P (k) \\sim \ck^\\boldsymbol {-\gamma }\

</Mathematik>

wo eine Normalisierung unveränderlich ist und ein Parameter ist, dessen Wert normalerweise in der Reihe ist, sind 2 Bevorzugte Verhaftung und das Fitnessmodell als Mechanismen vorgeschlagen worden, vermuteten Macht-Gesetzgrad-Vertrieb in echten Netzen zu erklären.

Geschichte

In Studien der Netze von Zitaten zwischen wissenschaftlichen Papieren hat Derek de Solla Price 1965 gezeigt, dass die Zahl von Verbindungen zu Papieren — d. h., die Zahl von Zitaten, die sie erhalten — einen Vertrieb mit dem schweren Schwanz im Anschluss an einen Vertrieb von Pareto oder Macht-Gesetz, und so hatten, dass das Zitat-Netz ohne Skalen ist. Er hat den Begriff "Netz-ohne Skalen" nicht jedoch gebraucht, das bis einige Jahrzehnte später nicht ins Leben gerufen wurde. In einer späteren Zeitung 1976 hat Preis auch einen Mechanismus vorgeschlagen, das Ereignis von Macht-Gesetzen in Zitat-Netzen zu erklären, die er "kumulativen Vorteil" genannt hat, aber die heute unter dem Namen bevorzugte Verhaftung allgemeiner bekannt sind.

Das neue Interesse an Netzen ohne Skalen hat 1999 mit der Arbeit von Albert-László Barabási und Kollegen an der Universität der Notre Dame angefangen, die die Topologie eines Teils des World Wide Web kartografisch dargestellt hat, findend, dass einige Knoten, die sie "Mittelpunkte" genannt haben, noch viele Verbindungen hatten als andere, und dass das Netz als Ganzes einen mit der Machtgesetzvertrieb der Zahl von Verbindungen hatte, die zu einem Knoten in Verbindung stehen. Nach der Entdeckung, dass einige andere Netze, einschließlich einiger sozialer und biologischer Netze, auch Grad-Vertrieb mit dem schweren Schwanz hatten, haben Barabási und Mitarbeiter den Begriff "Netz-ohne Skalen" ins Leben gerufen, um die Klasse von Netzen zu beschreiben, die einen mit der Machtgesetzgrad-Vertrieb ausstellen. Amaral. hat gezeigt, dass die meisten wirklichen Netze in zwei große Kategorien gemäß dem Zerfall des Grad-Vertriebs P (k) für großen k eingeteilt werden können.

Barabási und Albert haben einen generativen Mechanismus vorgeschlagen, das Äußere des mit der Machtgesetzvertriebs zu erklären, den sie "bevorzugte Verhaftung" genannt haben, und der im Wesentlichen dasselbe als das ist, das durch den Preis vorgeschlagen ist. Analytische Lösungen für diesen Mechanismus (auch ähnlich der Lösung des Preises) wurden 2000 von Dorogovtsev, Mendes und Samukhin und unabhängig von Krapivsky, Redner und Leyvraz präsentiert, und später streng vom Mathematiker Béla Bollobás bewiesen. Namentlich, jedoch, erzeugt dieser Mechanismus nur eine spezifische Teilmenge von Netzen in der Klasse ohne Skalen, und viele alternative Mechanismen sind seitdem entdeckt worden.

Die Geschichte von Netzen ohne Skalen schließt auch etwas Unstimmigkeit ein. Auf einem empirischen Niveau ist die Natur ohne Skalen von mehreren Netzen in Zweifel gezogen worden. Zum Beispiel, die drei Brüder Faloutsos hat geglaubt, dass das Internet einen Macht-Gesetzgrad-Vertrieb auf der Grundlage von traceroute Daten hatte; jedoch ist es darauf hingewiesen worden, dass das eine Schicht 3 Trugbild ist, das durch Router geschaffen ist, die als Knoten des hohen Grads erscheinen, während sie die innere Schicht 2 Struktur des ASes verbergen, den sie miteinander verbinden.

Auf einem theoretischen Niveau sind Verbesserungen zur abstrakten Definition von ohne Skalen vorgeschlagen worden. Zum Beispiel, Li u. a. (2005) hat sich kürzlich potenziell genauer "ohne Skalen metrisch" geboten. Lassen Sie kurz G ein Graph mit dem Rand sein setzt E, und zeigen den Grad eines Scheitelpunkts (d. h. die Zahl des Rand-Ereignisses zu) dadurch an. Definieren Sie

:

Das wird maximiert, wenn Knoten des hohen Grads mit anderen Knoten des hohen Grads verbunden werden. Definieren Sie jetzt

:

wo s der maximale Wert von s (H) für H im Satz aller Graphen mit dem zu G identischen Grad-Vertrieb ist. Das gibt einen metrischen zwischen 0 und 1, wo ein Graph G mit kleinem S (G) "an der Skala reich" ist, und ein Graph G mit S (G) in der Nähe von 1 "ohne Skalen" ist. Diese Definition gewinnt den Begriff der Selbstähnlichkeit, die im "ohne Skalen" Namen einbezogen ist.

Eigenschaften

Die bemerkenswerteste Eigenschaft in einem Netz ohne Skalen ist die Verhältnishäufigkeit von Scheitelpunkten mit einem Grad, der außerordentlich den Durchschnitt überschreitet. Die Knoten des höchsten Grads werden häufig "Mittelpunkte" genannt und werden gedacht, spezifischen Zwecken in ihren Netzen zu dienen, obwohl das außerordentlich vom Gebiet abhängt.

Das Eigentum ohne Skalen entspricht stark der Robustheit des Netzes zum Misserfolg. Es stellt sich heraus, dass den Hauptmittelpunkten von kleineren nah gefolgt wird. Diesen wird abwechselnd von anderen Knoten mit einem noch kleineren Grad und so weiter gefolgt. Diese Hierarchie berücksichtigt eine Schuld tolerantes Verhalten. Wenn Misserfolge aufs Geratewohl vorkommen und die große Mehrheit von Knoten diejenigen mit dem kleinen Grad sind, ist die Wahrscheinlichkeit, dass ein Mittelpunkt betroffen würde, fast unwesentlich. Selbst wenn ein Mittelpunkt-Misserfolg vorkommt, wird das Netz allgemein seinen Zusammenhang wegen der restlichen Mittelpunkte nicht verlieren. Andererseits, wenn wir einige Hauptmittelpunkte wählen und sie aus dem Netz nehmen, wird das Netz in eine Reihe ziemlich isolierter Graphen verwandelt. So sind Mittelpunkte sowohl eine Kraft als auch eine Schwäche von Netzen ohne Skalen. Diese Eigenschaften sind analytisch mit der Perkolationstheory von Cohen studiert worden u. a. und durch Callaway und al.

Eine andere wichtige Eigenschaft von Netzen ohne Skalen ist der sich sammelnde mitwirkende Vertrieb, der abnimmt, als der Knotengrad zunimmt. Dieser Vertrieb folgt auch einem Macht-Gesetz. Das deutet an, dass die Knoten des niedrigen Grads sehr dichten Subgraphen gehören und jene Subgraphen mit einander durch Mittelpunkte verbunden werden. Denken Sie ein soziales Netz, in dem Knoten Leute sind und Verbindungen Bekanntschaft-Beziehungen zwischen Leuten sind. Es ist leicht zu sehen, dass Leute dazu neigen, Gemeinschaften, d. h., kleine Gruppen zu bilden, in denen jeder jeden kennt (kann man an solche Gemeinschaft wie ein ganzer Graph denken). Außerdem haben die Mitglieder einer Gemeinschaft auch einige Bekanntschaft-Beziehungen Leuten außerhalb dieser Gemeinschaft. Einige Menschen werden jedoch mit einer Vielzahl von Gemeinschaften (z.B, Berühmtheiten, Politiker) verbunden. Jene Leute können als die für das Klein-Weltphänomen verantwortlichen Mittelpunkte betrachtet werden.

Zurzeit ändern sich die spezifischeren Eigenschaften von Netzen ohne Skalen mit dem generativen Mechanismus, der verwendet ist, um sie zu schaffen. Zum Beispiel legen Netze, die durch die bevorzugte Verhaftung normalerweise erzeugt sind, die Scheitelpunkte des hohen Grads in der Mitte des Netzes, sie zusammen verbindend, um einen Kern mit progressiv Knoten des niedrigeren Grads zu bilden, die die Gebiete zwischen dem Kern und der Peripherie zusammensetzen. Die zufällige Eliminierung sogar eines großen Bruchteils von Scheitelpunkten presst den gesamten Zusammenhang des Netzes sehr wenig zusammen, darauf hinweisend, dass solche Topologien für die Sicherheit nützlich sein konnten, während ins Visier genommene Angriffe den Zusammenhang sehr schnell zerstören. Andere Netze ohne Skalen, die die Scheitelpunkte des hohen Grads an der Peripherie legen, stellen diese Eigenschaften nicht aus. Ähnlich kann sich der sich sammelnde Koeffizient von Netzen ohne Skalen bedeutsam abhängig von anderen topologischen Details ändern.

Eine Endeigenschaft betrifft die durchschnittliche Entfernung zwischen zwei Scheitelpunkten in einem Netz. Als mit den meisten unordentlichen Netzen, wie das kleine Weltnetzmodell, ist diese Entfernung hinsichtlich eines hoch bestellten Netzes wie ein Gitter-Graph sehr klein. Namentlich, ein unkorrelierter mit der Machtgesetzgraph, der 2 Als solcher hat, wird die Natur ohne Skalen von vielen Netzen noch von der wissenschaftlichen Gemeinschaft diskutiert. Einige Beispiele von Netzen haben behauptet, ohne Skalen zu sein, schließen Sie ein:

• Soziale Netze, einschließlich Kollaborationsnetze. Ein Beispiel, das umfassend studiert worden ist, ist die Kollaboration von Filmschauspielern in Filmen.
• Sexuelle Partner in Menschen, der die Streuung von Geschlechtskrankheiten betrifft.
• Viele Arten von Computernetzen, einschließlich des Internets und des webgraph des World Wide Web.
• Wechselwirkungsnetze des Protein-Proteins.
• Semantische Netze.
• Luftfahrtgesellschaft-Netze.

Klettern Sie freie Topologie ist auch in hohen Temperatursupraleitern gefunden worden. Die Qualitäten von Hoch-Temperatursupraleiter — eine Zusammensetzung, in der Elektronen den Gesetzen der Quant-Physik und dem Fluss in der vollkommenen Gleichzeitigkeit ohne Reibung folgen — scheinen verbunden mit den fractal Maßnahmen von anscheinend zufälligen Sauerstoff-Atomen.

Generative Modelle

Diese Netze ohne Skalen entstehen zufällig allein nicht. Erdős und Rényi (1960) haben ein Modell des Wachstums für Graphen studiert, in denen, an jedem Schritt, zwei Knoten gleichförmig aufs Geratewohl gewählt werden und eine Verbindung zwischen ihnen eingefügt wird. Die Eigenschaften dieser zufälligen Graphen sind von den Eigenschaften verschieden, die in Netzen ohne Skalen gefunden sind, und deshalb ist ein Modell für diesen Wachstumsprozess erforderlich.

Das größtenteils weit bekannte generative Modell für eine Teilmenge von Netzen ohne Skalen ist Barabási, und Albert (1999) reich bekommen reicheres generatives Modell, in dem jede neue Webseite Verbindungen zu vorhandenen Webseiten mit einem Wahrscheinlichkeitsvertrieb schafft, der, aber nicht gleichförmig

ist

proportional zum Strom im Grad Webseiten. Dieses Modell wurde von Derek J. de Solla Price 1965 unter dem Begriff kumulativer Vorteil ursprünglich entdeckt, aber hat Beliebtheit nicht erreicht, bis Barabási die Ergebnisse unter seinem aktuellen Namen (BA Modell) wieder entdeckt hat. Gemäß diesem Prozess wird eine Seite mit vielen in den Verbindungen mehr in den Verbindungen anziehen als eine regelmäßige Seite. Das erzeugt ein Macht-Gesetz, aber der resultierende Graph unterscheidet sich

vom wirklichen Webgraphen in anderen Eigenschaften wie die Anwesenheit kleinen

dicht verbundene Gemeinschaften. Allgemeinere Modelle und Netzeigenschaften sind vorgeschlagen und studiert worden (für eine Rezension sieh das Buch von Dorogovtsev und Mendes).

Ein etwas verschiedenes generatives Modell für Webverbindungen ist von Pennock angedeutet worden u. a. (2002). Sie haben Gemeinschaften mit Interessen an einem spezifischen Thema wie die Hausseiten von Universitäten, Aktiengesellschaften, Zeitungen oder Wissenschaftlern untersucht, und haben die Hauptmittelpunkte des Webs verworfen. In diesem Fall war der Vertrieb von Verbindungen nicht mehr ein Macht-Gesetz, aber hat einer Normalverteilung geähnelt. Gestützt auf diesen Beobachtungen haben die Autoren ein generatives Modell vorgeschlagen, das bevorzugte Verhaftung mit einer Grundlinie-Wahrscheinlichkeit mischt, eine Verbindung zu gewinnen.

Ein anderes generatives Modell ist das von Kumar studierte Kopie-Modell u. a. (2000),

in dem neue Knoten einen gegenwärtigen Knoten aufs Geratewohl wählen und einen Bruchteil der Verbindungen des gegenwärtigen Knotens kopieren. Das erzeugt auch ein Macht-Gesetz.

Interessanterweise ist das Wachstum der Netze (das Hinzufügen neuer Knoten) nicht eine notwendige Bedingung, für ein Netz ohne Skalen zu schaffen. Dangalchev (2004) führt Beispiele an, statische Netze ohne Skalen zu erzeugen. Eine andere Möglichkeit (Caldarelli u. a. 2002) soll die Struktur als statisch denken und eine Verbindung zwischen Scheitelpunkten gemäß einem besonderen Eigentum der zwei beteiligten Scheitelpunkte ziehen. Einmal angegeben der statistische Vertrieb für diese Scheitelpunkt-Eigenschaften (fitnesses), es stellt sich heraus, dass in einigen Verhältnissen auch statische Netze Eigenschaften ohne Skalen entwickeln.

Ideales Netz ohne Skalen

Im Zusammenhang der Netztheorie ist ein ideales Netz ohne Skalen ein zufälliges Netz mit einem Grad-Vertrieb im Anschluss an den idealen Gasdichte-Vertrieb ohne Skalen. Diese Netze haben das spezielle Eigentum, den Stadtgröße-Vertrieb und die Wahlergebnisse wieder hervorzubringen, die den Größe-Vertrieb von sozialen Gruppen mit der Informationstheorie über komplizierte Netze, ausfasern

wenn ein Wettbewerbstraube-Wachstumsprozess auf das Netz angewandt wird. In Modellen von idealen Netzen ohne Skalen ist es möglich zu demonstrieren, dass die Zahl von Dunbar die Ursache des als die 'sechs Grade der Trennung bekannten Phänomenes' ist.

Siehe auch

• Netzmodell der sozialen Kreise - ein mehr verallgemeinertes generatives Modell für viele "wirkliche Netze", von denen das Netz ohne Skalen ein spezieller Fall ist
• Zufälliger Graph
• Erdős-Rényi Modell
• Erklettern Sie invariance
• Kompliziertes Netz
• Webgraph
• Caldarelli G. "Netze ohne Skalen" Presse der Universität Oxford, Oxford (2007).
• Robb, John. Netze ohne Skalen und Terrorismus, 2004.

Links

• snGraph Optimale Software, um Netze ohne Skalen zu führen.
• Der Erdős Webgraph Server, der die Hypertext-Link-Struktur eines wöchentlichen aktualisierten, den ständig zunehmenden Teil des WWW beschreibt.