Ein zufälliger geometrischer Graph ist ein ungerichteter geometrischer Graph mit Knoten gleichverteilt auf dem zugrundeliegenden Raum .[1] Zwei Knoten sind genau dann verbunden, wenn ihre Distanz geringer ist als ein zuvor spezifizierter Parameter .

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[2]. Außerdem können sie benutzt werden, um Benchmarks für (externe) Graphalgorithmen zu erstellen.

Definition

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

Im Folgenden bezeichnet   einen ungerichteten Graphen mit einer Knotenmenge   und einer Kantenmenge  . Die Knotenanzahl sei  , die Kantenanzahl  . Außerdem sind alle mathematischen Betrachtungen auf dem metrischen Raum  , falls nicht anders spezifiziert. Die dazugehörige Metrik ist der euklidische Abstand, also für beliebige Knoten   ist der euklidische Abstand definiert als  .

Für   und   wird ein zufälliger geometrischer Graph   generiert, indem   Knoten gleichverteilt auf   gezogen werden. Alle Knoten, deren euklidischer Abstand kleiner als   ist, werden durch eine Kante verbunden. Hierbei werden keine Schleifen betrachtet, da sonst jeder Knoten eine Schleife hätte. Damit charakterisieren die Parameter   und   einen zufälligen geometrischen Graph.

Algorithmen

Bearbeiten

Naiver Algorithmus

Bearbeiten

Die naive Vorgehensweise ist es, für jeden Knoten die Distanz zu jedem anderen Knoten zu berechnen. Da es   mögliche Verbindungen gibt, ist die Zeitkomplexität  . Die Knoten werden mittels eines Zufallszahlengenerators auf   generiert. Praktisch kann man dies mit   Zufallszahlengeneratoren auf  , 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

Bearbeiten

Holtgrewe et al.

Bearbeiten

Dieser Algorithmus, welcher von Holtgrewe et al. vorgeschlagen wurde, war der erste verteilte Generator für zufällige geometrische Graphen für Dimension 2.[3] Das Einheitsquadrat wird hierbei in gleich große Quadrate (Zellen) mit einer Seitenlänge von mindestens  partitioniert. Für eine gegebene Anzahl   von Prozessoren wird jedem Prozessor   Zellen zugewiesen. Hier ist   die Anzahl der Zellen der Größe   in einer Dimension. Der Einfachheit halber wird   als Quadratzahl angenommen, der Algorithmus kann aber für eine beliebige Anzahl an Prozessoren adaptiert werden. Jeder Prozessor generiert   Knoten im Einheitsquadrat, insgesamt werden also die benötigten  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  haben.

Die erwartete Laufzeit ist  . Eine obere Schranke der Kommunikationskosten ist gegeben durch  . Hierbei ist   die Zeit, die für eine alle-zu-alle Kommunikation mit Nachrichten der Länge l bit zu   Kommunikationspartnern.   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.

Bearbeiten

Die Vorgehensweise in diesem Algorithmus ist ähnlich zu dem Vorgehen von Holtgrewe:[3] Man teilt den Einheitswürfel in gleich große Chunks der Seitenlänge   oder größer. In der Dimension 2 sind es also Quadrate, in Dimension 3 Würfel. Da maximal   Chunks in jede Dimension passen, ist die Anzahl der Chunks beschränkt durch  . Jedem der   Prozessoren werden   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   ist, ohne zusätzlichen Kosten für Kommunikation.[3]

Eigenschaften

Bearbeiten

Isolierte Knoten und Konnektivität

Bearbeiten

Die Wahrscheinlichkeit, dass ein einzelner Knoten in einem zufälligen geometrischen Graphen isoliert ist, ist  [4]. Sei  die Zufallsvariable, die zählt wie viele Knoten isoliert sind, dann ist der Erwartungswert . Der Term  enthält Informationen über die Konnektivität des zufälligen geometrischen Graphen. Für  ist der Graph asymptotisch fast sicher verbunden. Für  ist der Graph asymptotisch fast sicher nicht verbunden. Und für  besitzt der Graph eine riesige Komponente mit mehr als  Knoten und  ist Poisson verteilt mit Parameter  . Es folgt, dass falls  die Wahrscheinlichkeit, dass der Graph verbunden ist,  ist und die Wahrscheinlichkeit, dass er nicht verbunden ist, ist  . Für jede  -Norm ( ) und für jede Anzahl an Dimensionen  hat der Graph eine scharfe Grenze für die Konnektivität bei  mit einer Konstante  . Im Spezialfall des zweidimensionalen Raumes und der euklidischen Norm (  and  ) ist  .

Hamiltonizität

Bearbeiten

Es wurde gezeigt, dass im zweidimensionalen Fall der Schwellwert  auch Aufschluss über die Existenz eines Hamiltonischen Kreises gibt[5]. Für jedes  , hat der Graph asymptotisch fast sicher einen Hamiltonischen Kreis falls  und der Graph hat asymptotisch fast sicher keinen Hamiltonischen Kreis falls  .

