Gráfica geométrica hiperbólica

Un grafo geométrico hiperbólico (HGG) o red geométrica hiperbólica (HGN) es un tipo especial de red espacial donde (1) las coordenadas latentes de los nodos se esparcen de acuerdo con una función de densidad de probabilidad en un espacio hiperbólico de curvatura negativa constante y (2) hay una arista entre dos nodos si están cerca de acuerdo con una función de la métrica ^{[1] [2]} (típicamente una función de paso de Heaviside que resulta en conexiones deterministas entre vértices más cercanos que una cierta distancia umbral, o una función decreciente de la distancia hiperbólica que produce la probabilidad de conexión). Un HGG generaliza un grafo geométrico aleatorio (RGG) cuyo espacio de incrustación es euclidiano.

Formulación matemática

Matemáticamente, un HGG es un grafo con un conjunto de vértices V ( cardinalidad ) y un conjunto de aristas E construido considerando los nodos como puntos colocados en un espacio hiperbólico bidimensional de curvatura gaussiana negativa constante y radio de corte , es decir, el radio del disco de Poincaré que se puede visualizar utilizando un modelo hiperboloide . Cada punto tiene coordenadas polares hiperbólicas con y . ${\displaystyle G(V,E)}$ ${\displaystyle N=|V|}$ ${\displaystyle \mathbb {H} _{\zeta }^{2}}$ ${\displaystyle -\zeta ^{2}}$ ${\displaystyle R}$ ${\displaystyle i}$ ${\displaystyle (r_{i},\theta _{i})}$ ${\displaystyle 0\leq r_{i}\leq R}$ ${\displaystyle 0\leq \theta _{i}<2\pi }$

La ley hiperbólica de los cosenos permite medir la distancia entre dos puntos y , ^[2] ${\displaystyle d_{ij}}$ ${\displaystyle i}$ ${\displaystyle j}$

${\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 )}.}$

El ángulo  es el ángulo (más pequeño) entre los dos vectores de posición . ${\displaystyle \Delta }$

En el caso más simple, se establece un borde si y solo si) dos nodos están dentro de un cierto radio de vecindad , esto corresponde a un umbral de influencia. ${\displaystyle (i,j)}$  ${\displaystyle r}$ ${\displaystyle d_{ij}\leq r}$

Función de decaimiento de la conectividad

En general, se establecerá un enlace con una probabilidad que depende de la distancia  . Una función de decaimiento de la conectividad representa la probabilidad de asignar una arista a un par de nodos a una distancia . En este marco, el caso simple de vecindad de código duro como en los gráficos geométricos aleatorios se conoce como función de decaimiento de truncamiento . ^[3] ${\displaystyle d_{ij}}$ ${\displaystyle \gamma (s):\mathbb {R} ^{+}\to [0,1]}$ ${\displaystyle s}$

Generación de gráficos geométricos hiperbólicos

Krioukov et al. ^[2] describen cómo generar gráficos geométricos hiperbólicos con una distribución de nodos uniformemente aleatoria (así como versiones generalizadas) en un disco de radio en . Estos gráficos producen una distribución de ley de potencia para los grados de los nodos. La coordenada angular de cada punto/nodo se elige de forma uniformemente aleatoria entre , mientras que la función de densidad para la coordenada radial r se elige de acuerdo con la distribución de probabilidad : ${\displaystyle R}$ ${\displaystyle \mathbb {H} _{\zeta }^{2}}$ ${\displaystyle \theta }$ ${\displaystyle [0,2\pi ]}$ ${\displaystyle \rho }$

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

El parámetro de crecimiento controla la distribución: para , la distribución es uniforme en , para valores más pequeños los nodos se distribuyen más hacia el centro del disco y para valores más grandes más hacia el borde. En este modelo, los bordes entre los nodos y existen si y solo si o con probabilidad si se utiliza una función de decaimiento de conectividad más general. El grado promedio está controlado por el radio del disco hiperbólico. Se puede demostrar que para los grados de los nodos siguen una distribución de ley de potencia con exponente . ${\displaystyle \alpha >0}$ ${\displaystyle \alpha =\zeta }$ ${\displaystyle \mathbb {H} _{\zeta }^{2}}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle d_{uv}<R}$ ${\displaystyle \gamma (d_{uv})}$ ${\displaystyle R}$ ${\displaystyle \alpha /\zeta >1/2}$ ${\displaystyle \gamma =1+2\alpha /\zeta }$

