Zufälliger geometrischer Graph

Ein zufälliger geometrischer Graph ist ein ungerichteter geometrischer Graph mit Knoten gleichverteilt auf dem zugrundeliegenden Raum $[0,1)^{d}$. Zwei Knoten sind genau dann verbunden, wenn ihre Distanz geringer ist als ein zuvor spezifizierter Parameter $r\in (0,1)$.

Zufällige geometrische Graphen ähneln menschlichen sozialen Netzwerken in vielerlei Hinsicht. Sie zeigen häufig Gemeinschaftsstrukturen, d. h. es bilden sich dicht verknüpfte Gruppen von Knoten. Andere Generatoren für zufällige Graphen, wie zum Beispiel das Erdős-Rényi-Modell oder Barabási-Albert-Modell (BA-Modell), generieren keine solche Strukturen. Außerdem sind Knoten mit einem hohen Knotengrad besonders wahrscheinlich verbunden mit anderen Knoten mit einem hohen Knotengrad.

Eine Anwendung der zufälligen geometrischen Graphen besteht in der Modellierung von Ad-hoc-Netzwerken. Außerdem können sie benutzt werden, um Benchmarks für (externe) Graphalgorithmen zu erstellen.

Definition

Generierung eines zufälligen geometrischen Graphs mit n = 500 Knoten für unterschiedliche Parameter r.

Im Folgenden bezeichnet $G=(V,E)$ einen ungerichteten Graphen mit einer Knotenmenge $V$ und einer Kantenmenge $E\subseteq V\times V$. Die Knotenanzahl sei $|V|=n$, die Kantenanzahl $|E|=m$. Außerdem sind alle mathematischen Betrachtungen auf dem metrischen Raum $[0,1)^{d}$, falls nicht anders spezifiziert. Die dazugehörige Metrik ist der euklidische Abstand, also für beliebige Knoten $x,y\in [0,1)^{d}$ ist der euklidische Abstand definiert als ${\textstyle d(x,y)=\|x-y\|_{2}={\sqrt {\sum _{i=1}^{d}(x_{i}-y_{i})^{2}}}}$.

Für $n\in \mathbb {N}$ und $r\in (0,1)$ wird ein zufälliger geometrischer Graph ${\mathcal {G}}(n,r)$ generiert, indem $n$ Knoten gleichverteilt auf $[0,1)^{d}$ gezogen werden. Alle Knoten, deren euklidischer Abstand kleiner als $r\in (0,1)$ ist, werden durch eine Kante verbunden. Hierbei werden keine Schleifen betrachtet, da sonst jeder Knoten eine Schleife hätte. Damit charakterisieren die Parameter $n$ und $r$ einen zufälligen geometrischen Graph.

Algorithmen

Naiver Algorithmus

Die naive Vorgehensweise ist es, für jeden Knoten die Distanz zu jedem anderen Knoten zu berechnen. Da es ${\frac {n(n-1)}{2}}$ mögliche Verbindungen gibt, ist die Zeitkomplexität $\Theta (n^{2})$. Die Knoten werden mittels eines Zufallszahlengenerators auf $[0,1)^{d}$ generiert. Praktisch kann man dies mit $d$ Zufallszahlengeneratoren auf $[0,1)$, einen für jede Dimension, realisieren.

Ein Algorithmus in Pseudocode dafür ist:

V = generiereKnoten(n) // Generiere n Knoten im Einheitswürfel.
besuchteKnoten = {}
for each p ∈ V
    besuchteKnoten.add(p)
	for each q ∈ V\besuchteKnoten   // Da es ein ungerichteter Graph ist, müssen
	                                // bereits besuchte Knoten nicht betrachtet werden.
		if distanz(p, q) <= r
			ergänzeKante(p, q) // Füge die Kante (p, q) zur Kantendatenstruktur hinzu.
		end
	end
end

Da dieser Algorithmus nicht skalierbar ist (jeder Knoten braucht die Position jedes anderen Knotens), haben Holtgrewe et al. und Funke et al. neue Algorithmen für dieses Problem vorgeschlagen.

Verteilte Algorithmen

Holtgrewe et al.

Dieser Algorithmus, welcher von Holtgrewe et al. vorgeschlagen wurde, war der erste verteilte Generator für zufällige geometrische Graphen für Dimension 2. Das Einheitsquadrat wird hierbei in gleich große Quadrate (Zellen) mit einer Seitenlänge von mindestens $r$partitioniert. Für eine gegebene Anzahl $P=p^{2}$ von Prozessoren wird jedem Prozessor ${\textstyle {k \over p}\times {k \over p}}$ Zellen zugewiesen. Hier ist $k=\left\lfloor {1/r}\right\rfloor$ die Anzahl der Zellen der Größe $r$ in einer Dimension. Der Einfachheit halber wird $P$ als Quadratzahl angenommen, der Algorithmus kann aber für eine beliebige Anzahl an Prozessoren adaptiert werden. Jeder Prozessor generiert ${\textstyle {\frac {n}{P}}}$ Knoten im Einheitsquadrat, insgesamt werden also die benötigten $n$Knoten generiert. Wenn hierbei Knoten generiert werden, welche in eine Zelle eines anderen Prozessors gehören, werden diese dann zu den korrekten Prozessoren verteilt. Nach diesem Schritt werden die Knoten nach den Zellennummer sortiert, in welche sie fallen, zum Beispiel mit Quicksort. Danach schickt jeder Prozessor jedem benachbarten Prozessor die Position der Knoten in den Randzellen, womit dann alle Kanten generiert werden können. Die Prozessoren brauchen nicht mehr Information zur Generierung der Kanten, da die Zellen mindestens die Seitenlänge $r$haben.

