[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/wiki20\/2021\/01\/22\/zufalliger-geometrischer-graph-wikipedia\/#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/wiki20\/2021\/01\/22\/zufalliger-geometrischer-graph-wikipedia\/","headline":"Zuf\u00e4lliger geometrischer Graph – Wikipedia","name":"Zuf\u00e4lliger geometrischer Graph – Wikipedia","description":"before-content-x4 In der Graphentheorie a zuf\u00e4lliger geometrischer Graph ((RGG) ist das mathematisch einfachste r\u00e4umliche Netzwerk, n\u00e4mlich ein ungerichteter Graph, der","datePublished":"2021-01-22","dateModified":"2021-01-22","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/wiki20\/author\/lordneo\/#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/wiki20\/author\/lordneo\/","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/thumb\/f\/fd\/Random_Geometric_Graph.gif\/300px-Random_Geometric_Graph.gif","url":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/thumb\/f\/fd\/Random_Geometric_Graph.gif\/300px-Random_Geometric_Graph.gif","height":"300","width":"300"},"url":"https:\/\/wiki.edu.vn\/wiki20\/2021\/01\/22\/zufalliger-geometrischer-graph-wikipedia\/","wordCount":13207,"articleBody":"     (adsbygoogle = window.adsbygoogle || []).push({});before-content-x4In der Graphentheorie a zuf\u00e4lliger geometrischer Graph ((RGG) ist das mathematisch einfachste r\u00e4umliche Netzwerk, n\u00e4mlich ein ungerichteter Graph, der durch zuf\u00e4lliges Platzieren erstellt wird N. Knoten in einem bestimmten metrischen Raum (gem\u00e4\u00df 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.       (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4Zuf\u00e4llige geometrische Graphen \u00e4hneln in vielerlei Hinsicht realen menschlichen sozialen Netzwerken.  Zum Beispiel demonstrieren sie spontan die Community-Struktur – Cluster von Knoten mit hoher Modularit\u00e4t.  Andere Algorithmen zur Erzeugung zuf\u00e4lliger Graphen, wie sie beispielsweise mit dem Erd\u0151s-R\u00e9nyi-Modell oder dem Barab\u00e1si-Albert-Modell (BA) erstellt wurden, erzeugen diese Art von Struktur nicht.  Dar\u00fcber hinaus zeigen zuf\u00e4llige geometrische Diagramme die Gradassortativit\u00e4t entsprechend ihrer r\u00e4umlichen 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\u00fcber hinaus werden Benchmarks f\u00fcr (externe) Graph-Algorithmen durchgef\u00fchrt.Table of Contents       (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4Definition[edit]Algorithmen[edit]Naiver Algorithmus[edit]Pseudocode[edit]Verteilte Algorithmen[edit]Holtgrewe et al.[edit]Funke et al.[edit]Eigenschaften[edit]Isolierte Eckpunkte und Konnektivit\u00e4t[edit]Hamiltonicity[edit]Clustering-Koeffizient[edit]Verallgemeinerte zuf\u00e4llige geometrische Graphen[edit]\u00dcbersicht einiger Ergebnisse f\u00fcr Soft RGG[edit]Verweise[edit]Definition[edit]  Die Erzeugung eines zuf\u00e4lligen geometrischen Graphen f\u00fcr verschiedene Konnektivit\u00e4tsparameter r.Lassen Sie im Folgenden  G = (V., E.) bezeichnen einen ungerichteten Graphen mit einer Reihe von Eckpunkten V. und eine Reihe von Kanten E \u2286 V \u00d7 V..  Die eingestellten Gr\u00f6\u00dfen sind mit gekennzeichnet |V.|  = n und |E.|  = m.  Wenn nicht anders angegeben, zus\u00e4tzlich der metrische Raum [0,1)d with the euclidean distance is considered, i.e. for any points x,y\u2208[0,1)d{displaystyle x,yin [0,1)^{d}} the euclidean distance of x and y is defined as       (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4d(x,y)=||x\u2212y||2=\u2211i=1d(xi\u2212yi)2{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 \u2208 V. sind nur dann verbunden, wenn ihr Abstand kleiner als ein zuvor angegebener Parameter ist r \u2208 (0,1), ohne Schleifen.  Also die Parameter r und n ein RGG vollst\u00e4ndig charakterisieren.Algorithmen[edit]Naiver Algorithmus[edit]Der naive Ansatz besteht darin, den Abstand jedes Scheitelpunkts zu jedem anderen Scheitelpunkt zu berechnen.  Wie es gibt n((n– –1)2{ textstyle { frac {n (n-1)} {2}}}M\u00f6gliche Verbindungen, die \u00fcberpr\u00fcft werden, ist die zeitliche Komplexit\u00e4t des naiven Algorithmus \u0398((n2){ textstyle  Theta (n ^ {2})}.  Die Abtastwerte werden unter Verwendung eines Zufallszahlengenerators (RNG) aktiviert [0,1)d{displaystyle [0,1)^{d}}. Practically, one can implement this using d random number generators on [0,1){displaystyle [0,1)}, one RNG for every dimension.Pseudocode[edit]V\u00a0:= generateSamples(n)  \/\/ Generates n samples in the unit cube.for each p \u2208 V do    for each q \u2208 V{p} do        if distance(p, q) \u2264 r then            addConnection(p, q) \/\/ Add the edge (p, q) to the edge data structure.        end if    end forend forDa dieser Algorithmus nicht skalierbar ist (jeder Scheitelpunkt ben\u00f6tigt Informationen von jedem anderen Scheitelpunkt), haben Holtgrewe et al.  und Funke et al.  haben neue Algorithmen f\u00fcr dieses Problem eingef\u00fchrt.Verteilte Algorithmen[edit]Holtgrewe et al.[edit]Dieser von Holtgrewe et al. Vorgeschlagene Algorithmus war der erste verteilte RGG-Generatoralgorithmus f\u00fcr Dimension 2.[4]  Es unterteilt das Einheitsquadrat in gleich gro\u00dfe Zellen mit einer Seitenl\u00e4nge von mindestens r{ displaystyle r}.  F\u00fcr eine bestimmte Anzahl P.=p2{ displaystyle P = p ^ {2}}von Prozessoren ist jeder Prozessor zugeordnet kp\u00d7kp{ textstyle {k  over p}  times {k  over p}}Zellen, wo k=\u230a1\/.r\u230b.{ textstyle k =  left  lfloor {1 \/ r}  right  rfloor.}Der Einfachheit halber P.{ textstyle P}wird als quadratische Zahl angenommen, dies kann jedoch auf eine beliebige Anzahl von Prozessoren verallgemeinert werden.  Jeder Prozessor generiert dann nP.{ textstyle { frac {n} {P}}}Eckpunkte, die dann an ihre jeweiligen Eigent\u00fcmer verteilt werden.  Dann werden die Eckpunkte nach der Zellennummer sortiert, in die sie fallen, beispielsweise mit Quicksort.  Als n\u00e4chstes sendet jeder Prozessor seinen benachbarten Prozessoren die Informationen \u00fcber die Eckpunkte in den Randzellen, so dass jede Verarbeitungseinheit die Kanten in ihrer Partition unabh\u00e4ngig von den anderen Einheiten berechnen kann.  Die erwartete Laufzeit ist \u00d6((nP.Log\u2061nP.){ textstyle O ({ frac {n} {P}}  log { frac {n} {P}})}.  Eine Obergrenze f\u00fcr die Kommunikationskosten dieses Algorithmus ist gegeben durch T.einll– –t\u00d6– –einll((n\/.P.,P.)+T.einll– –t\u00d6– –einll((1,P.)+T.p\u00d6ichnt– –t\u00d6– –p\u00d6ichnt((n\/.((k\u22c5P.)+2){ Anzeigestil T_ {Alles zu Alles} (n \/ P, P) + T_ {Alles zu Alles} (1, P) + T_ {Punkt zu Punkt} (n \/ (k  cdot {P. }) + 2)}, wo T.einll– –t\u00d6– –einll((l,c){ displaystyle T_ {all-to-all} (l, c)}bezeichnet die Zeit f\u00fcr eine Gesamtkommunikation mit Nachrichten von L\u00e4nge l Bits zu c Kommunikationspartner. T.p\u00d6ichnt– –t\u00d6– –p\u00d6ichnt((l){ displaystyle T_ {Punkt-zu-Punkt} (l)}ist die Zeit, die f\u00fcr eine Punkt-zu-Punkt-Kommunikation f\u00fcr eine Nachricht von L\u00e4nge ben\u00f6tigt wird l Bits.Da dieser Algorithmus nicht kommunikationsfrei ist, haben Funke et al.  vorgeschlagen[4]  Ein skalierbarer verteilter RGG-Generator f\u00fcr h\u00f6here Dimensionen, der ohne Kommunikation zwischen den Verarbeitungseinheiten funktioniert.Funke et al.[edit]Der in diesem Algorithmus verwendete Ansatz[4]  \u00e4hnelt dem Ansatz in Holtgrewe: Teilen Sie den Einheitsw\u00fcrfel in gleich gro\u00dfe St\u00fccke mit einer Seitenl\u00e4nge von mindestens r.  Also rein d = 2 Dies sind Quadrate in d = 3 das sind W\u00fcrfel.  Da kann h\u00f6chstens passen \u230a1\/.r\u230b{ textstyle { left  lfloor {1 \/ r}  right  rfloor}}  Chunks pro Dimension, die Anzahl der Chunks ist begrenzt \u230a1\/.r\u230bd{ textstyle { left  lfloor {1 \/ r}  right  rfloor} ^ {d}}.  Nach wie vor ist jeder Prozessor zugeordnet \u230a1\/.r\u230bdP.{ textstyle { left  lfloor {1 \/ r}  right  rfloor} ^ {d}  over P}Chunks, f\u00fcr die die Eckpunkte generiert werden.  Um einen kommunikationsfreien Prozess zu erreichen, erzeugt jeder Prozessor dann die gleichen Eckpunkte in den benachbarten Bl\u00f6cken, 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\u00fcr Dimension 3 haben Funke et al.  zeigte, dass die erwartete Laufzeit ist \u00d6((m+nP.+Log\u2061P.){ textstyle O ({ frac {m + n} {P}} +  log {P})}ohne Kosten f\u00fcr die Kommunikation zwischen Verarbeitungseinheiten.Eigenschaften[edit]Isolierte Eckpunkte und Konnektivit\u00e4t[edit]Die Wahrscheinlichkeit, dass ein einzelner Scheitelpunkt in einem RGG isoliert wird, betr\u00e4gt ((1– –\u03c0r2)n– –1{ textstyle (1-  pi r ^ {2}) ^ {n-1}}.[5]  Lassen X.{ textstyle X}  sei die Zufallsvariable, die z\u00e4hlt, wie viele Eckpunkte isoliert sind.  Dann der erwartete Wert von X.{ textstyle X}ist E.((X.)=n((1– –\u03c0r2)n– –1=ne– –\u03c0r2n– –\u00d6((r4n){ textstyle E (X) = n (1-  pi r ^ {2}) ^ {n-1} = ne ^ {-  pi r ^ {2} n} -O (r ^ {4} n) }}.  Der Begriff \u03bc=ne– –\u03c0r2n{ textstyle  mu = ne ^ {-  pi r ^ {2} n}}bietet Informationen zur Konnektivit\u00e4t des RGG.  Zum \u03bc\u27f60{ textstyle  mu  longrightarrow 0}ist die RGG asymptotisch fast sicher verbunden.  Zum \u03bc\u27f6\u221e{ displaystyle  mu  longrightarrow  infty}ist die RGG asymptotisch fast sicher getrennt.  Und f\u00fcr \u03bc=\u0398((1){ textstyle  mu =  Theta (1)}hat die RGG eine riesige Komponente, die mehr als abdeckt n2{ textstyle { frac {n} {2}}}Eckpunkte und X.{ displaystyle X}  ist Poisson mit Parameter verteilt \u03bc{ displaystyle  mu}.  Daraus folgt, dass wenn \u03bc=\u0398((1){ textstyle  mu =  Theta (1)}ist die Wahrscheinlichkeit, dass das RGG verbunden ist P.[X=0]\u223ce– –\u03bc{ textstyle P.[X=0] sim e ^ {-  mu}}und die Wahrscheinlichkeit, dass das RGG nicht verbunden ist, ist "},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/wiki20\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/wiki20\/2021\/01\/22\/zufalliger-geometrischer-graph-wikipedia\/#breadcrumbitem","name":"Zuf\u00e4lliger geometrischer Graph – Wikipedia"}}]}]