Zufälliger geometrischer Graph – Wikipedia

In der Graphentheorie a zufälliger geometrischer Graph ((RGG) ist das mathematisch einfachste räumliche Netzwerk, nämlich ein ungerichteter Graph, der durch zufälliges Platzieren erstellt wird N. Knoten in einem bestimmten metrischen Raum (gemäß einer bestimmten Wahrscheinlichkeitsverteilung) und zwei Knoten durch eine Verbindung verbinden, wenn und nur wenn ihre Entfernung in einem bestimmten Bereich liegt, z. B. kleiner als ein bestimmter Nachbarschaftsradius; r.

Zufällige geometrische Graphen ähneln in vielerlei Hinsicht realen menschlichen sozialen Netzwerken. Zum Beispiel demonstrieren sie spontan die Community-Struktur – Cluster von Knoten mit hoher Modularität. Andere Algorithmen zur Erzeugung zufälliger Graphen, wie sie beispielsweise mit dem Erdős-Rényi-Modell oder dem Barabási-Albert-Modell (BA) erstellt wurden, erzeugen diese Art von Struktur nicht. Darüber hinaus zeigen zufällige geometrische Diagramme die Gradassortativität entsprechend ihrer räumlichen Dimension an:^[1] “Beliebt” Knoten (solche mit vielen Links) sind besonders wahrscheinlich mit anderen beliebten Knoten verbunden.

Eine reale Anwendung von RGGs ist die Modellierung von Ad-hoc-Netzwerken.^[2] Darüber hinaus werden Benchmarks für (externe) Graph-Algorithmen durchgeführt.

Definition[edit]

Lassen Sie im Folgenden G = (V., E.) bezeichnen einen ungerichteten Graphen mit einer Reihe von Eckpunkten V. und eine Reihe von Kanten E ⊆ V × V.. Die eingestellten Größen sind mit gekennzeichnet |V.| = n und |E.| = m. Wenn nicht anders angegeben, zusätzlich der metrische Raum [0,1)^d with the euclidean distance is considered, i.e. for any points

${displaystyle x,yin [0,1)^{d}}$

the euclidean distance of x and y is defined as

after-content-x4

${displaystyle d(x,y)=||x-y||_{2}={sqrt {sum _{i=1}^{d}(x_{i}-y_{i})^{2}}}}$

.

A random geometric graph (RGG) is an undirected geometric graph with nodes randomly sampled from the uniform distribution of the underlying space [0,1)^d.^[3] Zwei Eckpunkte p, q ∈ V. sind nur dann verbunden, wenn ihr Abstand kleiner als ein zuvor angegebener Parameter ist r ∈ (0,1), ohne Schleifen. Also die Parameter r und n ein RGG vollständig charakterisieren.

Algorithmen[edit]

Naiver Algorithmus[edit]

Der naive Ansatz besteht darin, den Abstand jedes Scheitelpunkts zu jedem anderen Scheitelpunkt zu berechnen. Wie es gibt

${ textstyle { frac {n (n-1)} {2}}}$

Mögliche Verbindungen, die überprüft werden, ist die zeitliche Komplexität des naiven Algorithmus

${ textstyle Theta (n ^ {2})}$

. Die Abtastwerte werden unter Verwendung eines Zufallszahlengenerators (RNG) aktiviert

${displaystyle [0,1)^{d}}$

. Practically, one can implement this using d random number generators on

${displaystyle [0,1)}$

, one RNG for every dimension.

Pseudocode[edit]

V := generateSamples(n)  // Generates n samples in the unit cube.
for each p ∈ V do
    for each q ∈ V{p} do
        if distance(p, q) ≤ r then
            addConnection(p, q) // Add the edge (p, q) to the edge data structure.
        end if
    end for
end for

Da dieser Algorithmus nicht skalierbar ist (jeder Scheitelpunkt benötigt Informationen von jedem anderen Scheitelpunkt), haben Holtgrewe et al. und Funke et al. haben neue Algorithmen für dieses Problem eingeführt.

Verteilte Algorithmen[edit]

Holtgrewe et al.[edit]

Dieser von Holtgrewe et al. Vorgeschlagene Algorithmus war der erste verteilte RGG-Generatoralgorithmus für Dimension 2.^[4] Es unterteilt das Einheitsquadrat in gleich große Zellen mit einer Seitenlänge von mindestens

${ displaystyle r}$

. Für eine bestimmte Anzahl

${ displaystyle P = p ^ {2}}$

von Prozessoren ist jeder Prozessor zugeordnet

${ textstyle {k over p} times {k over p}}$

Zellen, wo

${ textstyle k = left lfloor {1 / r} right rfloor.}$

Der Einfachheit halber

${ textstyle P}$

wird als quadratische Zahl angenommen, dies kann jedoch auf eine beliebige Anzahl von Prozessoren verallgemeinert werden. Jeder Prozessor generiert dann

${ textstyle { frac {n} {P}}}$

Eckpunkte, die dann an ihre jeweiligen Eigentümer verteilt werden. Dann werden die Eckpunkte nach der Zellennummer sortiert, in die sie fallen, beispielsweise mit Quicksort. Als nächstes sendet jeder Prozessor seinen benachbarten Prozessoren die Informationen über die Eckpunkte in den Randzellen, so dass jede Verarbeitungseinheit die Kanten in ihrer Partition unabhängig von den anderen Einheiten berechnen kann. Die erwartete Laufzeit ist

${ textstyle O ({ frac {n} {P}} log { frac {n} {P}})}$

. Eine Obergrenze für die Kommunikationskosten dieses Algorithmus ist gegeben durch

${ Anzeigestil T_ {Alles zu Alles} (n / P, P) + T_ {Alles zu Alles} (1, P) + T_ {Punkt zu Punkt} (n / (k cdot {P. }) + 2)}$

, wo

${ displaystyle T_ {all-to-all} (l, c)}$

bezeichnet die Zeit für eine Gesamtkommunikation mit Nachrichten von Länge l Bits zu c Kommunikationspartner.

${ displaystyle T_ {Punkt-zu-Punkt} (l)}$

ist die Zeit, die für eine Punkt-zu-Punkt-Kommunikation für eine Nachricht von Länge benötigt wird l Bits.

Da dieser Algorithmus nicht kommunikationsfrei ist, haben Funke et al. vorgeschlagen^[4] Ein skalierbarer verteilter RGG-Generator für höhere Dimensionen, der ohne Kommunikation zwischen den Verarbeitungseinheiten funktioniert.

Funke et al.[edit]

Der in diesem Algorithmus verwendete Ansatz^[4] ähnelt dem Ansatz in Holtgrewe: Teilen Sie den Einheitswürfel in gleich große Stücke mit einer Seitenlänge von mindestens r. Also rein d = 2 Dies sind Quadrate in d = 3 das sind Würfel. Da kann höchstens passen

${ textstyle { left lfloor {1 / r} right rfloor}}$

Chunks pro Dimension, die Anzahl der Chunks ist begrenzt

${ textstyle { left lfloor {1 / r} right rfloor} ^ {d}}$

. Nach wie vor ist jeder Prozessor zugeordnet

${ textstyle { left lfloor {1 / r} right rfloor} ^ {d} over P}$

Chunks, für die die Eckpunkte generiert werden. Um einen kommunikationsfreien Prozess zu erreichen, erzeugt jeder Prozessor dann die gleichen Eckpunkte in den benachbarten Blöcken, indem er die Pseudozufallung von gesetzten Hash-Funktionen ausnutzt. Auf diese Weise berechnet jeder Prozessor dieselben Scheitelpunkte und es besteht keine Notwendigkeit, Scheitelpunktinformationen auszutauschen.

Für Dimension 3 haben Funke et al. zeigte, dass die erwartete Laufzeit ist

${ textstyle O ({ frac {m + n} {P}} + log {P})}$

ohne Kosten für die Kommunikation zwischen Verarbeitungseinheiten.

Eigenschaften[edit]

Isolierte Eckpunkte und Konnektivität[edit]

Die Wahrscheinlichkeit, dass ein einzelner Scheitelpunkt in einem RGG isoliert wird, beträgt

${ textstyle (1- pi r ^ {2}) ^ {n-1}}$

.^[5] Lassen

${ textstyle X}$

sei die Zufallsvariable, die zählt, wie viele Eckpunkte isoliert sind. Dann der erwartete Wert von

${ textstyle X}$

ist

${ textstyle E (X) = n (1- pi r ^ {2}) ^ {n-1} = ne ^ {- pi r ^ {2} n} -O (r ^ {4} n) }}$

