Wachstumsmodelle für Netze verständlich erklärt

In einer neuen Siedlung lernt jede neu zugezogene Familie zwei Nachbarn kennen. Wen, entscheidet eine einfache Regel. Diese Seite zeigt, wie die Regel bestimmt, ob alle ähnlich viele Leute kennen oder einzelne Familien sehr viele.

Zuletzt aktualisiert: 11. November 2026

Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.

Eine Siedlung wächst Familie für Familie

Stellen Sie sich eine neue Siedlung vor. Anfangs wohnen dort nur wenige Familien, und alle kennen sich. Jeden Monat zieht eine neue Familie ein. Sie kennt noch niemanden. Bald lernt sie zwei Nachbarn kennen, nicht mehr und nicht weniger. Alle Bekanntschaften zusammen bilden das Netz der Siedlung.

Die Frage ist: Welche zwei Nachbarn? Im ersten Fall ist jede Familie gleich wahrscheinlich. Die Neue greift sich ihre Bekannten sozusagen aus dem Hut.

Im zweiten Fall lernt sie bevorzugt Familien kennen, die schon viele kennen. Das ist als Bild gedacht: Wer viele kennt, wird beim Straßenfest öfter erwähnt und häufiger vorgestellt. Wer wenige kennt, bleibt eher unbemerkt.

Daraus folgt eine Rückkopplung. Wer früh viele kennt, bekommt weitere dazu und fällt dadurch noch mehr auf. Fachleute nennen diese Regel bevorzugte Anbindung. Eine Familie mit sehr vielen Bekanntschaften heißt dann Hub.

Das Programm zum Ausprobieren

Zu dieser Seite gehört ein Programm zum Ausprobieren, die Demo. Der erste Knopf unten öffnet sie, der zweite führt zum zweiten Teil für Fachleute. Zum Verstehen brauchen Sie die Demo nicht.

Sie lässt am Rechner eine solche Siedlung wachsen, nach einem vereinfachten Rechenbild (Fachwort: Modell). Ein Regler ändert die Regel, nach der sich Neue anbinden. Alle Aussagen auf dieser Seite beschreiben dieses Rechenbild, nicht echte Siedlungen.

Die fünf Beispiele zum Anklicken sind Einzelläufe. Im Beispiel mit normaler Bevorzugung kennt die bekannteste Familie 103 andere. Der typische Wert aus fünf Läufen liegt höher. Ein Einzelfall zeigt die Richtung, nicht die Größe.

Sechs Regeln, sechs Spitzen

Die Demo vergleicht Regeln an einer Siedlung mit 4000 Familien, in der jede Neue zwei Nachbarn kennenlernt. Gemessen wird, wie viele andere die bekannteste Familie (die Spitze) am Ende kennt. Genommen wird jeweils der mittlere Wert (Fachwort: Median) aus fünf Läufen.

• Keine Bevorzugung: Jede Familie ist gleich wahrscheinlich. Die bekannteste kennt 20 andere.
• Normale Bevorzugung mit Alterung: Wer lange in der Siedlung wohnt, wird für Neue weniger interessant. Die bekannteste kennt 21 andere.
• Schwache Bevorzugung: Die Chance wächst langsamer als die Zahl der Bekannten. Die bekannteste kennt 36 andere.
• Normale Bevorzugung: Die Chance wächst im gleichen Verhältnis wie die Zahl der Bekannten. Die bekannteste kennt 145 andere.
• Normale Bevorzugung mit Anziehungskraft (Fachwort: Fitness): Jede Familie hat eine zufällige Anziehungskraft, und wer mehr davon hat, wird öfter gewählt. Die bekannteste kennt mehr als die 145 von eben. Wie viele mehr, schwankt von Lauf zu Lauf stark.
• Starke Bevorzugung: Die Chance wächst schneller als die Zahl der Bekannten. Die bekannteste kennt mehr als vier Fünftel der Siedlung.