La imagen muestra gráficos generados aleatoriamente para diferentes valores de y en . Se puede observar cómo tiene un efecto en la distribución de los nodos y en la conectividad del gráfico. Para la visualización del gráfico se utiliza la representación nativa donde las variables de distancia tienen sus valores hiperbólicos verdaderos, por lo tanto, los bordes son líneas rectas. ${\displaystyle \alpha }$ ${\displaystyle R}$ ${\displaystyle \mathbb {H} _{1}^{2}}$ ${\displaystyle \alpha }$ ${\displaystyle R}$

Gráficos geométricos hiperbólicos aleatorios con N=100 nodos cada uno para diferentes valores de alfa y R

Generador de complejidad cuadrática

Fuente: ^[4]

El algoritmo ingenuo para la generación de grafos geométricos hiperbólicos distribuye los nodos en el disco hiperbólico eligiendo las coordenadas angulares y radiales de cada punto que se muestrean aleatoriamente. Para cada par de nodos se inserta una arista con la probabilidad del valor de la función de decaimiento de conectividad de su respectiva distancia. El pseudocódigo se ve de la siguiente manera:

 ${\displaystyle V=\{\},E=\{\}}$para  hacer para cada par hacer si entonces regresar ${\displaystyle i\gets 0}$   ${\displaystyle N-1}$   ${\displaystyle \theta \gets U[0,2\pi ]}$  ${\displaystyle r\gets {\frac {1}{\alpha }}{\text{acosh}}(1+(\cosh \alpha R-1)U[0,1])}$  ${\displaystyle V=V\cup \{(r,\theta )\}}$  ${\displaystyle (u,v)\in V\times V,u\neq v}$    ${\displaystyle U[0,1]\leq \gamma (d_{uv})}$   ${\displaystyle E=E\cup \{(u,v)\}}$  ${\displaystyle V,E}$

${\displaystyle N}$es el número de nodos a generar, la distribución de la coordenada radial por la función de densidad de probabilidad se logra utilizando el muestreo por transformada inversa . denota el muestreo uniforme de un valor en el intervalo dado. Debido a que el algoritmo verifica los bordes de todos los pares de nodos, el tiempo de ejecución es cuadrático. Para aplicaciones donde es grande, esto ya no es viable y se necesitan algoritmos con un tiempo de ejecución subcuadrático. ${\displaystyle \rho }$ ${\displaystyle U}$ ${\displaystyle N}$

Generación subcuadrática

Para evitar la comprobación de los bordes entre cada par de nodos, los generadores modernos utilizan estructuras de datos adicionales que dividen el gráfico en bandas. ^{[5] [6]} Una visualización de esto muestra un gráfico hiperbólico con el límite de las bandas dibujado en naranja. En este caso, la partición se realiza a lo largo del eje radial. Los puntos se almacenan ordenados por su coordenada angular en su respectiva banda. Para cada punto , los límites de su círculo hiperbólico de radio se pueden (sobre)estimar y utilizar para realizar la comprobación de los bordes solo para los puntos que se encuentran en una banda que interseca el círculo. Además, la clasificación dentro de cada banda se puede utilizar para reducir aún más la cantidad de puntos a observar al considerar solo los puntos cuya coordenada angular se encuentra en un cierto rango alrededor de la de (este rango también se calcula sobrestimando el círculo hiperbólico alrededor de ). ${\displaystyle u}$ ${\displaystyle R}$ ${\displaystyle u}$ ${\displaystyle u}$

Usando esta y otras extensiones del algoritmo, las complejidades temporales de (donde es el número de nodos y el número de aristas) son posibles con alta probabilidad. ^[7] ${\displaystyle {\mathcal {O}}(n\log \log n+m)}$ ${\displaystyle n}$ ${\displaystyle m}$

