Gráfica geométrica aleatoria

Parte de una serie sobre
Ciencia de redes
Teoría
Gráfico Red compleja Contagio Mundo pequeño Sin escala Estructura de la comunidad Filtración Evolución Controlabilidad Dibujo gráfico Capital social Análisis de enlaces Mejoramiento Reciprocidad Cierre Homofilia Transitividad Apego preferencial Teoría del equilibrio Efecto de red Influencia social
Tipos de red
Informativo (informática) Telecomunicación Transporte Social Colaboración científica Biológico Neurona artificial Interdependiente Semántico Espacial Dependencia Fluir en chip
Gráficos
Características Camarilla Componente Cortar Ciclo Estructura de datos Borde Bucle Vecindario Camino Vértice Lista  / matriz de adyacencia Listado  / matriz de incidencias Tipos Bipartito Completo Dirigido Hiper Etiquetado Multi Aleatorio Ponderado
Métrica Algoritmos
Centralidad Grado Motivo Agrupamiento Distribución de grados Asortatividad Distancia Modularidad Eficiencia
Modelos
Topología Gráfico aleatorio Erdős–Rényi Barabási–Albert Bianconi–Barabási Modelo de fitness Watts-Strogatz Aleatorio exponencial (ERGM) Geometría aleatoria (RGG) Hiperbólico (HGN) Jerárquico Bloque estocástico Modelado de bloques Entropía máxima Configuración suave Punto de referencia LFR Dinámica Red booleana basado en agente Epidemia / SIR
Liza Categorías
Temas Software Científicos de redes Categoría:Teoría de redes Categoría:Teoría de grafos
en a mi

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.

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.

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)}$

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.

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.

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})}$

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}}}$

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}$

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}}$

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}$

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 }$