Je stärker die Bevorzugung, desto größer die Spitze. Diese Reihenfolge ist in der Messung stabil, die genauen Zahlen sind es nicht. Eine Deutung: Wächst die Chance schneller als die Zahl der Bekannten, lohnt sich jeder weitere Bekannte besonders. Dann zieht die Spitze immer mehr Neue an.

Bei starker Bevorzugung gewinnt oft keine einzelne Familie allein. Die zweitbekannteste kennt laut Messung über viele Läufe im Median etwa 84 % so viele wie die bekannteste, doch einzelne Läufe streuen stark.

Die Alterung hebt den Vorteil der Bevorzugung fast ganz auf. Früh einziehen reicht dann nicht, denn der Vorsprung der Alten verliert mit den Jahren an Wert. Die Spitze bleibt so klein wie ohne Bevorzugung.

Warum eine einzelne Kennzahl täuscht

Fachleute fassen das Bild einer Siedlung gern in eine einzige Kennzahl. Die hängt davon ab, welchen Teil man misst, ähnlich wie das Tempo einer Autofahrt: Auf der Autobahn kommt eine andere Zahl heraus als in der Stadt. Hier entscheidet, ab wie vielen Bekannten man mitzählt. Eine Kennzahl sagt deshalb wenig, solange niemand dazusagt, wie gemessen wurde.

Häufige Missverständnisse

• „Hubs sind die Besten.“ Nicht in der normalen Regel. Dort sind alle Familien beim Einzug gleich. Den Vorsprung bringen Zufall und frühes Einziehen, denn wer früher kommt, hat mehr Zeit zum Sammeln.
• „Stärkere Bevorzugung bringt mehr Hubs.“ Nein. Die bekannteste Familie wird größer, aber es bleiben wenige Familien, die so viel an sich ziehen. Bei starker Bevorzugung kennt die bekannteste mehr als vier Fünftel der Siedlung.
• „Die Kennzahl der Demo zeigt, ob die Regel stimmt.“ Nein. Das Verfahren rechnet auch dann eine Zahl aus, wenn es keine Hubs gibt. Ohne Bevorzugung kam in der Demo ebenfalls eine heraus.

Woran Sie das im Alltag erkennen

Anzeichen, dass eine solche Regel mitspielen könnte:

• Viele wählen, was schon viele gewählt haben, etwa das volle Lokal oder den Kanal mit den meisten Abonnenten. Ein kleiner Vorsprung verstärkt sich dann selbst.
• Ein paar Namen sind überall bekannt, die meisten nur wenigen. Das Bild ist schief, nicht gleichmäßig.
• Wer neu dazukommt, holt gegen die Etablierten schwer auf, außer er ist wirklich anziehender.

Das sind Hinweise, kein Beweis. Auch andere Gründe führen zu einem schiefen Bild, und die Demo prüft das nicht.

Wie ernst ist das Rechenbild zu nehmen?

Im Rechenbild hängen sich nur Neue an Bestehende. Es gibt keine neuen Bekanntschaften unter den Alten, keine Umzüge und keine echten Daten. Es zeigt, was eine einfache Regel erzeugen kann, nicht, wie echte Netze entstanden sind.

Was Sie mitnehmen:

• Eine einfache Regel kann ein schiefes Bild erzeugen, ohne dass jemand es plant.
• Von schwach bis stark reicht das Bild von „alle ähnlich“ bis „wenige beherrschen alles“. Die Stärke der Regel entscheidet.
• Fragen Sie bei einer Kennzahl aus einem endlichen Netz immer, wie sie gemessen wurde.

Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.

Modell und Annahmen

Dieser Teil ist eigenständig lesbar. Er beschreibt ein Wachstumsmodell für Netze (bevorzugte Anbindung und ihre Varianten), seine Theorie, die Messungen der Demo und deren Grenzen.

