Hyperbolický geometrický graf - Hyperbolic geometric graph - Wikipedia

Síťová věda
Teorie
Graf Komplexní síť Nákaza Malý svět Bez vodního kamene Struktura Společenství Perkolace Vývoj Ovladatelnost Kreslení grafu Sociální kapital Analýza odkazů Optimalizace Vzájemnost Uzavření Homofilie Přechodnost Preferenční příloha Teorie rovnováhy Síťový efekt Sociální vliv
Typy sítí
Informační (výpočetní) Telekomunikace Doprava Sociální Vědecká spolupráce Biologický Umělý neurální Vzájemně závislé Sémantický Prostorový Závislost Tok na čipu
Grafy
Funkce Klika Součástka Střih Cyklus Datová struktura Okraj Smyčka Sousedství Cesta Vrchol Seznam sousedů  / matice Seznam případů  / matice Typy Bipartitní Kompletní Režie Hyper Multi Náhodný Vážený
Metriky Algoritmy
Centrálnost Stupeň Mezi Blízkost PageRank Motiv Shlukování Rozdělení stupňů Assortativity Vzdálenost Modularita Účinnost
Modely
Topologie Náhodný graf Erdős – Rényi Barabási – Albert Fitness model Watts – Strogatz Exponenciální náhodné (ERGM) Náhodné geometrické (RGG) Hyperbolický (HGN) Hierarchický Stochastický blok Maximální entropie Měkká konfigurace Referenční hodnota LFR Dynamika Booleovská síť agent Epidemický /VÁŽENÝ PANE
Seznamy Kategorie
Témata Software Síťoví vědci Kategorie: Teorie sítí Kategorie: Teorie grafů

A hyperbolický geometrický graf (HGG) nebo hyperbolická geometrická síť (HGN) je speciální typ prostorová síť kde (1) latentní souřadnice uzlů jsou posypány podle a funkce hustoty pravděpodobnosti dohyperbolický prostor z konstantní negativní zakřivení a (2) an okraj mezi dvěma uzly je přítomen, pokud jsou blízké podle funkce metrický^[1][2] (obvykle buď a Funkce Heaviside step což má za následek deterministické spojení mezi vrcholy bližšími, než je určitá prahová vzdálenost, nebo rozpadající se funkce hyperbolické vzdálenosti poskytující pravděpodobnost spojení). HGG zobecňuje a náhodný geometrický graf (RGG), jehož vkládací prostor je Euklidovský.

Matematická formulace

Matematicky, a HGG je graf ${ displaystyle G (V, E)}$ s vrcholem soubor PROTI (mohutnost ${ displaystyle N = | V |}$) a sadu hran E zkonstruováno zvážením uzlů jako bodů umístěných do 2-dimenzionálního hyperbolického prostoru ${ displaystyle mathbb {H} _ { zeta} ^ {2}}$ konstantní zápor Gaussovo zakřivení, ${ displaystyle - zeta ^ {2}}$ a poloměr odříznutí ${ displaystyle R}$, tj. poloměr Poincaré disk které lze vizualizovat pomocí a hyperboloidní model.Každý bod ${ displaystyle i}$ má hyperbolické polární souřadnice ${ displaystyle (r_ {i}, theta _ {i})}$ s ${ displaystyle 0 leq r_ {i} leq R}$ a ${ displaystyle 0 leq theta _ {i} <2 pi}$.

The hyperbolický zákon kosinů umožňuje měřit vzdálenost ${ displaystyle d_ {ij}}$ mezi dvěma body ${ displaystyle i}$ a ${ displaystyle j}$,^[2]

${ displaystyle cosh ( zeta d_ {ij}) = cosh ( zeta r_ {i}) cosh ( zeta r_ {j})}$${ displaystyle - sinh ( zeta r_ {i}) sinh ( zeta r_ {j}) cos { bigg (} underbrace { pi ! - ! { bigg |} pi - | theta _ {i} ! - ! theta _ {j} | { bigg |}} _ { Delta} { bigg)}.}$

Úhel${ displaystyle Delta}$ je (nejmenší) úhel mezi nimipolohové vektory.

V nejjednodušším případě hrana ${ displaystyle (i, j)}$ je stanoveno, pokud (pokud a pouze pokud) jsou dva uzly v určitém poloměr sousedství ${ displaystyle r}$, ${ displaystyle d_ {ij} leq r}$, to odpovídá prahové hodnotě vlivu.

Funkce rozpadu připojení

Obecně bude spojení navázáno s pravděpodobností v závislosti na vzdálenosti${ displaystyle d_ {ij}}$. A funkce rozpadu připojení ${ displaystyle gamma (s): mathbb {R} ^ {+} až [0,1]}$ představuje pravděpodobnost přiřazení hrany dvojici uzlů na dálku ${ displaystyle s}$. V tomto rámci je jednoduchý případ pevný kód sousedství jako v náhodné geometrické grafy se označuje jako funkce zkrácení zkrácení.^[3]

Generování hyperbolických geometrických grafů

Krioukov a kol.^[2] popsat, jak generovat hyperbolické geometrické grafy s rovnoměrně náhodným rozložením uzlů (stejně jako zobecněné verze) na disku o poloměru ${ displaystyle R}$ v ${ displaystyle mathbb {H} _ { zeta} ^ {2}}$. Tyto grafy poskytují a rozdělení moci a zákona pro stupně uzlů. Úhlová souřadnice ${ displaystyle theta}$ každého bodu / uzlu je vybráno rovnoměrně náhodně ${ displaystyle [0,2 pi]}$, zatímco funkce hustoty pro radiální souřadnici r je zvolena podle rozdělení pravděpodobnosti ${ displaystyle rho}$:

