Gráfico geométrico aleatorio

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

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

En el caso especial que${\textstyle d=2}$, la probabilidad de que un único vértice esté aislado en un RGG es${\textstyle (1-\pi r^{2})^{n-1}}$. ^{[ 7 ]} Deje${\textstyle X}$Sea la variable aleatoria que cuenta cuántos vértices están aislados. Entonces, el valor esperado de${\textstyle X}$es${\textstyle E(X)=n(1-\pi r^{2})^{n-1}=ne^{-\pi r^{2}n}-O(r^{4}n)}$. El término${\textstyle \mu =ne^{-\pi r^{2}n}}$proporciona información sobre la conectividad del RGG. Para${\textstyle \mu \longrightarrow 0}$, el RGG es asintóticamente casi seguramente conectado. Para${\displaystyle \mu \longrightarrow \infty }$, el RGG es asintóticamente casi seguramente desconectado. Y para${\textstyle \mu =\Theta (1)}$, el RGG tiene un componente gigante que cubre más de${\textstyle {\frac {n}{2}}}$vértices y${\displaystyle X}$es una distribución de Poisson con parámetro${\displaystyle \mu }$. De ello se deduce que si${\textstyle \mu =\Theta (1)}$, la probabilidad de que el RGG esté conectado es${\textstyle P[X=0]\sim e^{-\mu }}$y la probabilidad de que el RGG no esté conectado es${\textstyle P[X>0]\sim 1-e^{-\mu }}$.

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

Se ha demostrado que, en el caso bidimensional, el umbral${\textstyle r\sim {\sqrt {\ln(n) \over \pi n}}}$También proporciona información sobre la existencia de un ciclo hamiltoniano ( Camino hamiltoniano ). ^{[ 8 ]} Para cualquier${\displaystyle \epsilon >0}$, si${\textstyle r\sim {\sqrt {\ln(n) \over (\pi +\epsilon )n}}}$, entonces el RGG asintóticamente casi seguramente no tiene ciclo hamiltoniano y si${\textstyle r\sim {\sqrt {\ln(n) \over (\pi -\epsilon )n}}}$para cualquier${\textstyle \epsilon >0}$, entonces el RGG tiene asintóticamente casi con seguridad un ciclo hamiltoniano.

El coeficiente de agrupamiento de RGGs solo depende de la dimensión d del espacio subyacente [ 0,1) ^d . El coeficiente de agrupamiento es ^{[ 9 ]}

${\textstyle C_{d}=1-H_{d}(1)}$incluso${\displaystyle d}$y${\textstyle C_{d}={3 \over 2}-H_{d}({1 \over 2})}$para impar${\displaystyle d}$dónde$${\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}}}$$Para grandes${\displaystyle d}$, esto se simplifica a${\displaystyle C_{d}\sim 3{\sqrt {2 \over \pi d}}\left({3 \over 4}\right)^{d+1 \over 2}}$.

En el límite de alta densidad para una red con función de conexión exponencial, el número de nodos aislados sigue una distribución de Poisson, y la red resultante contiene un único componente gigante y solo nodos aislados. ^{[ 11 ]} Por lo tanto, al asegurar que no haya nodos aislados, en el régimen denso, la red está completamente conectada; similar a los resultados mostrados en ^{[ 12 ]} para el modelo de disco. A menudo, las propiedades de estas redes, como la centralidad de intermediación ^{[ 13 ]} y la conectividad ^{[ 11 ],} se estudian en el límite de densidad.${\displaystyle \to \infty }$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 pueden ser extremadamente densas, los efectos de borde impactarán en la conectividad total; de hecho, ^{[ 14 ]} demostró que para la conectividad total, con una función de conexión exponencial, los efectos de borde se ven muy afectados, ya que los nodos cerca de la esquina/cara de un dominio tienen menos probabilidades de conectarse en comparación con los del interior. Como resultado, la conectividad total puede expresarse como una suma de las contribuciones del interior y los límites geométricos. 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. ^{[ 15 ]}