Zufallsgraphen und Random Walks in R – Tutorial für ECE 232E

Einleitung: Warum Zufallsgraphen und Random Walks?

Zufallsgraphen sind ein zentrales Werkzeug der Netzwerkwissenschaft. Sie helfen uns, reale Phänomene wie soziale Netzwerke, das Internet oder Epidemien zu modellieren. In diesem Tutorial lernst du, wie du mit R Zufallsgraphen erzeugst, ihre Eigenschaften analysierst und Random Walks darauf simulierst. Die Beispiele sind an das ECE 232E Projekt angelehnt, aber eigenständig und lehrreich.

1. Erzeugung von Zufallsgraphen mit dem Erdős-Rényi-Modell

Das Erdős-Rényi (ER) Modell ist der einfachste Zufallsgraph: Gegeben n Knoten, wird jede Kante mit Wahrscheinlichkeit p unabhängig gezogen. Wir nutzen R und das Paket igraph.

1.1 Netzwerke erzeugen und Gradverteilung plotten

Für n = 900 und verschiedene p (0.002, 0.006, 0.012, 0.045, 0.1) erzeugen wir Graphen und plotten die Gradverteilung. Die Verteilung ist binomial, nähert sich aber für kleine p einer Poisson-Verteilung an. Der mittlere Grad ist np, die Varianz np(1-p).

library(igraph)
n <- 900
p_werte <- c(0.002, 0.006, 0.012, 0.045, 0.1)
for (p in p_werte) {
  g <- sample_gnp(n, p)
  deg <- degree(g)
  hist(deg, main = paste("Gradverteilung p =", p), xlab = "Grad")
  cat("p =", p, "Mittelwert:", mean(deg), "Varianz:", var(deg), "\n")
}

Die theoretischen Werte bestätigen sich: Mittelwert ≈ np, Varianz ≈ np(1-p).

1.2 Zusammenhang und riesige Zusammenhangskomponente

Für jedes p prüfen wir, ob der Graph zusammenhängend ist. Für kleine p ist er es selten. Wir schätzen die Wahrscheinlichkeit durch 100 Wiederholungen. Die riesige Zusammenhangskomponente (GCC) entsteht bei p ≈ 1/n. Für p = 0.002 ist der Graph meist zerteilt; der Durchmesser der GCC ist dann klein.

p <- 0.006
connected_count <- 0
for (i in 1:100) {
  g <- sample_gnp(900, p)
  if (is_connected(g)) connected_count <- connected_count + 1
}
cat("Wahrscheinlichkeit für Zusammenhang bei p =", p, ":", connected_count/100)

1.3 Größte Komponente als Funktion von p

Wir variieren p von 0 bis 0.1 und plotten die relative Größe der GCC. Der Schwellwert, bei dem eine GCC entsteht, liegt bei p ≈ 1/n = 0.0011. Bei p ≈ ln(n)/n ≈ 0.005 wird der Graph fast sicher zusammenhängend.

pmax <- 0.1
p_seq <- seq(0, pmax, length.out = 50)
gcc_avg <- numeric(length(p_seq))
for (j in seq_along(p_seq)) {
  p <- p_seq[j]
  gcc_sizes <- numeric(100)
  for (i in 1:100) {
    g <- sample_gnp(900, p)
    comp <- components(g)
    gcc_sizes[i] <- max(comp$csize)/900
  }
  gcc_avg[j] <- mean(gcc_sizes)
}
plot(p_seq, gcc_avg, type = "l", xlab = "p", ylab = "Relative GCC-Größe")

2. Preferential Attachment-Modell

Das Barabási-Albert-Modell erzeugt skalenfreie Netze mit Potenzgesetz-Gradverteilung. Neue Knoten verbinden sich bevorzugt mit bereits gut vernetzten Knoten.

2.1 Netzwerk erzeugen und Gemeinschaften finden

Mit n = 1050, m = 1 erzeugen wir einen Graphen und nutzen den Fast-Greedy-Algorithmus zur Gemeinschaftserkennung. Die Modularität misst die Qualität der Partition.

g <- sample_pa(1050, m = 1, directed = FALSE)
fc <- cluster_fast_greedy(g)
modularity(fc)

