Gráfica geométrica aleatoria

En teoría de grafos, la red espacial matemáticamente más simple

En teoría de grafos , un grafo geométrico aleatorio ( RGG ) es la red espacial matemáticamente más simple , es decir, un grafo no dirigido construido colocando aleatoriamente N nodos en algún espacio métrico (de acuerdo con una distribución de probabilidad especificada) y conectando dos nodos mediante un enlace si y solo si su distancia está en un rango dado, por ejemplo, menor que un cierto radio de vecindad, r .

Los gráficos geométricos aleatorios se parecen a las redes sociales humanas reales en varios aspectos. Por ejemplo, demuestran espontáneamente la estructura de la comunidad : grupos de nodos con alta modularidad . Otros algoritmos de generación de gráficos aleatorios, como los generados mediante el modelo Erdős–Rényi o el modelo Barabási–Albert (BA), no crean este tipo de estructura. Además, los gráficos geométricos aleatorios muestran una asortatividad de grados según su dimensión espacial: ^[1] los nodos "populares" (aquellos con muchos vínculos) tienen una probabilidad particular de estar vinculados a otros nodos populares.

Una aplicación real de los RGG es el modelado de redes ad hoc . ^[2] Además, se utilizan para realizar evaluaciones comparativas para algoritmos gráficos.

Definición

La generación de un gráfico geométrico aleatorio para diferentes parámetros de conectividad r.

En lo que sigue, sea  G = ( V , E ) un grafo no dirigido con un conjunto de vértices V y un conjunto de aristas E ⊆ V × V . Los tamaños de los conjuntos se denotan por | V | = n y | E | = m . Además, si no se indica lo contrario, se considera el espacio métrico [0,1) ^d con la distancia euclidiana , es decir, para cualquier punto la distancia euclidiana de x e y se define como ${\displaystyle x,y\in [0,1)^{d}}$

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

Un grafo geométrico aleatorio (RGG) es un grafo geométrico no dirigido con nodos muestreados aleatoriamente de la distribución uniforme del espacio subyacente [0,1) ^d . ^[3] Dos vértices p, q ∈ V están conectados si, y solo si, su distancia es menor que un parámetro especificado previamente r ∈ (0,1) , excluyendo cualquier bucle . Por lo tanto, los parámetros r y n caracterizan completamente un RGG.

Algoritmos

Algoritmo ingenuo

El enfoque ingenuo consiste en calcular la distancia de cada vértice a cada uno de los demás vértices. Como existen posibles conexiones que se comprueban, la complejidad temporal del algoritmo ingenuo es . Las muestras se generan utilizando un generador de números aleatorios (RNG) en . En la práctica, se puede implementar esto utilizando d generadores de números aleatorios en , un RNG para cada dimensión. ${\textstyle {\frac {n(n-1)}{2}}}$ ${\textstyle \Theta (n^{2})}$ ${\displaystyle [0,1)^{d}}$ ${\displaystyle [0,1)}$

Pseudocódigo

V  := generateSamples( n ) // Genera n muestras en el cubo unitario. para cada  p ∈ V  hacer  para cada  q ∈ V \{p} hacer  si distancia( p , q ) ≤ r  entonces addConnection( p , q ) // Agrega la arista (p, q) a la estructura de datos de la arista.  fin si  fin para fin para

Como este algoritmo no es escalable (cada vértice necesita información de todos los demás vértices), Holtgrewe et al. y Funke et al. han introducido nuevos algoritmos para este problema.

Algoritmos distribuidos

Holtgrewe y otros.