• Wachstum: Start mit \(m+1\) vollständig verbundenen Knoten. Danach kommt je Zeitschritt \(t\) ein neuer Knoten und verbindet sich mit \(m\) verschiedenen bestehenden Knoten. Die Ziele werden nacheinander ohne Zurücklegen gezogen, jedes bestehende \(i\) mit Wahrscheinlichkeit proportional zu einem Gewicht \(w_i\) (nächster Abschnitt).
• Symbole: \(n\) ist die Zahl der Knoten am Ende, \(k_i\) der Grad von Knoten \(i\) (Zahl seiner Verbindungen), \(t_i\) seine Ankunftszeit, \(a\) der Exponent der Anbindung, \(A_0\) die Anfangsattraktivität, \(\nu\) die Stärke der Alterung und \(\eta_i\) die Fitness von Knoten \(i\).
• Varianten: \(a = 0\) ist Zufallsanbindung, \(a = 1\) linear (Barabási–Albert), \(a < 1\) unterlinear, \(a > 1\) überlinear. \(A_0 > 0\) lässt auch Knoten mit wenigen Verbindungen eine Chance. \(\nu > 0\) senkt das Gewicht alter Knoten mit dem Faktor \((t - t_i + 1)^{-\nu}\), bei \(\nu = 1\) also umgekehrt proportional zum Alter. Die Fitness \(\eta_i\) ist gleichverteilt in \((0, 1]\) oder überall 1.
• Regler und Voreinstellung: \(n\) von 500 bis 10 000 (3 000), \(m\) von 1 bis 5 (2), \(a\) von 0 bis 2 (1), \(A_0\) von 0 bis 10 (0), \(\nu\) von 0 bis 2 (0), Fitness aus oder gleichverteilt.
• Kennzahlen: die Gradverteilung \(P(k)\) (Anteil der Knoten mit Grad \(k\)), der größte Grad \(k_{\max}\), der Hubanteil \(s = k_{\max} / \sum_i k_i\) (Anteil des größten Hubs an allen Kantenenden) und der geschätzte Exponent \(\hat\alpha\) ab einer Untergrenze \(k_{\min}\), in der Hauptansicht \(3m\).
• Rechenweg: Eigener Code (numpy). Das allgemeine Wachstum rechnet quadratisch in \(n\). Die rein lineare Regel läuft über eine Liste der Kantenenden in fast linearer Zeit: Jeder Knoten steht so oft darin, wie sein Grad ist, und ein Ziehen aus der Liste hat dieselbe Verteilung wie das Gewicht \(k_i\).
• Messreihen: Mediane über fünf Läufe mit festen Zufallsfolgen. Die Zufallszahlen sind über alle Größen \(n\) gekoppelt (dieselbe Folge liefert für jedes \(n\) dieselben ersten Zufallszahlen), die Werte für verschiedene \(n\) sind daher stark korreliert.

Die Formeln

Ein neuer Knoten, der zur Zeit \(t\) eintrifft, wählt einen bestehenden Knoten \(i\) mit Wahrscheinlichkeit proportional zum Gewicht

\[w_i = (k_i + A_0)^{a} \, (t - t_i + 1)^{-\nu} \, \eta_i.\]

Für lineare Anbindung (\(a = 1\), \(A_0 = \nu = 0\), \(\eta_i = 1\)) hat die Gradverteilung im Grenzfall \(n \to \infty\) für \(k \ge m\) den Wert

\[P(k) = \frac{2m(m+1)}{k(k+1)(k+2)} \sim k^{-3}.\]

Das ist ein Potenzgesetz mit dem Exponenten \(\gamma = 3\). Bei Zufallsanbindung (\(a = 0\), sonst wie oben) fällt sie exponentiell:

\[P(k) = \frac{1}{m+1} \left( \frac{m}{m+1} \right)^{k-m}.\]

Bei \(a = 1\) und \(A_0 > 0\) ist der Exponent \(\gamma = 3 + A_0 / m\). Der Exponent-Schätzer für diskrete Daten nutzt die \(N\) Knoten mit Grad \(k_i \ge k_{\min}\):

\[\hat\alpha = 1 + N \big/ \sum_i \ln\!\big(k_i / (k_{\min} - 1/2)\big)\]

Er ist keine Anpassungsprüfung: Er rechnet auch für Verteilungen, die kein Potenzgesetz sind, eine Zahl aus.