Die erwartete Laufzeit ist ${\textstyle O({\frac {n}{P}}\log {\frac {n}{P}})}$. Eine obere Schranke der Kommunikationskosten ist gegeben durch $T_{all-to-all}(n/P,P)+T_{all-to-all}(1,P)+T_{point-to-point}(n/(k\cdot {P})+2)$. Hierbei ist $T_{all-to-all}(l,c)$ die Zeit, die für eine alle-zu-alle Kommunikation mit Nachrichten der Länge l bit zu $c$ Kommunikationspartnern. $T_{point-to-point}(l)$ ist die Zeit für eine Punkt-zu-Punkt Kommunikation für eine Nachricht der Länge l bit.

Da dieser Algorithmus nicht kommunikationsfrei ist, haben Funke et al. einen skalierbaren, verteilten Generator vorgeschlagen, der auch in höheren Dimensionen ohne Kommunikation zwischen den Prozessoren funktioniert.

Funke et al.

Die Vorgehensweise in diesem Algorithmus ist ähnlich zu dem Vorgehen von Holtgrewe: Man teilt den Einheitswürfel in gleich große Chunks der Seitenlänge $r$ oder größer. In der Dimension 2 sind es also Quadrate, in Dimension 3 Würfel. Da maximal ${\left\lfloor {1/r}\right\rfloor }$ Chunks in jede Dimension passen, ist die Anzahl der Chunks beschränkt durch ${\textstyle {\left\lfloor {1/r}\right\rfloor }^{d}}$. Jedem der $P$ Prozessoren werden ${\textstyle {\left\lfloor {1/r}\right\rfloor }^{d} \over P}$ Chunks zugewiesen, für welche es Punkte generiert. Für einen kommunikationsfreien Ablauf generiert jeder Prozessor zusätzlich dieselben Knoten in den benachbarten Chunks. Dies wird durch Hashfunktionen mit speziellen Seeds ermöglicht. Auf diese Weise berechnet jeder Prozessor dieselben Knoten und es müssen keine Knotenpositionen kommuniziert werden.

Für Dimension 3 haben Funke et al. bewiesen, dass die erwartete Laufzeit ${\textstyle O({\frac {m+n}{P}}+\log {P})}$ ist, ohne zusätzlichen Kosten für Kommunikation.

Eigenschaften

Isolierte Knoten und Konnektivität

Die Wahrscheinlichkeit, dass ein einzelner Knoten in einem zufälligen geometrischen Graphen isoliert ist, ist ${\textstyle (1-\pi r^{2})^{n-1}}$. Sei ${\textstyle X}$die Zufallsvariable, die zählt wie viele Knoten isoliert sind, dann ist der Erwartungswert${\textstyle E(X)=n(1-\pi r^{2})^{n-1}=ne^{-\pi r^{2}n}-O(r^{4}n)}$. Der Term ${\textstyle \mu =ne^{-\pi r^{2}n}}$enthält Informationen über die Konnektivität des zufälligen geometrischen Graphen. Für ${\textstyle \mu \longrightarrow 0}$ist der Graph asymptotisch fast sicher verbunden. Für $\mu \longrightarrow \infty$ist der Graph asymptotisch fast sicher nicht verbunden. Und für ${\textstyle \mu =\Theta (1)}$besitzt der Graph eine riesige Komponente mit mehr als ${\textstyle n \over 2}$Knoten und $X$ist Poisson verteilt mit Parameter $\mu$. Es folgt, dass falls ${\textstyle \mu =\Theta (1)}$die Wahrscheinlichkeit, dass der Graph verbunden ist, ${\textstyle P[X=0]\sim e^{-\mu }}$ist und die Wahrscheinlichkeit, dass er nicht verbunden ist, ist ${\textstyle P[X>0]\sim 1-e^{-\mu }}$. Für jede ${\textstyle l_{p}}$-Norm (${\textstyle 1\leq p\leq \infty }$) und für jede Anzahl an Dimensionen $d>2$hat der Graph eine scharfe Grenze für die Konnektivität bei ${\textstyle r\sim ({\ln(n) \over \alpha _{p,d}n})^{1 \over d}}$mit einer Konstante $\alpha _{p,d}$. Im Spezialfall des zweidimensionalen Raumes und der euklidischen Norm ($d=2$ and $p=2$) ist ${\textstyle r\sim {\sqrt {\ln(n) \over \pi n}}}$.

Hamiltonizität