${ displaystyle rho (r) = alpha { frac { sinh ( alpha r)} { cosh ( alpha R) -1}}}$

Parametr růstu ${ displaystyle alpha> 0}$ řídí distribuci: Pro ${ displaystyle alpha = zeta}$, distribuce je v jednotném formátu ${ displaystyle mathbb {H} _ { zeta} ^ {2}}$, pro menší hodnoty jsou uzly distribuovány více směrem ke středu disku a pro větší hodnoty více směrem k hranici. V tomto modelu hrany mezi uzly ${ displaystyle u}$ a ${ displaystyle v}$ existuje-li ${ displaystyle d_ {uv}$ nebo s pravděpodobností ${ displaystyle gamma (d_ {uv})}$ pokud se použije obecnější funkce rozpadu připojení. Průměrný stupeň je řízen poloměrem ${ displaystyle R}$ hyperbolického disku. Je možné ukázat, že pro ${ displaystyle alpha / zeta> 1/2}$ stupně uzlů sledují rozdělení zákonu moci s exponentem ${ displaystyle gamma = 1 + 2 alpha / zeta}$.

Obrázek zobrazuje náhodně generované grafy pro různé hodnoty ${ displaystyle alpha}$ a ${ displaystyle R}$ v ${ displaystyle mathbb {H} _ {1} ^ {2}}$. Je vidět, jak ${ displaystyle alpha}$ má vliv na distribuci uzlů a ${ displaystyle R}$ na konektivitu grafu. K vizualizaci grafu se používá nativní reprezentace, kde proměnné vzdálenosti mají své skutečné hyperbolické hodnoty, proto jsou hrany přímky.

Náhodné hyperbolické geometrické grafy s N = 100 uzlů pro různé hodnoty alfa a R

Generátor kvadratické složitosti^[4]

Naivní algoritmus pro generování hyperbolických geometrických grafů distribuuje uzly na hyperbolickém disku výběrem úhlových a radiálních souřadnic každého bodu a jsou náhodně vzorkovány. Pro každou dvojici uzlů se pak vloží hrana s pravděpodobností hodnoty funkce rozpadu konektivity jejich příslušné vzdálenosti. Pseudokód vypadá následovně:

${ displaystyle V =  {}, E =  {}}$pro ${ Displaystyle  dostane 0}$ na ${ displaystyle N-1}$ dělat    ${ displaystyle  theta  dostane U [0,2  pi]}$    ${ displaystyle r  gets { frac {1} { alpha}} { text {acosh}} (1 + ( cosh  alpha R-1) U [0,1])}$    ${ displaystyle V = V  pohár  {(r,  theta) }}$pro každý pár  ${ displaystyle (u, proti)  v V  krát V, u  neq v}$ dělat    -li ${ displaystyle U [0,1]  leq  gamma (d_ {uv})}$ pak        ${ displaystyle E = E  pohár  {(u, v) }}$vrátit se ${ displaystyle V, E}$

${ displaystyle N}$ je počet uzlů, které se mají generovat, rozdělení radiální souřadnice podle funkce hustoty pravděpodobnosti ${ displaystyle rho}$ je dosaženo použitím vzorkování inverzní transformace. ${ displaystyle U}$označuje jednotné vzorkování hodnoty v daném intervalu. Protože algoritmus kontroluje hrany pro všechny páry uzlů, je runtime kvadratický. Pro aplikace, kde ${ displaystyle N}$ je velký, už to není životaschopné a jsou potřeba algoritmy se subkvadratickým runtime.

Subkvadratická generace

Aby se zabránilo kontrole hran mezi každou dvojicí uzlů, používají moderní generátory další datové struktury že rozdělit graf do pásem.^[5][6] Vizualizace toho ukazuje hyperbolický graf s hranicí pruhů nakreslených oranžově. V tomto případě se dělení provádí podél radiální osy. Body se ukládají seřazené podle úhlové souřadnice v příslušném pásmu. Za každý bod ${ displaystyle u}$, limity jeho hyperbolického kruhu poloměru ${ displaystyle R}$ lze (nad-) odhadnout a použít pouze k provedení kontroly hran u bodů, které leží v pásmu, které protíná kruh. Kromě toho lze třídění v každém pásmu použít k dalšímu snížení počtu bodů, na které se díváme, pouze s ohledem na body, jejichž úhlová souřadnice leží v určitém rozsahu kolem jednoho z ${ displaystyle u}$ (tento rozsah je také vypočítán nadhodnocením hyperbolického kruhu kolem ${ displaystyle u}$).

Pomocí tohoto a dalších rozšíření algoritmu, časové složitosti ${ displaystyle { mathcal {O}} (n log log n + m)}$(kde ${ displaystyle n}$ je počet uzlů a ${ displaystyle m}$ počet hran) jsou možné s vysokou pravděpodobností.^[7]

Hyperbolický graf je rozdělen do pásem tak, že každý z nich drží přibližně stejný počet bodů.

Zjištění

Pro ${ displaystyle zeta = 1}$ (Gaussovo zakřivení ${ displaystyle K = -1}$), HGG tvoří soubor sítí, pro které je možné vyjádřit rozdělení stupňů analyticky jako uzavřená forma pro omezující případ velkého počtu uzlů.^[2] To stojí za zmínku, protože to neplatí pro mnoho souborů grafů.

Aplikace

HGG byly navrženy jako slibný model pro sociální sítě kde se hyperbolicita objevuje prostřednictvím konkurence mezi podobnost a popularita jednotlivce.^[8]

Reference