Herleitungen Schritt für Schritt

Die folgenden Herleitungen sind Rechnungen dieser Seite (Mean-Field-Näherungen: Der Zufallsprozess wird durch seine Erwartungswerte ersetzt), keine Messungen der Demo. Wo die Demo dieselbe Größe misst, steht es dabei.

Lineare Anbindung: Wachstum eines Knotens und Gradverteilung.

• Schritt 1: Jede Ankunft fügt \(m\) Kanten hinzu, also \(2m\) zur Gradsumme. Zur Zeit \(t\) ist die Gradsumme etwa \(2mt\).
• Schritt 2: Ein Knoten \(i\) bekommt pro Ankunft im Mittel etwa \(m\,k_i / (2mt) = k_i / (2t)\) neue Kanten. Die Näherung ignoriert, dass die \(m\) Ziele verschieden sein müssen.
• Schritt 3: Aus \(\mathrm{d}k_i/\mathrm{d}t = k_i/(2t)\) und \(k_i(t_i) = m\) folgt

\[k_i(t) = m \sqrt{t / t_i}\]

• Schritt 4: Für eine Schwelle \(x \ge m\) ist \(k_i(t) < x\) genau dann, wenn \(t_i > m^2 t / x^2\). Sind die Ankunftszeiten gleichverteilt auf \([0, t]\), hat das die Wahrscheinlichkeit \(1 - m^2/x^2\). Die Dichte ist \(2m^2/x^3\), also ein Potenzgesetz mit Exponent 3.
• Schritt 5: Die exakte Verteilung oben hat im Zähler \(2m(m+1)\) statt \(2m^2\). Die Näherung trifft den Exponenten, nicht den Vorfaktor.
• Schritt 6: Der älteste Knoten hat \(t_i\) von der Größenordnung 1, also \(k_{\max} \sim m\sqrt{n}\). Die Demo misst das Wurzelwachstum (das Verhältnis \(k_{\max}/\sqrt{n}\) ist von \(n\) unabhängig); die Konstante hängt von \(m\) ab, die Näherung liefert sie nicht.

Zufallsanbindung. Hier bekommt jeder Knoten pro Ankunft etwa \(m/t\) neue Kanten. Aus \(\mathrm{d}k_i/\mathrm{d}t = m/t\) folgt \(k_i(t) = m\,(1 + \ln(t/t_i))\). Damit ist \(k_i(t) > x\) genau dann, wenn \(t_i < t\,e^{-(x/m - 1)}\), und mit gleichverteilten Ankunftszeiten hat das die Wahrscheinlichkeit \(e^{-(x/m - 1)}\): ein exponentieller Abfall wie in der exakten Formel. Die Basis der Näherung, \(e^{-1/m}\), weicht von der exakten \(m/(m+1)\) ab; die Näherung trifft die Form, nicht die Basis.

Anfangsattraktivität. Die Summe der Gewichte \(k_i + A_0\) ist etwa \((2m + A_0)\,t\). Aus \(\mathrm{d}k_i/\mathrm{d}t = m\,(k_i + A_0) / ((2m + A_0)\,t)\) folgt \(k_i + A_0 \propto t^{m/(2m + A_0)}\). Der Exponent der Verteilung ist dann \(1 + (2m + A_0)/m = 3 + A_0/m\), wie oben angegeben.

Obergrenze des Hubanteils.

• Schritt 1: Weil die \(m\) Ziele verschieden sind, bekommt ein gegebener Knoten pro Ankunft höchstens eine Kante. Sein Grad ist also höchstens etwa \(n\).
• Schritt 2: Die Gradsumme ist etwa \(2mn\). Also gilt \(s \lesssim 1/(2m)\), bei \(m = 2\) etwa 25 %.
• Schritt 3: Gemessen sind 24,7 % bei \(a = 2\), \(n = 3\,000\), \(m = 2\) (Tabelle unten): Der Hub bekam bei fast jeder Ankunft eine Kante. Die Obergrenze folgt aus dem Zählen; dass sie bei \(a = 2\) nahezu erreicht wird, ist die Messung.
• Folgerung: Jede Kante hat zwei Enden. Hält der größte Hub 20,4 % der Kantenenden, steckt er in gut zwei Fünfteln aller Kanten (Rechnung dieser Seite).

