Einleitung

Dieses Dokument gibt eine kurze Übersicht über sogenannte Random Network Models. Dabei handelt es sich um theoretisch fundierte Modelle von Netzwerken, die z. B. als Kontrastfolie zu empirischen Netzwerken herangezogen werden können. Anhand von Beispielen werden drei wichtige Modelle (Random Graph, Small Worls, Scale-free) vorgestellt, bevor diese am Ende mit einem empirischen Netzwerk verglichen werden.

Random Graph

Das erste Modell ist das Random-Graph-Modell nach Erdös und Renyi. Die zur Erstellung notwendigen Parameter sind die Anzahl an Knoten (n) und Kanten sowie ein type-Argument. Dieses spezifiziert, wie die Kanten erstellt werden sollen. Im Fall von ‘gnm’ wird der zweite Wert in der Funktion als Anzahl der zu erstellenden Knoten interpretiert. Der Wert ‘gnp’ verlangt dagegen eine Wahrscheinlichkeit, mit der eine Kante generiert wird. In dem vorliegenden Beispiel wird ein Random Graph mit 12 Knoten und 10 Kanten erstellt. Nachdem dieser in der Variable ‘g’ abgespeichert wurde, können unterschiedliche Berechnungen erfolgen; z. B. lässt sich die Dichte des erstellen Graphen berechnen. Diese ergibt sich aus dem Verhältnis der Anzahl der vorhandenen Kanten (10) zu der Anzahl an theoretisch möglichen Kanten (12*11/2).

library(igraph)
## 
## Attaching package: 'igraph'
## The following objects are masked from 'package:stats':
## 
##     decompose, spectrum
## The following object is masked from 'package:base':
## 
##     union
g <- erdos.renyi.game(n=12,10,type='gnm')
g
## IGRAPH U--- 12 10 -- Erdos renyi (gnm) graph
## + attr: name (g/c), type (g/c), loops (g/l), m (g/n)
## + edges:
##  [1] 4-- 5 2-- 8 2-- 9 2--10 2--11 7--11 2--12 3--12 4--12 6--12
graph.density(g)
## [1] 0.1515152

Dass die Kanten in diesem Modell zufällig erzeugt werden, lässt sich beobachten, wenn man zwei verschiedene Modelle, die mit denselben Werten erzeugt wurden, miteinander vergleicht.

Interessant an diesen Graphen ist, dass sie einen relativ kleinen Durchmesser besitzen, man also in relativ wenigen Schritten von einem Knoten aus jeden anderen Knoten erreichen kann.Im vorliegenden Beispiel werden Graphen mit unterschiedlicher Anzahl an Knoten erzeugt. Man erkennt deutlich, dass der Durchmesser sehr viel langsamer zunimmt als die Größe des Graphen.

Small World

Small-World Graphen stellen insofern eine Erweiterung dar, als sie der Tatsache gerecht zu werden versuchen, dass viele empirische Netzwerke über regelmäßige Strukturen im Sinne von Clustern verfügen. Das von Watts und Strogatz entwickelte Small-World-Modell versucht also sowohl kurze Pfadlängen zwischen den Knoten und hohes Clustering miteinander zu verbinden. Dabei werden die in einem Graphen vorhandenen Knoten mit einer spezifizierten Wahrscheinlichkeit neu verknüpft.

Die folgende Simulation zeigt wie mit zunehmender Wahrscheinlichkeit, dass ein Knoten neu verknüpft wird, der Durchmesser des gesamten Graphen schnell sinkt.

Scale-Free

Beide bislang besprochenen Modelle lassen allerdings ein Merkmal unberücksichtigt, welches bei empirischen Netzwerken auftritt. Diese verfügen nämlich häufig über eine so genannte power-law-Verteilung. Ein gängigerer Begriff, der dieses Phänomen umschreibt, ist der des ‘Preferential Attachment’. Damit ist gemeint, dass die Wahrscheinlichkeit, mit der zwei Knoten über eine Kante verfügen, davon abhängt, über wie viele Verknüpfungen einer der beiden verfügt. Ein Knoten, der also bereits über viele Kanten zu anderen Knoten verfügt, wird mit einer höheren Wahrscheinlichkeit mit einem neu hinzugefügten Knoten verknüpft. Anhand des folgendne Graphen lässt sich dies optisch nachvollziehen. Im Anschluss zeigt die sogenannte ‘degree distribution’ numerisch auf, wie sehr sich die einzelnen Knoten hinsichtlich der Anzahl der mit ihnen verknüpfen Kanten unterscheiden.

median(degree(g))
## [1] 1
mean(degree(g))
## [1] 1.98
table(degree(g))
## 
##  1  2  3  4  5  7  8  9 10 
## 56 25  8  4  2  1  2  1  1
op <- par(mfrow=c(1,2))
plot(degree.distribution(g),xlab="Degree",
ylab="Proportion")
plot(degree.distribution(g),log='xy',
xlab="Degree",ylab="Proportion")

par(op)

Vergleich eines empirischen Netzwerks mit den vorgestellten Graph-Modellen

Zuletzt soll ein Vergleich hergestellt werden zwischen den erläuterten Graph-Modellen und einem empirischen Netzwerk. Der Datensatz wird hierfür in ein iGraph-Objekt konvertiert (ilhds). Die Ausgabe der Variable gibt darüber Auskunft, dass das Netzwerk aus 1283 Knoten und 2708 Kanten besteht. Die Dichte des gesamten Netzwerks beträgt nur 0.003. Die durchschnittliche Anzahl an Kanten pro Knoten ist beläuft sich auf ein arithmetisches Mittel von 4.22.

library(UserNetR)
library(intergraph)
data(lhds)
ilhds <- asIgraph(lhds)
ilhds
## IGRAPH U--- 1283 2708 -- 
## + attr: title (g/c), hivscreen (v/c), na (v/l), nutrition (v/c),
## | popmil (v/n), state (v/c), vertex.names (v/c), years (v/n), na
## | (e/l)
## + edges:
##  [1]  2--  10  2--  11  2--  19  2--  20  5--1003  5--   6  6--  11
##  [8]  6--  17 10--  11 11--  19 11--  26  2--  12  6--  12 10--  12
## [15] 11--  12 12--  19 12--  26  9--  14 14--  15 14--  18 14--  25
## [22] 14--  27 14-- 226 14-- 414 14-- 697 14-- 698  2--  17 10--  17
## [29] 11--  17 16--  17 17--  19 17--  20 17--  26 16--  21 10--  26
## [36] 19--  26 28--  46 28--  53 29--  32 29--  35 29--  52 28--  30
## + ... omitted several edges
graph.density(ilhds)
## [1] 0.00329279
mean(degree(ilhds))
## [1] 4.221356

Mit den Informationen aus dem empirischen Netzwerk können nun theoretische Modelle mit denselben Spezifikationen erstellt und mit diesem verglichen werden.

g_rnd <- erdos.renyi.game(1283,.0033,type='gnp')
g_smwrld <- watts.strogatz.game(dim=1,size=1283,
nei=2,p=.25)
g_prfatt <- barabasi.game(1283,out.dist=c(.15,.6,.25),                  directed=FALSE,zero.appeal=2)

So lassen sich beispielsweise die ‘degree distributions’ der theoretischen Graphen mit dem empirischen Netzwerk vergleichen.