Die Modularität ist bei diesem Modell meist niedrig, da es keine starken Gemeinschaften gibt. Für m = 2 oder 6 steigt die Dichte, aber die Modularität bleibt ähnlich.

2.2 Gradverteilung im log-log-Plot

Die Gradverteilung folgt einem Potenzgesetz: P(k) ~ k-γ. Im log-log-Plot ergibt sich eine Gerade mit Steigung -γ. Für m = 1 ist γ ≈ 3.

deg <- degree(g)
deg_dist <- degree_distribution(g)
k <- which(deg_dist > 0) - 1
pk <- deg_dist[deg_dist > 0]
plot(k, pk, log = "xy", xlab = "Grad k", ylab = "P(k)")
# Lineare Regression
fit <- lm(log(pk) ~ log(k))
abline(fit, col = "red")

2.3 Nachbarschaftsgradverteilung

Wählt man zufällig einen Knoten und dann einen zufälligen Nachbarn, hat dieser im Mittel einen höheren Grad als ein zufälliger Knoten. Dies ist der „Freunde-Paradoxon“-Effekt. Die Verteilung der Nachbargrade ist ebenfalls potenzgesetzartig, aber mit flacherem Exponenten.

neighbor_degrees <- function(g) {
  v <- sample(V(g), 1)
  nb <- neighbors(g, v)
  if (length(nb) == 0) return(NA)
  j <- sample(nb, 1)
  return(degree(g, j))
}
nd <- replicate(1000, neighbor_degrees(g))
hist(nd, breaks = 50)

3. Random Walks auf Netzwerken

Ein Random Walk ist ein Prozess, bei dem ein Walker zufällig von Knoten zu Knoten entlang der Kanten springt. Wir untersuchen die mittlere Entfernung vom Startpunkt.

3.1 Random Walk auf ER-Netzwerken

Für n = 900, p = 0.015 starten wir einen Random Walk und messen ⟨s(t)⟩ und σ²(t). Die mittlere Entfernung wächst anfangs wie √t, sättigt aber beim Durchmesser.

g <- sample_gnp(900, 0.015)
start <- sample(V(g), 1)
walk <- random_walk(g, start, steps = 100, stuck = "return")
dist <- distances(g, v = start, to = walk)
plot(0:100, dist, type = "l", xlab = "Schritte t", ylab = "Entfernung s(t)")

3.2 Vergleich mit preferential attachment-Netz

Auf einem skalenfreien Netz (BA-Modell) wächst ⟨s(t)⟩ langsamer, da Hubs den Walker anziehen und die Entfernung klein halten. Die Varianz ist ebenfalls geringer.

g_ba <- sample_pa(900, m = 1, directed = FALSE)
walk_ba <- random_walk(g_ba, start, steps = 100, stuck = "return")
dist_ba <- distances(g_ba, v = start, to = walk_ba)
plot(0:100, dist_ba, type = "l", col = "blue")

4. Modifiziertes Preferential Attachment mit Altersabnahme

Eine Erweiterung bestraft alte Knoten: Die Anbindewahrscheinlichkeit ist proportional zu (ki + 1) * (1 / (li + 1)). Dies erzeugt realistischere Netze, in denen alte Knoten irgendwann weniger Kanten erhalten.

g_age <- sample_pa_age(1050, m = 1, pa.exp = 1, age.exp = -1, aging.bin = 1)
deg_age <- degree(g_age)
hist(deg_age, breaks = 50)

Die Gradverteilung zeigt einen steileren Abfall als beim einfachen BA-Modell. Die Modularität ist ähnlich niedrig.

Fazit

Zufallsgraphen und Random Walks sind mächtige Werkzeuge, um Netzwerke zu verstehen. Mit R und igraph kannst du schnell eigene Experimente durchführen. Die Konzepte helfen dir nicht nur bei deinem Projekt, sondern auch bei aktuellen Themen wie der Analyse von sozialen Medien oder der Verbreitung von KI-Modellen. Probiere die Beispiele aus und variiere die Parameter – so entwickelst du ein Gefühl für die Dynamik.