Warum der Schätzer unter 3 liegt und mit \(k_{\min}\) steigt. Die lokale Steigung der exakten Kurve ist \(-\mathrm{d}\ln P/\mathrm{d}\ln k = 1 + k/(k+1) + k/(k+2)\). Sie ist für jedes endliche \(k\) kleiner als 3 und wächst gegen 3. Ein Schätzer, der alle Grade ab \(k_{\min}\) mittelt, liefert deshalb für kleine \(k_{\min}\) Werte unter 3, die mit \(k_{\min}\) steigen. Das passt zur Messung und zur Beobachtung, dass der Schätzer auf der exakten Grenzverteilung 2,58 bis 2,97 ergibt. Die Rechnung erklärt die Richtung, nicht die Werte.

Durchgerechnet

Rechnung dieser Seite, keine Messung der Demo, außer wo angegeben.

• Theoriewerte für \(m = 2\): \(P(2) = (2 \cdot 2 \cdot 3) / (2 \cdot 3 \cdot 4) = 0{,}5\) und \(P(3) = (2 \cdot 2 \cdot 3) / (3 \cdot 4 \cdot 5) = 0{,}2\). Bei Zufallsanbindung ist \(P(2) = 1/(m+1) = 1/3\). Die Summe der linearen Verteilung ist 1, denn \(1/(k(k+1)(k+2)) = \tfrac12\,[1/(k(k+1)) - 1/((k+1)(k+2))]\) teleskopiert zu \(1/(2m(m+1))\) für \(k \ge m\).
• Kantenzahl: Die Startgruppe hat \(m(m+1)/2\) Kanten, danach kommen \(m\) je weiterem Knoten: \(m(m+1)/2 + (n-m-1)\,m\). Für \(n = 3\,000\), \(m = 2\) sind das 5 997.
• Hubanteil eines Einzellaufs: Größter Grad 103 geteilt durch \(2 \cdot 5\,997\) Kantenenden ergibt 0,9 %, weit unter der Obergrenze.
• Exponent mit Anfangsattraktivität: \(m = 2\), \(A_0 = 3\) gibt \(3 + 3/2 = 4{,}5\).
• Ein Schritt von Hand (\(m = 2\), \(a = 1\), \(A_0 = \nu = 0\), keine Fitness): Start ist ein Dreieck, alle Grade sind 2. Der Knoten 4 wählt die Knoten 1 und 2, danach haben sie Grad 3, die Knoten 3 und 4 Grad 2. Knoten 5 findet die Gewichte 3, 3, 2 und 2 mit Summe 10. Die erste Ziehung trifft sie mit Wahrscheinlichkeit 3/10, 3/10, 2/10 und 2/10. Weil die zweite Ziehung ohne Zurücklegen erfolgt, ist der Vorteil eines Knotens mit Grad 3 in der Wahrscheinlichkeit, überhaupt gewählt zu werden, etwas kleiner als das Gewichtsverhältnis 3 : 2.

Befunde

Alle Zahlen stammen aus den Messungen der Demo, sofern nichts anderes dabeisteht. Mediane gelten über fünf Läufe mit festen Zufallsfolgen, Einzelläufe sind genannt. Fünf Läufe sind wenig: Wo die Messgröße stark streut (größter Grad, Fitness, zweitgrößter Hub), gelten die Rangfolgen, die scharfen Zahlen nicht.

