Losowy wykres geometryczny - Random geometric graph

Nauka o sieci
Teoria
Wykres Złożona sieć Zakażenie Mały świat Bez skalowania Struktura społeczności Przesiąkanie Ewolucja Sterowalność Rysowanie wykresu Kapitał społeczny Analiza linków Optymalizacja Wzajemność Zamknięcie Homofilia Przechodniość Preferencyjne przywiązanie Teoria równowagi Efekt sieci Wpływ społeczny
Typy sieci
Informacyjne (obliczeniowe) Telekomunikacja Transport Społeczny Współpraca naukowa Biologiczny Sztuczny neuron Współzależny Semantyczny Przestrzenny Zależność Pływ na chipie
Wykresy
Cechy Klika Składnik Ciąć Cykl Struktura danych Krawędź Pętla Sąsiedztwo Ścieżka Wierzchołek Lista sąsiedztwa  / matryca Lista incydentów  / matryca Rodzaje Dwustronny Kompletny Skierowany Hiper Wielo Losowy Ważony
Metryka Algorytmy
Centralność Stopień Motyw Grupowanie Rozkład stopni Assortatywność Dystans Modułowość Efektywność
Modele
Topologia Wykres losowy Erdős-Rényi Barabasi–Albert Model fitness Waty – Strogatz Wykładniczy losowy (ERGM) Losowa geometria (RGG) Hiperboliczny (HGN) Hierarchiczny Blok stochastyczny Maksymalna entropia Konfiguracja miękka Wskaźnik LFR Dynamika Sieć logiczna agent oparty Epidemia / SIR
Listy Kategorie
Tematy Oprogramowanie Naukowcy sieci Kategoria:Teoria sieci Kategoria: Teoria grafów
v T mi

W teorii wykres , A losowo wykres geometryczne ( RGG ) jest matematycznie najprostszym sieć przestrzenną , a mianowicie nieukierunkowane wykres wykonana losowo umieszczenie N węzłów w niektórych metryki przestrzeni (według określonego rozkładu prawdopodobieństwa) łączący dwa węzły przez połączenia , wtedy i tylko jeśli ich odległość mieści się w określonym zakresie, np. mniejsza niż pewien promień sąsiedztwa, r .

Losowe wykresy geometryczne pod wieloma względami przypominają prawdziwe ludzkie sieci społecznościowe. Na przykład spontanicznie demonstrują strukturę społeczności – klastry węzłów o wysokiej modułowości . Inne algorytmy generowania grafów losowych, takie jak te generowane przy użyciu modelu Erdősa-Rényiego lub modelu Barabási-Albert (BA) , nie tworzą tego typu struktury. Dodatkowo, losowe wykresy geometryczne wyświetlają assortatywność stopni zgodnie z ich wymiarem przestrzennym: „popularne” węzły (te z wieloma linkami) są szczególnie narażone na połączenie z innymi popularnymi węzłami.

Prawdziwym zastosowaniem RGG jest modelowanie sieci ad hoc . Ponadto są one wykorzystywane do wykonywania testów porównawczych dla (zewnętrznych) algorytmów grafowych.

Definicja

Dalej niech  G = ( V , E ) oznacza graf nieskierowany ze zbiorem wierzchołków V i zbiorem krawędzi E ⊆ V × V . Rozmiary zestawów są oznaczone | V | = n i | E | = m . Dodatkowo, jeśli nie zaznaczono inaczej, uwzględniana jest przestrzeń metryczna [0,1) ^d z odległością euklidesową , tj. dla dowolnych punktów odległość euklidesowa x i y jest zdefiniowana jako ${\ Displaystyle x, y \ w [0,1) ^ {d}}$

${\ Displaystyle d (x, y) = | | xy | | _ {2} = {\ sqrt {\ suma _ {i = 1} ^ {d} (x_ {i} -y_ {i}) ^ {2 }}}}$.