. Der Begriff

${ textstyle mu = ne ^ {- pi r ^ {2} n}}$

bietet Informationen zur Konnektivität des RGG. Zum

${ textstyle mu longrightarrow 0}$

ist die RGG asymptotisch fast sicher verbunden. Zum

${ displaystyle mu longrightarrow infty}$

ist die RGG asymptotisch fast sicher getrennt. Und für

${ textstyle mu = Theta (1)}$

hat die RGG eine riesige Komponente, die mehr als abdeckt

${ textstyle { frac {n} {2}}}$

Eckpunkte und

${ displaystyle X}$

ist Poisson mit Parameter verteilt

${ displaystyle mu}$

. Daraus folgt, dass wenn

${ textstyle mu = Theta (1)}$

ist die Wahrscheinlichkeit, dass das RGG verbunden ist

${ textstyle P.[X=0] sim e ^ {- mu}}$

und die Wahrscheinlichkeit, dass das RGG nicht verbunden ist, ist

${ textstyle P.[X>0] sim 1-e ^ {- mu}}$

${ textstyle l_ {p}}$

-Norm (

${ textstyle 1 leq p leq infty}$

) und für eine beliebige Anzahl von Dimensionen

${ displaystyle d> 2}$

${ textstyle r sim ({ ln (n) über alpha _ {p, d} n}) ^ {1 über d}}$