Frage	Befund
Stimmt der Kern?	Der Endgrad des ältesten Knotens stimmt für fünf Regeln mit der durch Aufzählung aller Zustände berechneten Verteilung überein (nur \(m = 1\), 7 Knoten, je 12 000 Läufe, Prüfschwelle fünf Standardfehler). Der schnelle Sampler verhält sich wie das allgemeine Wachstum (KS-Test, 2 500 Läufe). Gegen networkx.barabasi_albert_graph bei \(m = 3\) liegen Hubgröße (im Mittel mehrerer Netze) innerhalb von 20 % und Exponent innerhalb von 0,08.
Welche Werte hat die Theorie?	Ein einzelnes Netz mit 64 000 Knoten (\(m = 3\)) liegt bei den Graden 3, 4, 5, 6, 8 und 10 innerhalb von 8 % der linearen Theorie. Ein einzelnes Netz mit Zufallsanbindung (8 000 Knoten, \(m = 2\)) liegt bei den Graden 2, 3, 4, 6 und 8 innerhalb von 15 %.
Einzelläufe der fünf Beispiele?	Linear (\(n = 3\,000\), \(m = 2\)): größter Grad 103, Hubanteil 0,9 %, \(\hat\alpha = 2{,}79\). Zufallsanbindung (\(n = 2\,500\)): größter Grad 22, \(\hat\alpha = 3{,}98\) (bedeutungslos, die Verteilung ist exponentiell). Überlinear (\(a = 1{,}5\)): größter Grad 2 037 mit 20,4 % der Kantenenden, der zweitgrößte (Grad 1 893) mit 18,9 %, zusammen 39 %. Alterung (\(\nu = 1\), \(n = 2\,500\)): größter Grad 18, \(\hat\alpha = 4{,}34\) (die Reihe unten gibt als Median bei \(n = 4\,000\) 4,52). Fitness: 233, mehr als im linearen Einzellauf bei etwas kleinerem \(n\).
Hängt der Exponent von der Untergrenze ab? (linear, \(n = 16\,000\), \(m = 3\))	Ja: \(\hat\alpha = 2{,}58\) bei \(k_{\min} = 3\) (alle 16 000 Knoten), 2,78 bei \(k_{\min} = 6\) (rund 4 570 Knoten) und 2,95 bei \(k_{\min} = 40\) (rund 120 Knoten); Theorie für \(n \to \infty\): 3. Der Median liegt in der ganzen Reihe unter 3, ein systematischer Effekt. Bei \(k_{\min} = 40\) streut der Wert von Lauf zu Lauf um etwa \(\pm 0{,}1\); einzelne Netze liegen dort über 3 (Maximum 3,07 in weiteren Läufen).
Wie wächst der größte Grad? (linear, \(m = 3\))	117 bei \(n = 1\,000\), 254 bei 4 000, 488 bei 16 000 und 972 bei 64 000; geteilt durch \(\sqrt{n}\) zwischen 3,7 und 4,0, das 1,2- bis 1,3-fache von \(m\sqrt{n}\). Die fünf Läufe liegen am oberen Rand: Mit 400 weiteren Zufallsfolgen ist der Median von \(k_{\max}/\sqrt{n}\) 2,96 (\(n = 1\,000\)) und 3,00 (4 000). Robust ist das Wachstum wie \(\sqrt{n}\); die Konstante hängt von \(m\) ab (Median von \(k_{\max}/(m\sqrt{n})\): 1,87 bei \(m = 1\), 1,30 bei 2, 1,03 bei 3, 0,76 bei 5).
Wie unterscheiden sich die Regeln? (Median des größten Grades, \(n = 4\,000\), \(m = 2\))	Zufallsanbindung 20, mit Alterung 21, unterlinear (\(a = 0{,}5\)) 36, Anfangsattraktivität 3 gibt 54, linear 145, linear mit Fitness 746, überlinear (\(a = 1{,}5\)) 3 327. Die Rangfolge ist robust, die scharfen Zahlen nicht: Mit 15 weiteren Läufen liegt Fitness bei etwa 509 (Spanne 303 bis 712, 746 ist der Ausreißer) und überlinear zwischen 2 466 und 3 714. Bei überlinearer Anbindung hält der größte Hub 20,8 % der Kantenenden (mit 15 weiteren Läufen im Median 20,05 %, Spanne 15 bis 22 %), bei linearer 0,9 %. Geschätzter Exponent (Median): linear 2,78, mit Alterung 4,52, mit Anfangsattraktivität 3 gibt 3,20 bei einer Theorie von 4,5.
Wie groß ist der zweitgrößte Hub? (überlinear, \(a = 1{,}5\), \(m = 2\))	Laut Messdokumentation der Demo hat er 84 % (\(n = 4\,000\)) bis 90 % (\(n = 10\,000\)) des Grades des größten, als Median über mehr Läufe als die fünf festen; die Angabe steht nur dort. Eine Nachrechnung dieser Seite mit 40 weiteren Läufen ergibt Mediane wenige Prozentpunkte darunter, einzelne Läufe zwischen gut einem Fünftel und gleich viel; der Median der fünf festen Läufe liegt bei \(n = 4\,000\) deutlich niedriger. Es gewinnt also meist kein einzelner Knoten. Bei \(m = 1\) ist es anders: ein Knoten hält 46 %, der zweite nur 1,2 % des ersten. Ebenfalls Rechnung dieser Seite (\(n = 4\,000\), \(m = 2\), Median der fünf festen Läufe): Knoten mit Grad mindestens fünfzig gibt es ein Dutzend bei \(a = 1\), 7 bei \(a = 1{,}5\) und 2 bei \(a = 2\); stärkere Bevorzugung heißt also größere, aber weniger Hubs.
Wo kippt die Anbindung? (Hubanteil, \(n = 3\,000\), \(m = 2\))	\(a = 0\): 0,2 %, \(a = 0{,}5\): 0,3 %, \(a = 1\): 1,0 %, \(a = 1{,}25\): 6,8 %, \(a = 1{,}5\): 20,4 %, \(a = 2\): 24,7 %. Der Anteil wächst steil ab \(a = 1\) und sättigt bei etwa 25 %. Bei \(a = 1{,}5\) hängt er von \(m\) ab (\(m = 1\): 46 %, \(m = 5\): 7 %) und nur schwach von \(n\) (\(n = 1\,000\): 18,8 %, \(n = 10\,000\): 22,2 %).