Losowo wykres geometryczne (RGG) jest nieukierunkowane geometryczny wykres z węzłami losowo wybranych z równomiernym rozkładem bazowego miejsca [0,1) ^d . Dwa wierzchołki p, q ∈ V są połączone wtedy i tylko wtedy, gdy ich odległość jest mniejsza niż wcześniej określony parametr r ∈ (0,1) , wyłączając wszelkie pętle . Tak więc parametry r i n w pełni charakteryzują RGG.

Algorytmy

Algorytm naiwny

Naiwnym podejściem jest obliczenie odległości każdego wierzchołka od każdego innego wierzchołka. Ponieważ istnieją możliwe połączenia, które są sprawdzane, złożoność czasowa algorytmu naiwnego wynosi . Próbki są generowane przy użyciu generatora liczb losowych (RNG) on . Praktycznie można to zaimplementować za pomocą d generatorów liczb losowych na , po jednym RNG dla każdego wymiaru. ${\textstyle {\frac {n(n-1)}{2}}}$${\textstyle \Theta (n^{2})}$${\ Displaystyle [0,1) ^ {d}}$${\ Displaystyle [0,1)}$

Pseudo kod

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

Ponieważ ten algorytm nie jest skalowalny (każdy wierzchołek potrzebuje informacji o każdym innym wierzchołku), Holtgrewe i in. oraz Funke i in. wprowadzili nowe algorytmy dla tego problemu.

Algorytmy rozproszone

Holtgrewe i in.

Algorytm ten, zaproponowany przez Holtgrewe i in., był pierwszym algorytmem rozproszonego generatora RGG dla wymiaru 2. Dzieli kwadrat jednostkowy na komórki o równych rozmiarach o długości boku co najmniej . Dla danej liczby procesorów każdemu procesorowi przypisuje się komórki, gdzie dla uproszczenia przyjmuje się liczbę kwadratową, ale można to uogólnić na dowolną liczbę procesorów. Każdy procesor generuje następnie wierzchołki, które są następnie dystrybuowane do odpowiednich właścicieli. Następnie wierzchołki są sortowane według numerów komórek, do których należą, na przykład za pomocą Quicksort . Następnie każdy procesor wysyła następnie do sąsiednich procesorów informacje o wierzchołkach w komórkach granicznych, tak że każda jednostka przetwarzania może obliczyć krawędzie w swoim podziale niezależnie od innych jednostek. Oczekiwany czas działania to . Górna granica kosztu komunikacji tego algorytmu jest podana przez , gdzie oznacza czas komunikacji typu „wszystko do wszystkich” z wiadomościami o długości l bitów do c partnerów komunikacji. to czas potrzebny na komunikację punkt-punkt dla wiadomości o długości l bitów. ${\ Displaystyle r}$${\ Displaystyle P = p ^ {2}}$${\textstyle {k \over p}\times {k \over p}}$${\textstyle k=\lewa\lpodłoga {1/r}\prawa\rpodłoga .}$${\textstyle P}$${\textstyle {\frac {n}{P}}}$${\textstyle O({\frac {n}{P}}\log {\frac {n}{P}})}$${\ Displaystyle T_ {wszyscy do wszystkich} (n / P, P) + T_ {wszyscy do wszystkich} (1, P) + T_ {od punktu do punktu} (n / (k \ cdot {P) })+2)}$${\ Displaystyle T_ {wszyscy do wszystkich} (l, c)}$${\ Displaystyle T_ {od punktu do punktu} (l)}$

Ponieważ ten algorytm nie jest wolny od komunikacji, Funke et al. zaproponował skalowalny rozproszony generator RGG dla większych wymiarów, który działa bez komunikacji między jednostkami przetwarzającymi.

Funke i in.