mit konstant

${ displaystyle alpha _ {p, d}}$

. Im Sonderfall eines zweidimensionalen Raumes und der euklidischen Norm (

${ displaystyle d = 2}$

und

${ displaystyle p = 2}$

) Dies ergibt

${ textstyle r sim { sqrt { ln (n) over pi n}}}$

.

Hamiltonicity[edit]

Es hat sich gezeigt, dass im zweidimensionalen Fall die Schwelle

${ textstyle r sim { sqrt { ln (n) over pi n}}}$

liefert auch Informationen über die Existenz eines Hamilton-Zyklus (Hamilton-Pfad).^[6] Für jeden

${ displaystyle epsilon> 0}$

${ textstyle r sim { sqrt { ln (n) over ( pi + epsilon) n}}}$

, dann hat die RGG asymptotisch fast sicher keinen Hamilton-Zyklus und wenn

${ textstyle r sim { sqrt { ln (n) over ( pi – epsilon) n}}}$

für jeden

${ textstyle epsilon> 0}$

Clustering-Koeffizient[edit]

Der Clustering-Koeffizient von RGGs hängt nur von der Dimension ab d des zugrunde liegenden Raumes [0,1)^d. The clustering coefficient is ^[7]

${ textstyle C_ {d} = 1-H_ {d} (1)}$

für gerade

${ displaystyle d}$

und

${ textstyle C_ {d} = {3 over 2} -H_ {d} ({1 over 2})}$

für ungerade

${ displaystyle d}$

wo

Für große

${ displaystyle d}$

Dies vereinfacht zu

${ displaystyle C_ {d} sim 3 { sqrt {2 over pi d}} ({3 over 4}) ^ {d + 1 over 2}}$

.

