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
the euclidean distance of x and y is defined as
- .
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
Mögliche Verbindungen, die überprüft werden, ist die zeitliche Komplexität des naiven Algorithmus
. Die Abtastwerte werden unter Verwendung eines Zufallszahlengenerators (RNG) aktiviert
. Practically, one can implement this using d random number generators on
, 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
. Für eine bestimmte Anzahl
von Prozessoren ist jeder Prozessor zugeordnet
Zellen, wo
Der Einfachheit halber
wird als quadratische Zahl angenommen, dies kann jedoch auf eine beliebige Anzahl von Prozessoren verallgemeinert werden. Jeder Prozessor generiert dann
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
. Eine Obergrenze für die Kommunikationskosten dieses Algorithmus ist gegeben durch
, wo
bezeichnet die Zeit für eine Gesamtkommunikation mit Nachrichten von Länge l Bits zu c Kommunikationspartner.
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
Chunks pro Dimension, die Anzahl der Chunks ist begrenzt
. Nach wie vor ist jeder Prozessor zugeordnet
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
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
.[5] Lassen
sei die Zufallsvariable, die zählt, wie viele Eckpunkte isoliert sind. Dann der erwartete Wert von
ist
. Der Begriff
bietet Informationen zur Konnektivität des RGG. Zum
ist die RGG asymptotisch fast sicher verbunden. Zum
ist die RGG asymptotisch fast sicher getrennt. Und für
hat die RGG eine riesige Komponente, die mehr als abdeckt
Eckpunkte und
ist Poisson mit Parameter verteilt
. Daraus folgt, dass wenn
ist die Wahrscheinlichkeit, dass das RGG verbunden ist
und die Wahrscheinlichkeit, dass das RGG nicht verbunden ist, ist
-Norm (
) und für eine beliebige Anzahl von Dimensionen
mit konstant
. Im Sonderfall eines zweidimensionalen Raumes und der euklidischen Norm (
und
) Dies ergibt
.
Hamiltonicity[edit]
Es hat sich gezeigt, dass im zweidimensionalen Fall die Schwelle
liefert auch Informationen über die Existenz eines Hamilton-Zyklus (Hamilton-Pfad).[6] Für jeden
, dann hat die RGG asymptotisch fast sicher keinen Hamilton-Zyklus und wenn
für jeden
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]
für gerade
und
für ungerade
wo
Für große
Dies vereinfacht zu
.
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
und
verbinden mit der Wahrscheinlichkeit gegeben durch
wo
ist die euklidische Trennung und
,
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
Dies wird häufig verwendet, um drahtlose Netzwerke ohne Interferenz zu untersuchen. Der Parameter
stellt dar, wie das Signal mit der Entfernung abfällt, wann
ist freier Speicherplatz,
modelliert stark reflektierende Umgebungen. Wir bemerken das für
ist das Waxman-Modell, während als
und
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
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]
- ^ Antonioni, Alberto; Tomassini, Marco (28. September 2012). “Gradkorrelationen in zufälligen geometrischen Graphen”. Körperliche Überprüfung E.. 86 (3): 037101. arXiv:1207,2573. Bibcode:2012PhRvE..86c7101A. doi:10.1103 / PhysRevE.86.037101. PMID 23031054. S2CID 14750415.
- ^ Nekovee, Maziar (28. Juni 2007). “Wurmepidemien in drahtlosen Ad-hoc-Netzwerken”. Neues Journal für Physik. 9 (6): 189. arXiv:0707.2293. Bibcode:2007NJPh …. 9..189N. doi:10.1088 / 1367-2630 / 9/6/189. S2CID 203944.
- ^ Penrose, Mathew. (2003). Zufällige geometrische Graphen. Oxford: Oxford University Press. ISBN 0198506260. OCLC 51316118.
- ^ ein b c von Looz, Moritz; Strash, Darren; Schulz, Christian; Penschuck, Manuel; Sanders, Peter; Meyer, Ulrich; Lamm, Sebastian; Funke, Daniel (2017-10-20). “Kommunikationsfreie, massiv verteilte Graphengenerierung”. arXiv:1710.07565v3 [cs.DC].
- ^ Perez, Xavier; Mitsche, Dieter; Diaz, Josep (2007-02-13). “Dynamische zufällige geometrische Diagramme”. arXiv:cs / 0702074. Bibcode:2007cs …….. 2074D.
- ^ Perez, X.; Mitsche, D.; Diaz, J. (07.07.2006). “Scharfer Schwellenwert für die Hamiltonizität zufälliger geometrischer Graphen”. arXiv:cs / 0607023. Bibcode:2006cs …….. 7023D.
- ^ Christensen, Michael; Dall, Jesper (2002-03-01). “Zufällige geometrische Diagramme”. Körperliche Überprüfung E.. 66 (1 Pt 2): 016121. arXiv:cond-mat / 0203026. Bibcode:2002PhRvE..66a6121D. doi:10.1103 / PhysRevE.66.016121. PMID 12241440. S2CID 15193516.
- ^ Waxman, BM (1988). “Routing von Mehrpunktverbindungen”. IEEE Journal zu ausgewählten Bereichen der Kommunikation. 6 (9): 1617–1622. doi:10.1109 / 49.12889.
- ^ ein b Mao, G; Anderson, BD (2013). “Konnektivität großer drahtloser Netzwerke unter einem allgemeinen Verbindungsmodell”. IEEE-Transaktionen zur Informationstheorie. 59 (3): 1761–1772. doi:10.1109 / tit.2012.2228894. S2CID 3027610.
- ^ Penrose, Mathew D (1997). “Die längste Kante des zufälligen minimalen Spannbaums”. Die Annalen der angewandten Wahrscheinlichkeit: 340361.
- ^ Giles, Alexander P.; Georgiou, Orestis; Dettmann, Carl P. (2015). “Zwischenzentralität in dichten zufälligen geometrischen Netzwerken”. Internationale IEEE-Konferenz für Kommunikation 2015 (ICC). S. 6450–6455. arXiv:1410.8521. Bibcode:2014arXiv1410.8521K. doi:10.1109 / ICC.2015.7249352. ISBN 978-1-4673-6432-4. S2CID 928409.
- ^ Coon, J; Dettmann, CP; Georgiou, O (2012). “Volle Konnektivität: Ecken, Kanten und Flächen”. Zeitschrift für Statistische Physik. 147 (4): 758–778. arXiv:1201.3123. Bibcode:2012JSP … 147..758C. doi:10.1007 / s10955-012-0493-y. S2CID 18794396.
- ^ Dettmann, CP; Georgiou, O (2016). “Zufällige geometrische Graphen mit allgemeinen Verbindungsfunktionen”. Körperliche Überprüfung E.. 93 (3): 032313. arXiv:1411.3617. Bibcode:2016PhRvE..93c2313D. doi:10.1103 / physreve.93.032313. PMID 27078372.
Recent Comments