Es wurde gezeigt, dass im zweidimensionalen Fall der Schwellwert ${\textstyle r\sim {\sqrt {\ln(n) \over \pi n}}}$auch Aufschluss über die Existenz eines Hamiltonischen Kreises gibt. Für jedes $\epsilon >0$, hat der Graph asymptotisch fast sicher einen Hamiltonischen Kreis falls ${\textstyle r\sim {\sqrt {\ln(n) \over (\pi +\epsilon )n}}}$und der Graph hat asymptotisch fast sicher keinen Hamiltonischen Kreis falls ${\textstyle r\sim {\sqrt {\ln(n) \over (\pi -\epsilon )n}}}$.

Clusterkoeffizient

Der Clusterkoeffizient des zufälligen geometrischen Graphen hängt ausschließlich von der Dimension $d$ des zugrundeliegenden Raumes ${\textstyle [0,1)^{d}}$ab. Der Clusterkoeffizient ist ${\textstyle C_{d}=1-H_{d}(1)}$für gerade $d$und ${\textstyle C_{d}={3 \over 2}-H_{d}({1 \over 2})}$für ungerade $d$. Hierbei ist $H_{d}(x)={1 \over {\sqrt {\pi }}}\sum _{i=x}^{d \over 2}{\Gamma (i) \over \Gamma (i+{1 \over 2})}({3 \over 4})^{i+{1 \over 2}}$.

Für große $d$, vereinfacht sich der Clusterkoeffizient zu $C_{d}\sim 3{\sqrt {2 \over \pi d}}({3 \over 4})^{d+1 \over 2}$.

Generalisierte zufällige geometrische Graphen

Waxman hat 1988 den zufälligen geometrischen Graphen generalisiert, indem die durch $r$ gegebene deterministische Verbindungsfunktion durch eine probabilistische Verbindungsfunktion ausgetauscht wird. Die von Waxman vorgestellte Variante war eine gestreckte Exponentialfunktion, bei der zwei Knoten $i$und $j$mit Wahrscheinlichkeit $H_{ij}=\beta e^{-{r_{ij} \over r_{0}}}$verbunden werden, wobei $_{ij}$die euklidische Separation ist und $\beta$sowie $r_{0}$vom System gegebene Parameter. Ein solcher zufälliger geometrischer Graph wird auch „weicher“ zufälliger geometrischer Graph genannt, welcher zwei Quellen für Zufall hat: der Ort der Knoten und die Bildung der Kanten. Die Verbindungsfunktion wurde noch weiter verallgemeinert durch ${\textstyle H_{ij}=\beta e^{-({r_{ij} \over r_{0}})^{\eta }}}$, welche oft benutzt wird, um drahtlose Netzwerke ohne Interferenz zu untersuchen. Der Parameter $\eta$gibt an, wie das Signal über die Distanz abfällt. Dabei entspricht $\eta =2$einem freien Raum und $\eta >2$entspricht gefüllteren Umgebungen wie eine Stadt ($\eta =6$wird als Modellierung für New York benutzt). Im Gegenzug entspricht $\eta <2$hoch reflektiven Umgebungen. Für $\eta =1$ergibt sich genau das Modell von Waxman und für $\eta \to \infty$und ${\textstyle \beta =1}$ergibt sich das ursprüngliche Modell des zufälligen geometrischen Graphen. Die erweiterten Verbindungsfunktionen modellieren also, wie die Wahrscheinlichkeit einer Verbindung zwischen zwei Knoten abnimmt mit deren Distanz.

Weiche zufällige geometrische Graphen

Bei Verwendung der vorgestellten Exponentialfunktion als Verbindungsfunktion in einem Netzwerk mit hoher Dichte, ist die Anzahl isolierter Knoten Poisson verteilt und das resultierende Netzwerk enthält eine einzige riesige Komponente und sonst nur isolierte Knoten. Wird sichergestellt, dass kein Knoten isoliert ist, ist der Graph asymptotisch fast sicher verbunden, ähnlich wie in gezeigt. Eigenschaften wie Zentralität und Konnektivität werden meistens untersucht für den Fall, dass die Dichte asymptotisch gegen unendlich konvergiert. Dadurch werden Randfälle oft vernachlässigbar. In der realen Welt sind die Netzwerke aber endlich, auch wenn sie sehr dicht werden können und Randfälle haben einen Einfluss auf die Konnektivität. Tatsächlich wurde gezeigt, dass die Konnektivität, mit einer exponentiellen Verbindungsfunktion, stark beeinflusst wird durch Randeffekte, da Knoten nahe der Grenze der Domäne weniger wahrscheinlich mit den Knoten in der Masse verbunden werden. Daher kann volle Konnektivität ausgedrückt werden durch eine Summe an Beiträgen aus der Masse und von den geometrischen Grenzen. Eine allgemeinere Analyse der Verbindungsfunktionen in drahtlosen Netzwerken hat gezeigt, dass die Wahrscheinlichkeit für volle Konnektivität approximiert werden kann durch die Momente der Verbindungsfunktion und der Geometrie der Domäne.