Clusterkoeffizient

Bearbeiten

Der Clusterkoeffizient des zufälligen geometrischen Graphen hängt ausschließlich von der Dimension   des zugrundeliegenden Raumes  ab. Der Clusterkoeffizient ist[6]  für gerade  und  für ungerade  . Hierbei ist  .

Für große  , vereinfacht sich der Clusterkoeffizient zu  .

Generalisierte zufällige geometrische Graphen

Bearbeiten

Waxman[7] hat 1988 den zufälligen geometrischen Graphen generalisiert, indem die durch   gegebene deterministische Verbindungsfunktion durch eine probabilistische Verbindungsfunktion ausgetauscht wird. Die von Waxman vorgestellte Variante war eine gestreckte Exponentialfunktion, bei der zwei Knoten  und  mit Wahrscheinlichkeit  verbunden werden, wobei  die euklidische Separation ist und  sowie  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  , welche oft benutzt wird, um drahtlose Netzwerke ohne Interferenz zu untersuchen. Der Parameter  gibt an, wie das Signal über die Distanz abfällt. Dabei entspricht  einem freien Raum und  entspricht gefüllteren Umgebungen wie eine Stadt ( wird als Modellierung für New York benutzt). Im Gegenzug entspricht  hoch reflektiven Umgebungen. Für  ergibt sich genau das Modell von Waxman und für  und  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

Bearbeiten

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.[8] Wird sichergestellt, dass kein Knoten isoliert ist, ist der Graph asymptotisch fast sicher verbunden, ähnlich wie in[9] gezeigt. Eigenschaften wie Zentralität[10] und Konnektivität[11] 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[12], 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.[13]

Einzelnachweise

Bearbeiten
  1. Mathew Penrose: Random geometric graphs. Oxford University Press, Oxford 2003, ISBN 0-19-850626-0.
  2. Maziar Nekovee: Worm Epidemics in Wireless Adhoc Networks. 16. Juli 2007, doi:10.1088/1367-2630/9/6/189, arxiv:0707.2293v1.
  3. a b c Moritz von Looz, Darren Strash, Christian Schulz, Manuel Penschuck, Peter Sanders, Ulrich Meyer, Sebastian Lamm, Daniel Funke: Communication-free Massively Distributed Graph Generation. 20. Oktober 2017, arxiv:1710.07565v3 (englisch).
  4. Xavier Perez, Dieter Mitsche, Josep Diaz: Dynamic Random Geometric Graphs. In: Dynamic Random Geometric Graphs. 13. Februar 2007, arxiv:cs/0702074v2 (englisch).
  5. X. Perez, D. Mitsche, J. Diaz: Sharp threshold for hamiltonicity of random geometric graphs. In: Sharp threshold for hamiltonicity of random geometric graphs. 7. Juli 2006, arxiv:cs/0607023v1 (englisch).
  6. Michael Christensen, Jesper Dall: Random Geometric Graphs. In: Random Geometric Graphs. 1. März 2002, doi:10.1103/PhysRevE.66.016121, arxiv:cond-mat/0203026v2 (englisch).
  7. B. M. Waxman: Routing of multipoint connections. In: IEEE Journal on Selected Areas in Communications. Band 6, Nr. 9, 1988, S. 1617–1622, doi:10.1109/49.12889.
  8. Mathew D G Mao, B. D. Anderson: Connectivity of large wireless networks under a general connection model. In: IEEE Transactions on Information. Band 59, Nr. 3, 2013, S. 1761–1772, doi:10.1109/tit.2012.2228894.
  9. Penrose: The longest edge of the random minimal spanning tree. In: The Annals of Applied Probability. 1997, S. 340361.
  10. A. P. Giles, O. Georgiou, C. P. Dettmann: Betweenness centrality in dense random geometric networks. In: IEEE International Conference on Communications. 2015, S. 6450–6455, doi:10.1109/ICC.2015.7249352, arxiv:1410.8521, bibcode:2014arXiv1410.8521K.
  11. G. Mao, B. D. Anderson: Connectivity of large wireless networks under a general connection model. In: IEEE Transactions on Information. Band 59, Nr. 3, 2013, S. 1761–1772, doi:10.1109/tit.2012.2228894.
  12. J. Coon, C. P. Dettmann, O. Georgiou: Full connectivity: corners, edges and faces. In: Journal of Statistical Physics. Band 147, Nr. 4, 2012, S. 758–778, doi:10.1007/s10955-012-0493-y, arxiv:1201.3123, bibcode:2012JSP...147..758C.
  13. C. P. Dettmann, O Georgiou: Random geometric graphs with general connection functions. In: Physical Review E. Band 93, Nr. 3, 2016, S. 032313, doi:10.1103/physreve.93.032313, PMID 27078372, arxiv:1411.3617, bibcode:2016PhRvE..93c2313D.