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:​ 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.​. Además estas son usadas para realizar puntos de referencia para algoritmos de grafos (externos).

Definición

Generación de un grafo geométrico aleatorio para diferentes parámetros de conectividad r.

De ahora en adelante G = (V, E) denota un grafo indirecto con un conjunto de vértices V y un conjunto de lados E ⊆ V × V Los tamaños del conjunto está denotado por $\left\vert V\right\vert =n$ y $\left\vert E\right\vert =m$. Adicionalmente, si no es especificado, el espacio métrico $[0,1)^{d}$ se considera la distancia euclídea, por ejemplo, para cualquier punto $x,y\in [0,1)^{d}$ la distancia euclídea de x y y se define como

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

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 $[0,1)^{d}$​. 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.

Algoritmos

Algoritmo ingenuo

La aproximación ingenua consiste en calcular la distancia de cada vértice a cada vértice. Debido a que hay ${\textstyle {\frac {n(n-1)}{2}}}$ posibles conexiones que deben ser verificadas, la complejidad temporal del algoritmo ingenuo es ${\textstyle \Theta (n^{2})}$. Las muestras son generadas usando un generador de números aleatorios (GNA) en $[0,1)^{d}$. Prácticamente, uno puede implementar esto utilizando generadores de números aleatorios en $[0,1)$, un GNA para cada dimensión

Pseudocódigo

V := generateSamples(n)  // Genera n muestras en el cubo unitario.
for each p ∈ V do
    for each q ∈ V\{p} do
        if distance(p, q) ≤ r then
            addConnection(p, q) // Añadir el lado (p,q) a cada lado de la estructura de dato.
        end if
    end for
end for

Dado que este algoritmo no es escalable (cada vértice necesita información de cada uno de los otros vértices), Holtgrewe et al. y Funke et al. presentaron nuevos algoritmos para este problema.

Algoritmos distribuidos

Holtgrewe et al.

Este algoritmo, que fue propuesto por Holtgrewe et al., fue el primer algoritmo generador distribuido GGA para dimensión 2​. Este divide un cuadrado de lado 1 en celdas del mismo tamaño de al menos $r$. Para un número dado $P=p^{2}$ de procesadores, a cada procesador se le asigna ${\textstyle {k \over p}\times {k \over p}}$ celdas, donde ${\textstyle k=\left\lfloor {1/r}\right\rfloor .}$ Por simplicidad, ${\textstyle P}$ se asume como el cuadrado de un número, pero puede ser generalizado para cualquier número de procesadores. Cada procesador genera ${\textstyle {\frac {n}{P}}}$ 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. El tiempo de ejecución esperado es de ${\textstyle O({\frac {n}{P}}\log {\frac {n}{P}})}$. Un límite superior para el costo de comunicación de este algoritmo está dado por $T_{all-to-all}(n/P,P)+T_{all-to-all}(1,P)+T_{point-to-point}(n/(k\cdot {P})+2)$dónde $T_{all-to-all}(l,c)$ denota el tiempo para una comunicación de todos-con-todos con mensajes de longitud l bits con c compañeros de comunicación.

Debido a que este algoritmo no es de comunicación libre, Funke et. al. propusieron​ un GGA generador para altas dimensiones, que funciona sin comunicación entre las unidades procesadoras.

Funke et al.

La aproximación utilizada en este algoritmo​ 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 puede encajar ${\textstyle {\left\lfloor {1/r}\right\rfloor }}$ pedazos por dimensión, es número de pedazos está limitado a ${\textstyle {\left\lfloor {1/r}\right\rfloor }^{d}}$. Como antes, a cada procesador se le asigna ${\textstyle {\left\lfloor {1/r}\right\rfloor }^{d} \over P}$ pedazos. 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 ${\textstyle O({\frac {m+n}{P}}+\log {P})}$, sin costo de comunicación entre las unidades de procesamiento.

Referencias

• Datos: Q7291969