Este algoritmo, propuesto por Holtgrewe et al., fue el primer algoritmo generador de RGG distribuido para dimensión 2. ^[4] Divide el cuadrado unitario en celdas de igual tamaño con una longitud de lado de al menos . Para un número dado de procesadores, a cada procesador se le asignan celdas, donde Para simplificar, se supone que es un número cuadrado, pero esto se puede generalizar a cualquier número de procesadores. Luego, cada procesador genera vértices, que luego se distribuyen a sus respectivos propietarios. Luego, los vértices se ordenan por el número de celda en el que caen, por ejemplo con Quicksort . A continuación, cada procesador envía a sus procesadores adyacentes la información sobre los vértices en las celdas del borde, de modo que cada unidad de procesamiento puede calcular los bordes en su partición independientemente de las otras unidades. El tiempo de ejecución esperado es . Un límite superior para el costo de comunicación de este algoritmo está dado por , donde denota el tiempo para una comunicación de todos a todos con mensajes de longitud l bits a c socios de comunicación. es el tiempo que toma una comunicación punto a punto para un mensaje de longitud l bits. ${\displaystyle r}$ ${\displaystyle P=p^{2}}$ ${\textstyle {k \over p}\times {k \over p}}$ ${\textstyle k=\left\lfloor {1/r}\right\rfloor .}$ ${\textstyle P}$ ${\textstyle {\frac {n}{P}}}$ ${\textstyle O({\frac {n}{P}}\log {\frac {n}{P}})}$ ${\displaystyle T_{all-to-all}(n/P,P)+T_{all-to-all}(1,P)+T_{point-to-point}(n/(k\cdot {P})+2)}$ ${\displaystyle T_{all-to-all}(l,c)}$ ${\displaystyle T_{point-to-point}(l)}$

Dado que este algoritmo no está libre de comunicación, Funke et al. propusieron ^[4] un generador RGG distribuido escalable para dimensiones superiores, que funciona sin ninguna comunicación entre las unidades de procesamiento.

Funke y otros.

El enfoque utilizado en este algoritmo ^[4] es similar al enfoque de Holtgrewe: Particionar el cubo unitario en trozos de igual tamaño con una longitud de lado de al menos r . Entonces, en d = 2, serán cuadrados, en d = 3, serán cubos. Como solo pueden caber como máximo trozos por dimensión, el número de trozos está limitado a . Como antes, a cada procesador se le asignan trozos, para los cuales genera los vértices. Para lograr un proceso sin comunicación, cada procesador genera los mismos vértices en los trozos adyacentes explotando la pseudoaleatorización de las funciones hash sembradas . De esta manera, cada procesador calcula los mismos vértices y no hay necesidad de intercambiar información de vértices. ${\textstyle {\left\lfloor {1/r}\right\rfloor }}$ ${\textstyle {\left\lfloor {1/r}\right\rfloor }^{d}}$ ${\textstyle {\left\lfloor {1/r}\right\rfloor }^{d} \over P}$

Para la dimensión 3, Funke et al. demostraron que el tiempo de ejecución esperado es , sin ningún costo de comunicación entre unidades de procesamiento. ${\textstyle O({\frac {m+n}{P}}+\log {P})}$

Propiedades

Vértices aislados y conectividad

La probabilidad de que un único vértice esté aislado en un RGG es . ^[5] Sea la variable aleatoria que cuenta cuántos vértices están aislados. Entonces el valor esperado de es . El término proporciona información sobre la conectividad del RGG. Para , el RGG está asintóticamente casi seguramente conectado. Para , el RGG está asintóticamente casi seguramente desconectado. Y para , el RGG tiene un componente gigante que cubre más de vértices y se distribuye por Poisson con parámetro . De ello se deduce que si , la probabilidad de que el RGG esté conectado es y la probabilidad de que el RGG no esté conectado es . ${\textstyle (1-\pi r^{2})^{n-1}}$ ${\textstyle X}$ ${\textstyle 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 }}$

Para cualquier -Norma ( ) y para cualquier número de dimensiones , un RGG posee un umbral de conectividad agudo en con constante . En el caso especial de un espacio bidimensional y la norma euclidiana ( y ) esto produce . ${\textstyle l_{p}}$ ${\textstyle 1\leq p\leq \infty }$ ${\displaystyle d>2}$ ${\textstyle r\sim \left({\ln(n) \over \alpha _{p,d}n}\right)^{1 \over d}}$ ${\displaystyle \alpha _{p,d}}$ ${\displaystyle d=2}$ ${\displaystyle p=2}$ ${\textstyle r\sim {\sqrt {\ln(n) \over \pi n}}}$