Podejście zastosowane w tym algorytmie jest podobne do podejścia w Holtgrewe: Podziel sześcian jednostkowy na równej wielkości kawałki o długości boku co najmniej r . Więc w d = 2 to będą kwadraty, w d = 3 to będą sześciany. Ponieważ na wymiar można zmieścić tylko większość porcji, liczba porcji jest ograniczona do . Tak jak poprzednio, do każdego procesora przypisane są porcje, dla których generuje wierzchołki. Aby osiągnąć proces wolny od komunikacji, każdy procesor generuje następnie te same wierzchołki w sąsiednich porcjach, wykorzystując pseudorandomizację zaszczepionych funkcji mieszających . W ten sposób każdy procesor oblicza te same wierzchołki i nie ma potrzeby wymiany informacji o wierzchołkach. ${\textstyle {\left\lpodłoga {1/r}\prawa\rpodłoga }}$${\textstyle {\left\lfloor {1/r}\right\rfloor }^{d}}$${\textstyle {\left\lfloor {1/r}\right\rfloor }^{d} \over P}$

Dla wymiaru 3 Funke i in. pokazał, że oczekiwany czas działania to , bez żadnych kosztów komunikacji między jednostkami przetwarzającymi. ${\textstyle O({\frac {m+n}{P}}+\log {P})}$

Nieruchomości

Izolowane wierzchołki i łączność

Prawdopodobieństwo wyizolowania pojedynczego wierzchołka w RGG wynosi . Niech będzie zmienną losową zliczającą ile wierzchołków jest izolowanych. Wtedy oczekiwana wartość to . Termin ten dostarcza informacji o łączności RGG. Dla , RGG jest asymptotycznie prawie na pewno połączony. Dla , RGG jest asymptotycznie prawie na pewno odłączone. I dla , RGG ma gigantyczny składnik , który obejmuje więcej niż wierzchołki i jest rozłożony Poissona z parametrami . Wynika z tego , że jeżeli , prawdopodobieństwo, że RGG jest połączone jest i prawdopodobieństwo, że RGG nie jest połączone, wynosi . ${\textstyle (1-\pi r^{2})^{n-1}}$${\styl tekstu X}$${\styl tekstu X}$${\textstyle E(X)=n(1-\pi r^{2})^{n-1}=ne^{-\pi r^{2}n}-O(r^{4}n) }$${\textstyle \mu =ne^{-\pi r^{2}n}}$${\textstyle \mu \longrightarrow 0}$${\ Displaystyle \ mu \ longrightarrow \ infty}$${\textstyle \mu =\Theta (1)}$${\textstyle {\frac {n}{2}}}$${\ Displaystyle X}$${\ Displaystyle \ mu}$${\textstyle \mu =\Theta (1)}$${\textstyle P[X=0]\sim e^{-\mu }}$${\textstyle P[X>0]\sim 1-e^{-\mu }}$

Dla dowolnej -Normy ( ) i dowolnej liczby wymiarów , RGG posiada ostry próg łączności przy stałej . W szczególnym przypadku przestrzeni dwuwymiarowej i normy euklidesowej ( i ) daje to . ${\textstyle l_{p}}$${\textstyle 1\leq p\leq \infty }$${\displaystyle d>2}$${\textstyle r\sim ({\ln(n) \over \alpha _{p,d}n})^{1 \over d}}$${\displaystyle \alfa _{p,d}}$${\displaystyle d=2}$${\displaystyle p=2}$${\textstyle r\sim {\sqrt {\ln(n) \over \pi n}}}$

Hamiltoniczność

Wykazano, że w przypadku dwuwymiarowym próg dostarcza również informacji o istnieniu cyklu hamiltonowskiego ( Ścieżka hamiltonowska ). Dla każdego , jeśli , to RGG ma asymptotycznie prawie na pewno brak cyklu Hamiltona, a jeśli dla żadnego , to RGG ma asymptotycznie prawie na pewno cykl hamiltonowski. ${\textstyle r\sim {\sqrt {\ln(n) \over \pi n}}}$${\ Displaystyle \ epsilon > 0}$${\textstyle r\sim {\sqrt {\ln(n) \over (\pi +\epsilon )n}}}$${\textstyle r\sim {\sqrt {\ln(n) \over (\pi -\epsilon )n}}}$${\textstyle \epsilon >0}$

Współczynnik klastrowania

Współczynnik klastrów z RGGs zależy tylko od wymiarowania z d z Bazowy miejsca [0,1) ^d . Współczynnik grupowania wynosi