Verallgemeinerte zufällige geometrische Graphen[edit]

1988 Waxman ^[8] verallgemeinerte das Standard-RGG durch Einführung einer probabilistischen Verbindungsfunktion im Gegensatz zu der von Gilbert vorgeschlagenen deterministischen. Das von Waxman eingeführte Beispiel war ein gestrecktes Exponential mit zwei Knoten

${ displaystyle i}$

und

${ displaystyle j}$

verbinden mit der Wahrscheinlichkeit gegeben durch

${ textstyle H_ {ij} = beta e ^ {- {r_ {ij} über r_ {0}}}}$

wo

${ displaystyle r_ {ij}}$

ist die euklidische Trennung und

${ displaystyle beta}$

,

${ displaystyle r_ {0}}$

sind vom System bestimmte Parameter. Diese Art von RGG mit probabilistischer Verbindungsfunktion wird häufig als weicher zufälliger geometrischer Graph bezeichnet, der nun zwei Zufallsquellen aufweist. die Position von Knoten (Eckpunkten) und die Bildung von Verbindungen (Kanten). Diese Verbindungsfunktion wurde in der Literatur weiter verallgemeinert

${ textstyle H_ {ij} = beta e ^ {- ({r_ {ij} über r_ {0}}) ^ { eta}}}$

Dies wird häufig verwendet, um drahtlose Netzwerke ohne Interferenz zu untersuchen. Der Parameter

${ displaystyle eta}$

stellt dar, wie das Signal mit der Entfernung abfällt, wann

${ displaystyle eta = 2}$

ist freier Speicherplatz,

${ displaystyle eta> 2}$

${ displaystyle eta <2}$

modelliert stark reflektierende Umgebungen. Wir bemerken das für

${ displaystyle eta = 1}$

ist das Waxman-Modell, während als

${ displaystyle eta to infty}$

und

${ textstyle beta = 1}$

Wir haben die Standard-RGG. Intuitiv modellieren diese Art von Verbindungsfunktionen, wie die Wahrscheinlichkeit, dass eine Verbindung hergestellt wird, mit der Entfernung abnimmt.

Übersicht einiger Ergebnisse für Soft RGG[edit]

In der hohen Dichtegrenze für ein Netzwerk mit exponentieller Verbindungsfunktion ist die Anzahl der isolierten Knoten Poisson-verteilt, und das resultierende Netzwerk enthält nur eine eindeutige Riesenkomponente und isolierte Knoten.^[9] Wenn sichergestellt wird, dass keine isolierten Knoten vorhanden sind, ist das Netzwerk im dichten Bereich vollständig verbunden. ähnlich den Ergebnissen in ^[10] für das Plattenmodell. Oft sind die Eigenschaften dieser Netzwerke wie zwischen Zentralität ^[11] und Konnektivität ^[9] werden im Grenzfall als Dichte untersucht

${ displaystyle to infty}$

was oft bedeutet, dass Randeffekte vernachlässigbar werden. Im wirklichen Leben, in dem Netzwerke endlich sind, obwohl sie immer noch extrem dicht sein können, wirken sich Randeffekte auf die vollständige Konnektivität aus. eigentlich ^[12] zeigten, dass die vollständige Konnektivität mit einer exponentiellen Verbindungsfunktion stark von Randeffekten beeinflusst wird, da Knoten in der Nähe der Ecke / Fläche einer Domäne weniger wahrscheinlich eine Verbindung herstellen als Knoten in der Masse. Infolgedessen kann die vollständige Konnektivität als Summe der Beiträge aus der Masse und den Geometriegrenzen ausgedrückt werden. Eine allgemeinere Analyse der Verbindungsfunktionen in drahtlosen Netzwerken hat gezeigt, dass die Wahrscheinlichkeit einer vollständigen Konnektivität durch einige Momente der Verbindungsfunktion und der Bereichsgeometrie gut angenähert werden kann.^[13]

Verweise[edit]