Wie kann ich statistisch testen, ob mein Netzwerk (Grafik) ein "Small-World" -Netzwerk ist oder nicht?

Ein Small-World-Netzwerk ist eine Art mathematischer Graph, bei dem die meisten Knoten keine Nachbarn sind, die meisten Knoten jedoch durch eine kleine Anzahl von Sprüngen oder Schritten voneinander erreicht werden können. Insbesondere wird ein Small-World-Netzwerk als ein Netzwerk definiert, bei dem der typische Abstand L zwischen zwei zufällig ausgewählten Knoten (die Anzahl der erforderlichen Schritte) proportional zum Logarithmus der Anzahl der Knoten N im Netzwerk wächst, d. H.

$$L \approx \log(N)$$

Diese Beziehung zwischen L und N ist eine "Daumenregel". Ich suche nach einer professionelleren Bestimmung von Graphen für kleine Welten für meine Forschung. Wie kann ich testen, ob mein Diagramm ein kleines Diagramm ist oder nicht?

Das Small-World-Experiment umfasste mehrere Experimente, die von Stanley Milgram und anderen Forschern durchgeführt wurden, um die durchschnittliche Pfadlänge für soziale Netzwerke von Menschen in den USA zu untersuchen. Die Forschung war bahnbrechend, da sie darauf hinwies, dass die menschliche Gesellschaft ein Netzwerk vom Typ einer kleinen Welt ist, das durch kurze Pfadlängen gekennzeichnet ist. Die Experimente werden oft mit dem Ausdruck "sechs Trennungsgrade" assoziiert, obwohl Milgram diesen Begriff selbst nicht verwendete.

Vielen Dank im Voraus.

TL; DR:

Das kannst du nicht.

Was wird normalerweise gemacht?

Der aktuelle „Stand der Technik“ bei der Bestimmung, ob ein Netzwerk eine kleine Welt ist, verwendet den folgenden Ansatz:

1. Berechnen Sie die mittlere kürzeste Pfadlänge  und den Clustering-Koeffizienten  Ihres Netzwerks.$L$$C$

2. Generieren Sie ein geeignetes Ensemble von Nullmodellnetzwerken, z. B. Erdős-Rényi-Zufallsgraphen oder Maslov-Sneppen-Zufallsgraphen .

3. Berechnen Sie den Durchschnitt der mittleren kürzesten Pfadlänge über dieses Ensemble von Nullmodellnetzwerken. Berechnen Sie analog.C $L_\text{r}$$C_\text{r}$

4. Berechnen Sie den normalisierten kürzesten Pfad . und .$λ := L/L_\text{r}$$γ := C/C_\text{r}$

5. Wenn und bestimmte Kriterien erfüllen (z. B. und ), nennen Sie das Netzwerk ein Netzwerk mit kleiner Welt.$λ$$γ$$λ≈1$$γ>1$

Die Idee dahinter ist:

• Netzwerke mit kleiner Welt sollten eine räumliche Struktur haben, die sich in einem hohen Clusterkoeffizienten widerspiegelt. Im Gegensatz dazu haben zufällige Netzwerke keine solche Struktur und einen niedrigen Clusterkoeffizienten.

• Small-World-Netzwerke kommunizieren effizient und ähnlich und haben daher eine kleine kürzeste Pfadlänge, die mit der von zufälligen Netzwerken vergleichbar ist. Rein räumliche Netzwerke haben dagegen eine hohe kürzeste Weglänge.

Wo die Probleme liegen

• Dies sagt nichts darüber aus, wie der mittlere kürzeste Pfad mit der Netzwerkgröße skaliert. Tatsächlich kann für reale Netzwerke nicht die gesamte von Ihnen angegebene Definition angewendet werden, da es nicht dasselbe Netzwerk mit einer unterschiedlichen Anzahl von Knoten gibt.

• Nehmen wir an, wir nehmen eine andere Definition einer kleinen Welt, die nicht direkt auf den Werten von und basiert , z.$λ$$γ$

  Ein Small-World-Netzwerk ist ein räumliches Netzwerk mit zusätzlichen Fernverbindungen.

  Dann können wir immer noch keine soliden Implikationen daraus ziehen, ob eine solche Definition nur mit und (oder tatsächlich anderen Netzwerkmaßen) erfüllt wird . Die Interpretation vieler Studien geht davon aus, dass alle Netzwerke eine Realisierung des Watts-Strogatz-Modells für eine Umverdrahtungswahrscheinlichkeit sind, was überhaupt nicht gerechtfertigt ist: Wir kennen viele andere Netzwerkmodelle, deren Realisierungen sich völlig vom Watts-Strogatz-Modell unterscheiden.$λ$$γ$

• Das obige Verfahren ist nicht robust gegenüber Messfehlern. Kleine Fehler beim Aufbau eines Netzwerks aus Messungen reichen aus, um beispielsweise ein Gitter wie ein Netzwerk mit kleiner Welt aussehen zu lassen, siehe z. B. Bialonski et al., Chaos (2010) und Papo et al., Front. Summen. Neurosci. (2016) . Tatsächlich ist mir keine einzige Studie bekannt, die behauptet, dass ein empirisches Netzwerk kein Netzwerk der kleinen Welt ist.

Nebenbemerkung: Was würden Sie gewinnen?

Mir sind keine nützlichen Erkenntnisse bekannt, die sich aus einem Netzwerk als kleine Welt ableiten lassen. Die Behauptung, dass ein Netzwerktyp durch ein bestimmtes Netzwerkmodell (z. B. das Watts-Strogatz-Modell) gut beschrieben wird, mag für Modellierungsstudien nützlich sein, geht aber weit über die Behauptung der Kleinheit hinaus.

^{Vollständiger Haftungsausschluss: Eine der oben genannten Arbeiten stammt aus meiner direkten akademischen Umgebung.}

Ein Small-Worldness-Index kann in "R" mit der Funktion smallworldness im Paket qgraph berechnet werden .

Dies basiert auf: Humphries, MD & Gurney, K. (2008). Netzwerk " Small-World-Ness": Eine quantitative Methode zur Bestimmung der kanonischen Netzwerkäquivalenz . PLoS One, 3 (4), e0002051

Aus dem Papier:

"Ein Netzwerk wird jetzt als 'kleine Welt' betrachtet, wenn S> 1 ist - eine Behauptung, die statistisch getestet werden kann."