Grafo geométrico aleatorio
En teoría de grafos, un grafo geométrico aleatorio (GGA) es la red espacial matemáticas más simple, nombrada como un grafo indirecto construido colocando aleatoriamente N nodos en algún espacio métrico (de acuerdo a una distribución de probabilidad especificada) y conectando dos nodos mediante un enlace si y solo si su distancia se encuentra en cierto rango, por ejemplo, más pequeña que cierto radio de un vecino, r. Los grafos aleatorios geométricos se parecen a las redes sociales humanas en muchos aspectos.
Es por esto, que muestran espontáneamente una estructura de comunidad - grupos de nodos con alta modularidad.
Otros algoritmos de generación de gráficos aleatorios, como aquellos generando el modelo Erdős–Rényi o el modelo Barabási–Albert (BA) no crean este tipo de estructura.
Adicionalmente, los grafos geométricos aleatorios muestran grados de variedad de acuerdo a su dimensión espacial:[1] nodos "populares" (aquellos con muchos enlaces) están particularmente ligados a otros nodos populares.
Una aplicación del mundo real de los GGA consiste en el modelamiento de las redes ad hoc.
[2] Además estas son usadas para realizar puntos de referencia para algoritmos de grafos (externos).
De ahora en adelante G = (V, E) denota un grafo indirecto con un conjunto de vértices V y un conjunto de lados
Los tamaños del conjunto está denotado por
Adicionalmente, si no es especificado, el espacio métrico
se considera la distancia euclídea, por ejemplo, para cualquier punto
la distancia euclídea de x y y se define como Un grafo geométrico aleatorio (GGA) es un grafo geométrico no direccionado con nodos aleatoriamente muestreados a partir de una distribución uniforme en un espacio subyacente
[3] Dos vértices p, q ∈ V están conectados si y solo sí, su distancia es menos que la previamente especificada mediante el parámetro r ∈ (0,1), excluyendo cualquier bucle.
Así, los parámetros r y n carateriza íntegramente a una GGA.
posibles conexiones que deben ser verificadas, la complejidad temporal del algoritmo ingenuo es
Prácticamente, uno puede implementar esto utilizando generadores de números aleatorios en
, un GNA para cada dimensión Dado que este algoritmo no es escalable (cada vértice necesita información de cada uno de los otros vértices), Holtgrewe et al.
presentaron nuevos algoritmos para este problema.
Este algoritmo, que fue propuesto por Holtgrewe et al., fue el primer algoritmo generador distribuido GGA para dimensión 2.
[4] Este divide un cuadrado de lado 1 en celdas del mismo tamaño de al menos
se asume como el cuadrado de un número, pero puede ser generalizado para cualquier número de procesadores.
vértices, que son distribuidos a sus respectivos propietarios.
Entonces, los vértices son ordenados bajo el criterio del número de celda asignado, por ejemplo con el algoritmo de ordenamiento rápido.
Luego, cada procesador envia información a sus procesadores adyacentes acerca de los vértices en las células que están en los bordes, de modo que cada una de estas unidades procesadoras puede calcular los lados en su partición independientemente de otras unidades.
Debido a que este algoritmo no es de comunicación libre, Funke et.
propusieron[5] un GGA generador para altas dimensiones, que funciona sin comunicación entre las unidades procesadoras.
La aproximación utilizada en este algoritmo[6] es similar a la usada por Holtgrewe: Dividir un cubo de lado unitario en pedazos del mismo tamaño de por lo menos r. En d = 2 serían cuadrados, en d = 3 estos serían cubos.
Como antes, a cada procesador se le asigna
Para lograr un proceso libre de comunicación, cada procesador debe generar la misma cantidad de vértices en los pedazos adyacentes explotando la pseudoaleatoriedad de funciones hash con semillas.
De este modo, cada procesador calcula la misma cantidad de vértices y no hay necesidad de intercambiar información con las esquinas Para la dimensión 3, Funke et al.
mostraron que el tiempo de ejecución esperado es