Grenzen und was die Messung zeigt

Was sie belegt:

• Die Rangfolge der Regeln: Zufall, unterlinear, Anfangsattraktivität, linear, Fitness, überlinear. Zufall (20) und Alterung (21) liegen so dicht beieinander, dass ihre Reihenfolge nichts besagt. Die scharfen Zahlen von Fitness, überlinear und \(k_{\max}/\sqrt{n}\) gelten nicht.
• Das Wurzelwachstum des größten Grades, die Abhängigkeit des Schätzers von \(k_{\min}\) (beides bei \(m = 3\), linear) und die Theoriewerte für linear und Zufall.

Was sie nicht belegt:

• Einzelläufe: Die fünf Beispiele sind einzelne Läufe. Der lineare Einzellauf liegt unter dem Median der Reihe bei \(n = 4\,000\), und auch zwischen den fünf festen Läufen streut der größte Grad stark (bei \(n = 4\,000\), \(m = 3\) von 169 bis 294).
• Der Schätzer ist keine Anpassungsprüfung: Er liefert auch bei Zufallsanbindung (3,98) und bei Alterung (4,34), jeweils die Einzelläufe der Tabelle, eine Zahl. Die Demo prüft nicht, ob ein Potenzgesetz zu den Daten passt, und nutzt eine feste Untergrenze \(3m\). Das Verfahren von Clauset, Shalizi und Newman (Wahl von \(k_{\min}\) nach einem Abstandsmaß) ist nicht enthalten.
• Anfangsattraktivität: Der Schätzer erreicht die Theorie nicht (Tabelle, \(m = 2\), \(A_0 = 3\)). Eine Nachrechnung dieser Seite mit dem Code der Demo (\(n = 4\,000\), fünf Läufe) zeigt: Der Wert steigt mit der Untergrenze und überschreitet 4,5 erst bei einer Untergrenze um dreißig, wo nur wenige Dutzend Knoten im Schwanz liegen. Mit anderen Zufallsfolgen liegt er dort knapp an der Theorie. Eine mögliche Deutung ist, dass die Gewichte \(k + A_0\) die Kurve erst für \(k \gg A_0\) bestimmen, ungeprüft.
• Alterung, Fitness, überlineare Anbindung: Die Demo gibt dafür keine Theorie der Gradverteilung an und gleicht ihre Zahlen nicht mit der Literatur ab. Die Arbeiten der Quellenliste behandeln sie, aus dem Gedächtnis: Krapivsky, Redner und Leyvraz finden bei unterlinearer Anbindung eine gestreckt exponentielle Verteilung und bei überlinearer ein Gelieren, bei dem ein Knoten einen Teil der Kanten an sich zieht, und für \(a > 2\) nahezu alle neuen Kanten. Bianconi und Barabási zeigen für Fitness ein Potenzgesetz, dessen Exponent von der Fitnessverteilung abhängt. Für Alterung gibt es eine Arbeit von Dorogovtsev und Mendes.
• \(m\sqrt{n}\) ist nur die Größenordnung: Die Wurzel-Skalierung ist gezeigt, die Konstante hängt von \(m\) ab (Tabelle).
• Hubanteil bei \(a = 2\): Die Obergrenze etwa 25 % folgt aus dem Zählen (siehe Herleitung); warum sie dort nahezu erreicht wird, ist nicht gesondert geprüft.
• Kleine Netze: \(n\) liegt zwischen 500 und 10 000; die Messreihen laufen bis 64 000 Knoten nur mit der schnellen linearen Regel. Aussagen über \(n \to \infty\) sind Extrapolation.
• Keine realen Netze: Die Demo vergleicht Modelle mit Theorie, nicht mit Daten. Gerichtete, gewichtete oder mehrfache Kanten gibt es nicht.
• Nicht enthalten: eine Anpassungsprüfung des Potenzgesetzes, Wachstum durch Kopieren oder Triadenschluss (hohes Clustering) und gerichtete Netze wie Zitationsnetze (andere Gradverteilung).

