Zufallsnetzwerke und Random Walks: Eine praktische Einführung mit R

Einleitung: Warum Netzwerke heute überall sind

Ob Freundschaftsempfehlungen auf Instagram, die Verbreitung von KI-generierten Memes oder die Struktur des Internets – hinter den Kulissen stecken oft Zufallsnetzwerke. In diesem Tutorial lernst du, wie du mit R und dem igraph-Paket eigene Netzwerke erstellst, ihre Eigenschaften untersuchst und Random Walks simulierst. Der Stoff orientiert sich an typischen Projekten aus dem ECE 232E Kurs – aber wir lösen keine Aufgaben, wir verstehen die Konzepte.

Grundlagen: Das igraph-Paket in R

Zunächst installierst du igraph: install.packages('igraph'). Danach lädst du es: library(igraph). Wir arbeiten mit zwei Modellen: dem Erdős–Rényi (ER) Modell und dem Barabási–Albert (BA) Modell. Beide sind fundamental für das Verständnis von Zufallsnetzwerken.

Erdős–Rényi Netzwerke erstellen

Das ER-Modell erzeugt einen Graphen mit n Knoten, wobei jede Kante mit Wahrscheinlichkeit p unabhängig existiert. In R nutzt du erdos.renyi.game(n, p, type='gnp'). Beispiel für n=900 und p=0.006:

g_er <- erdos.renyi.game(900, 0.006, type='gnp')

Die Gradverteilung ist binomial, was du mit degree(g_er) und hist() überprüfen kannst. Theoretisch gilt: Mittelwert = n*p, Varianz = n*p*(1-p). Vergleiche deine empirischen Werte mit diesen Formeln.

Zusammenhang und Riesenkomponente

Für p=0.006 ist der Graph oft nicht zusammenhängend. Mit is.connected(g_er) prüfst du das. Die größte Zusammenhangskomponente (GCC) findest du mit clusters(g_er). Der Durchmesser der GCC gibt die längste kürzeste Pfadlänge an – wichtig für die Effizienz von Suchalgorithmen, wie sie etwa in sozialen Netzwerken verwendet werden.

Ein spannender Effekt: Die normalisierte GCC-Größe springt bei p ≈ 1/n ≈ 0.0011 von nahe 0 auf fast 1. Das ist der Phasenübergang, den du durch Sweepen über p-Werte (z.B. von 0.001 bis 0.015) und 100 Wiederholungen pro p visualisieren kannst. Der Schwellwert für >99% GCC liegt bei etwa p = ln(n)/n ≈ 0.0076.

Preferential Attachment: Das Barabási–Albert Modell

Anders als ER erzeugt das BA-Modell skalenfreie Netzwerke mit Potenzgesetz-Gradverteilung. In R: barabasi.game(n, m, directed=FALSE). Für n=1050, m=1:

g_ba <- barabasi.game(1050, m=1, directed=FALSE)

Diese Netzwerke sind fast immer zusammenhängend. Die Gradverteilung folgt P(k) ~ k^{-3}. Im Log-Log-Plot (mit plot(log(degree_dist), log='xy')) siehst du eine Gerade – die Steigung per linearer Regression ist der Exponent.

Community Detection und Assortativität

Mit cluster_fast_greedy(g_ba) findest du Communities. Die Modularität misst, wie gut die Communities vom Zufall abweichen. Assortativität (Korrelation der Grade benachbarter Knoten) berechnest du mit assortativity_degree(g_ba). In BA-Netzwerken ist sie oft negativ – Hubs verbinden sich bevorzugt mit vielen kleinen Knoten.

Random Walks auf Netzwerken

Ein Random Walk simuliert einen zufälligen Pfad. Starte an einem Knoten, wähle zufällig einen Nachbarn, wiederhole. In R:

random_walk <- function(g, steps) {
  node <- sample(V(g), 1)
  path <- node
  for (i in 1:steps) {
    neighbors <- neighbors(g, node)
    if (length(neighbors) == 0) break
    node <- sample(neighbors, 1)
    path <- c(path, node)
  }
  return(path)
}

Messe die durchschnittliche Distanz ⟨s(t)⟩ vom Start und die Varianz σ²(t). Auf ER-Netzwerken wächst ⟨s(t)⟩ zunächst schnell, dann langsamer – der Walk erkundet den Graphen. Auf BA-Netzwerken mit fat-tailed Gradverteilung ist die Varianz größer, weil der Walk oft an Hubs hängen bleibt.

Vergleich ER vs. BA

Für n=900 und p=0.015 ist der ER-Graph klein und der Walk erreicht schnell den Durchmesser. Bei n=9000 dauert es länger. Der BA-Graph mit m=1 hat einen kleineren Durchmesser (Small-World-Effekt), aber die Gradverteilung der besuchten Knoten unterscheidet sich von der globalen: Der Walk besucht häufiger Knoten mit hohem Grad.

Modifikation: Altersabhängige Anziehung

Im erweiterten BA-Modell beeinflusst das Alter eines Knotens die Anziehungswahrscheinlichkeit. Die Funktion sample_pa_age in igraph erlaubt Parameter α (Gradabhängigkeit) und β (Altersabhängigkeit). Mit β=-1 werden alte Knoten benachteiligt – ähnlich wie bei Trend-Themen in sozialen Medien, die nach einiger Zeit an Relevanz verlieren.

Erzeuge ein solches Netzwerk mit n=1050, m=1, α=1, β=-1, a=c=d=1, b=0:

g_age <- sample_pa_age(1050, m=1, pa.exp=1, aging.exp=-1, aging.bin=1)

Die Gradverteilung zeigt einen steileren Abfall (höherer Exponent). Die Modularität mit Fast Greedy ist oft niedriger als im Standard-BA-Modell, weil die Altersabhängigkeit die Community-Struktur stört.

Praktische Tipps für deine Projekte

• Vergleiche theoretische und empirische Werte: Berechne Mittelwert und Varianz der Grade und setze sie in Beziehung zu n*p.
• Nutze Schleifen für Sweeps: Für die GCC-Analyse iteriere über p-Werte und sammle die Ergebnisse in einem Data Frame.
• Log-Log-Plots: Verwende plot(..., log='xy') und abline(lm(...)) für die Regressionsgerade.
• Achte auf Selbstloops: Bei sample_degseq können Selbstloops entstehen – entferne sie mit simplify().

Fazit

Zufallsnetzwerke und Random Walks sind mächtige Werkzeuge, um reale Phänomene zu modellieren – von der Ausbreitung von KI-Apps bis zur Struktur des Internets. Mit R und igraph kannst du diese Konzepte selbst erkunden. Probiere verschiedene Parameter aus und beobachte, wie sich die Netzwerkeigenschaften ändern. Viel Erfolg bei deinen Projekten!