Hamiltonicidad

Se ha demostrado que, en el caso bidimensional, el umbral también proporciona información sobre la existencia de un ciclo hamiltoniano ( camino hamiltoniano ). ^[6] Para cualquier , si , entonces el RGG asintóticamente casi seguramente no tiene ciclo hamiltoniano y si para cualquier , entonces el RGG asintóticamente casi seguramente tiene un ciclo hamiltoniano. ${\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}$

Coeficiente de agrupamiento

El coeficiente de agrupamiento de los RGG depende únicamente de la dimensión d del espacio subyacente [0,1) ^d . El coeficiente de agrupamiento es ^[7]

${\textstyle C_{d}=1-H_{d}(1)}$para pares y para impares donde para grandes , esto se simplifica a . ${\displaystyle d}$ ${\textstyle C_{d}={3 \over 2}-H_{d}({1 \over 2})}$ ${\displaystyle d}$ $${\displaystyle H_{d}(x)={1 \over {\sqrt {\pi }}}\sum _{i=x}^{d \over 2}{\Gamma (i) \over \Gamma (i+{1 \over 2})}\left({3 \over 4}\right)^{i+{1 \over 2}}}$$ ${\displaystyle d}$ ${\displaystyle C_{d}\sim 3{\sqrt {2 \over \pi d}}\left({3 \over 4}\right)^{d+1 \over 2}}$

Gráficos geométricos aleatorios generalizados

En 1988 Waxman ^[8] generalizó el RGG estándar introduciendo una función de conexión probabilística en oposición a la determinista sugerida por Gilbert. El ejemplo introducido por Waxman fue una exponencial estirada donde dos nodos y se conectan con probabilidad dada por donde es la separación euclidiana y , son parámetros determinados por el sistema. Este tipo de RGG con función de conexión probabilística a menudo se conoce como un gráfico geométrico aleatorio suave, que ahora tiene dos fuentes de aleatoriedad: la ubicación de los nodos (vértices) y la formación de enlaces (bordes). Esta función de conexión se ha generalizado aún más en la literatura y a menudo se usa para estudiar redes inalámbricas sin interferencias. El parámetro representa cómo la señal decae con la distancia, cuando es espacio libre, modela un entorno más desordenado como una ciudad (= 6 modela ciudades como Nueva York) mientras que modela entornos altamente reflexivos. Notamos que para es el modelo de Waxman, mientras que como y tenemos el RGG estándar. Intuitivamente, este tipo de funciones de conexión modelan cómo la probabilidad de que se realice un enlace decae con la distancia. ${\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^{-\left({r_{ij} \over r_{0}}\right)^{\eta }}}$ ${\displaystyle \eta }$ ${\displaystyle \eta =2}$ ${\displaystyle \eta >2}$ ${\displaystyle \eta <2}$ ${\displaystyle \eta =1}$ ${\displaystyle \eta \to \infty }$ ${\textstyle \beta =1}$

Resumen de algunos resultados de Soft RGG

En el límite de alta densidad para una red con función de conexión exponencial, el número de nodos aislados se distribuye según Poisson, y la red resultante contiene un componente gigante único y solo nodos aislados. ^[9] Por lo tanto, al garantizar que no haya nodos aislados, en el régimen denso, la red también está completamente conectada; similar a los resultados que se muestran en ^[10] para el modelo de disco. A menudo, las propiedades de estas redes, como la centralidad de intermediación ^[11] y la conectividad ^[9], se estudian en el límite como la densidad , lo que a menudo significa que los efectos de borde se vuelven insignificantes. Sin embargo, en la vida real, donde las redes son finitas, aunque aún pueden ser extremadamente densas, los efectos de borde afectarán la conectividad completa; de hecho, ^[12] mostró que para la conectividad completa, con una función de conexión exponencial, se ve muy afectada por los efectos de borde, ya que los nodos cerca de la esquina/cara de un dominio tienen menos probabilidades de conectarse en comparación con los del volumen. Como resultado, la conectividad completa se puede expresar como una suma de las contribuciones del volumen y los límites de las geometrías. Un análisis más general de las funciones de conexión en redes inalámbricas ha demostrado que la probabilidad de conectividad total puede aproximarse bien expresada por unos pocos momentos de la función de conexión y la geometría de las regiones. ^[13] ${\displaystyle \to \infty }$