El gráfico hiperbólico está dividido en bandas de modo que cada una de ellas contiene aproximadamente el mismo número de puntos.

Recomendaciones

Para (curvatura gaussiana ), los HGG forman un conjunto de redes para las cuales es posible expresar la distribución de grados analíticamente como una forma cerrada para el caso límite de un gran número de nodos. ^[2] Vale la pena mencionar esto ya que no es cierto para muchos conjuntos de gráficos. ${\displaystyle \zeta =1}$ ${\displaystyle K=-1}$

Aplicaciones

Se han sugerido los HGG como un modelo prometedor para las redes sociales donde la hiperbolicidad aparece a través de una competencia entre la similitud y la popularidad de un individuo. ^[8]

Referencias

1. Barthélemy, Marc (2011). "Redes espaciales". Physics Reports . 499 (1–3): 1–101. arXiv : 1010.0302 . Código Bibliográfico :2011PhR...499....1B. doi :10.1016/j.physrep.2010.11.002. S2CID  4627021.
2. Krioukov, Dmitri; Papadopoulos, Fragkiskos; Kitsak, Maksim; Vahdat, Amin; Boguñá, Marián (2010). "Geometría hiperbólica de redes complejas". Physical Review E . 82 (3): 036106. arXiv : 1006.5169 . Código Bibliográfico :2010PhRvE..82c6106K. doi :10.1103/PhysRevE.82.036106. PMID  21230138. S2CID  6451908.
3. Barnett, L.; Di Paolo, E.; Bullock, S. (2007). "Redes aleatorias embebidas espacialmente" (PDF) . Physical Review E . 76 (5): 056115. Bibcode :2007PhRvE..76e6115B. doi :10.1103/PhysRevE.76.056115. PMID  18233726. Archivado (PDF) desde el original el 2023-02-04 . Consultado el 2023-02-04 .
4. Krioukov, Dmitri; Orsini, Chiara; Aldecoa, Rodrigo (17 de marzo de 2015). "Generador de grafos hiperbólicos". Computer Physics Communications . 196 : 492–496. arXiv : 1503.05180 . Código Bibliográfico :2015CoPhC.196..492A. doi :10.1016/j.cpc.2015.05.028. S2CID  8454036.
5. von Looz, Moritz; Meyerhenke, Henning; Prutkin, Roman (2015). "Generación de gráficos hiperbólicos aleatorios en tiempo subcuadrático". En Elbassioni, Khaled; Makino, Kazuhisa (eds.). Algoritmos y computación . Apuntes de clase en informática. Vol. 9472. Springer Berlin Heidelberg. págs. 467–478. doi :10.1007/978-3-662-48971-0_40. ISBN 9783662489710.
6. Meyerhenke, Henning; Laue, Sören; Özdayi, Mustafa; von Looz, Moritz (30 de junio de 2016). "Generar redes complejas masivas con geometría hiperbólica más rápido en la práctica". arXiv.org. arXiv : 1606.09481 . Código Bibliográfico :2016arXiv160609481V. {{cite journal}}: Requiere citar revista |journal=( ayuda )
7. Penschuck, Manuel (2017). "Generación de gráficos hiperbólicos aleatorios prácticos en tiempo casi lineal y con memoria sublineal". Schloss Dagstuhl - Leibniz-Zentrum für Informatik GMBH, Wadern/Saarbruecken, Alemania . Procedimientos internacionales de informática de Leibniz (LIPIcs). 75 : 26:1–26:21. doi : 10.4230/lipics.sea.2017.26 . ISBN 9783959770361Archivado desde el original el 4 de febrero de 2023. Consultado el 4 de febrero de 2023 .
8. Papadopoulos, Fragkiskos; Kitsak, Maksim; Serrano, M. Ángeles; Boguñá, Marián; Krioukov, Dmitri (12 de septiembre de 2012). "Popularidad versus similitud en redes en crecimiento". Naturaleza . 489 (7417): 537–540. arXiv : 1106.0286 . Código Bib :2012Natur.489..537P. doi : 10.1038/naturaleza11459. PMID  22972194. S2CID  4424179.