Erweiterungen und Verweise

Was die Demo auslässt, behandeln andere Demos dieser Website:

• Potenzgesetz prüfen: Der Potenzgesetz-Test schätzt den Exponenten, bestimmt, ab wo das Gesetz gilt, und prüft die Güte durch einen Zufallstest und den Vergleich mit Alternativen.
• Netze zu gegebenen Graden: Das Konfigurationsmodell zieht Netze zu vorgegebenen Gradfolgen, ohne zu fragen, woher diese kommen.
• Zufallsnetz ohne Hubs: Der Zufallsgraph ist das einfachste Zufallsnetz, in dem jede Kante unabhängig entsteht.

Quellen

• Barabási und Albert (1999): Emergence of scaling in random networks, Science (lineare bevorzugte Anbindung).
• Krapivsky, Redner und Leyvraz (2000): Connectivity of growing random networks, Physical Review Letters (unter- und überlineare Anbindung).
• Dorogovtsev, Mendes und Samukhin (2000): Structure of growing networks with preferential linking, Physical Review Letters (Anfangsattraktivität).
• Bianconi und Barabási (2001): Competition and multiscaling in evolving networks, Europhysics Letters (Fitness).
• Dorogovtsev und Mendes (2000): Evolution of networks with aging of sites, Physical Review E (Alterung).
• Clauset, Shalizi und Newman (2009): Anpassung von Potenzgesetzen an empirische Daten.
• Quelltext, Messreihen und Tests der Demo: github.com/sebastian-hanisch/wachstumsmodelle-demo.

Die genannten Arbeiten wurden für diese Seite nicht nachgeschlagen; die Angaben stammen aus dem Gedächtnis und aus der Demo, wo sie als nicht im Original geprüft vermerkt sind. Das Beispiel einer Siedlung im ersten Teil ist erdacht und stammt nicht aus der Demo. Die Herleitungen, der Handschritt, die Nachrechnungen zur Anfangsattraktivität, zum zweitgrößten Hub und zur Zahl der Hubs sind Rechnungen dieser Seite und keine Messungen der Demo.