Referencias

1. Antonioni, Alberto; Tomassini, Marco (28 de septiembre de 2012). "Correlaciones de grado en grafos geométricos aleatorios". Physical Review E . 86 (3): 037101. arXiv : 1207.2573 . Bibcode :2012PhRvE..86c7101A. doi :10.1103/PhysRevE.86.037101. PMID  23031054. S2CID  14750415.
2. Nekovee, Maziar (28 de junio de 2007). "Epidemias de gusanos en redes inalámbricas ad hoc". New Journal of Physics . 9 (6): 189. arXiv : 0707.2293 . Bibcode :2007NJPh....9..189N. doi :10.1088/1367-2630/9/6/189. S2CID  203944.
3. Penrose, Mathew. (2003). Gráficos geométricos aleatorios . Oxford: Oxford University Press. ISBN 0198506260.OCLC 51316118  .
4. von Looz, Moritz; Strash, Darren; Schulz, Christian; Penschuck, Manuel; Sanders, Peter; Meyer, Ulrich; Lamm, Sebastian; Funke, Daniel (2017-10-20). "Generación de grafos distribuidos masivamente sin comunicación". arXiv : 1710.07565v3 [cs.DC].
5. Pérez, Xavier; Mitsche, Dieter; Díaz, Josep (13 de febrero de 2007). "Gráficos geométricos aleatorios dinámicos". arXiv : cs/0702074 .
6. Pérez, X.; Mitsche, D.; Díaz, J. (7 de julio de 2006). "Umbral agudo para hamiltonicidad de grafos geométricos aleatorios". arXiv : cs/0607023 .
7. Christensen, Michael; Dall, Jesper (1 de marzo de 2002). "Gráficos geométricos aleatorios". Physical Review E . 66 (1 Pt 2): 016121. arXiv : cond-mat/0203026 . Código Bibliográfico :2002PhRvE..66a6121D. doi :10.1103/PhysRevE.66.016121. PMID  12241440. S2CID  15193516.
8. Waxman, BM (1988). "Enrutamiento de conexiones multipunto". Revista IEEE sobre áreas seleccionadas en comunicaciones . 6 (9): 1617–1622. doi :10.1109/49.12889.
9. Mao, G; Anderson, BD (2013). "Conectividad de grandes redes inalámbricas bajo un modelo de conexión general". IEEE Transactions on Information Theory . 59 (3): 1761–1772. doi :10.1109/tit.2012.2228894. S2CID  3027610.
10. Penrose, Mathew D (1997). "El borde más largo del árbol de expansión mínimo aleatorio". Anales de probabilidad aplicada : 340361.
11. Giles, Alexander P.; Georgiou, Orestis; Dettmann, Carl P. (2015). "Centralidad de intermediación en redes geométricas aleatorias densas". 2015 IEEE International Conference on Communications (ICC) . pp. 6450–6455. arXiv : 1410.8521 . Código Bibliográfico :2014arXiv1410.8521K. doi :10.1109/ICC.2015.7249352. ISBN: 978-1-4673-6432-4. Número de identificación del sujeto  928409.
12. Coon, J; Dettmann, CP; Georgiou, O (2012). "Conectividad total: esquinas, aristas y caras". Journal of Statistical Physics . 147 (4): 758–778. arXiv : 1201.3123 . Código Bibliográfico :2012JSP...147..758C. doi :10.1007/s10955-012-0493-y. S2CID  18794396.
13. Dettmann, CP; Georgiou, O (2016). "Gráficos geométricos aleatorios con funciones de conexión general". Physical Review E . 93 (3): 032313. arXiv : 1411.3617 . Código Bibliográfico :2016PhRvE..93c2313D. doi :10.1103/physreve.93.032313. PMID  27078372. S2CID  124506496.