${\textstyle C_{d}=1-H_{d}(1)}$na parzyste i na nieparzyste gdzie${\displaystyle d}$${\textstyle C_{d}={3 \over 2}-H_{d}({1 \over 2})}$${\displaystyle d}$

Dla dużych upraszcza to do . ${\displaystyle d}$${\ Displaystyle C_ {d} \ SIM 3 {\ sqrt {2 \ nad \ pi d}} ({3 \ nad 4}) ^ {d + 1 \ nad 2}}$

Uogólnione losowe wykresy geometryczne

W 1988 roku Waxman uogólnił standardową RGG, wprowadzając probabilistyczną funkcję koneksji w przeciwieństwie do deterministycznej funkcji sugerowanej przez Gilberta. Przykładem wprowadzonym przez Waxmana był rozciągnięty wykładnik, gdzie dwa węzły i łączą się z prawdopodobieństwem podanym przez gdzie jest separacją euklidesową, a , są parametrami wyznaczonymi przez system. Ten typ RGG z funkcją połączenia probabilistycznego jest często określany jako miękki losowy wykres geometryczny, który ma teraz dwa źródła losowości; lokalizacja węzłów (wierzchołków) i tworzenie połączeń (krawędzi). Ta funkcja połączenia została dalej uogólniona w literaturze i jest często wykorzystywana do badania sieci bezprzewodowych bez zakłóceń. Parametr ten przedstawia, w jaki sposób sygnał zanika wraz z odległością, gdy jest wolna przestrzeń, modeluje bardziej zagracone środowisko, takie jak miasto (= 6 modeli miast, takich jak Nowy Jork), podczas gdy modeluje środowiska o wysokim współczynniku odbicia. Zauważamy, że to model Waxman, podczas gdy jak i mamy standardową RGG. Intuicyjnie tego typu funkcje połączeń modelują, jak prawdopodobieństwo utworzenia łącza maleje wraz z odległością. ${\displaystyle i}$${\displaystyle j}$${\textstyle H_{ij}=\beta e^{-{r_{ij} \over r_{0}}}}$${\displaystyle r_{ij}}$${\ Displaystyle \ beta}$${\displaystyle r_{0}}$${\textstyle H_{ij}=\beta e^{-({r_{ij} \over r_{0}})^{\eta }}}$${\displaystyle \eta}$${\ Displaystyle \ eta = 2}$${\ Displaystyle \ eta > 2}$${\ Displaystyle \ eta <2}$${\ Displaystyle \ eta =1}$${\ Displaystyle \ eta \ do \ infty}$${\textstyle \beta =1}$

Przegląd niektórych wyników dla Soft RGG

W limicie wysokiej gęstości dla sieci z funkcją połączenia wykładniczego liczba izolowanych węzłów ma rozkład Poissona, a powstała sieć zawiera unikalny gigantyczny komponent i tylko izolowane węzły. Dlatego dzięki zapewnieniu, że nie ma izolowanych węzłów, w gęstym reżimie sieć jest w pełni połączona; podobne do wyników pokazanych w modelu dysku. Często właściwości tych sieci, takie jak centralne położenie i łączność, są badane na granicy, ponieważ gęstość, co często oznacza, że ​​efekty graniczne stają się nieistotne. Jednak w prawdziwym życiu, gdzie sieci są ograniczone, choć nadal mogą być niezwykle gęste, efekty graniczne będą miały wpływ na pełną łączność; w rzeczywistości pokazał, że na pełną łączność, z wykładniczą funkcją połączenia, duży wpływ mają efekty brzegowe, ponieważ węzły w pobliżu narożnika/powierzchni domeny mają mniejsze szanse na połączenie w porównaniu z węzłami masowymi. W rezultacie pełna łączność może być wyrażona jako suma udziałów z masy i granic geometrycznych. Bardziej ogólna analiza funkcji połączeniowych w sieciach bezprzewodowych wykazała, że ​​prawdopodobieństwo pełnej łączności można dobrze aproksymować za pomocą kilku momentów funkcji połączeniowej i geometrii regionów. ${\ Displaystyle \ do \ infty}$

Bibliografia