Ver el código de «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:<ref>{{Cita publicación|título=Degree correlations in random geometric graphs|apellidos=Antonioni|nombre=Alberto|apellidos2=Tomassini|nombre2=Marco|fecha=2012-09-28|publicación=Physical Review E|volumen=86|número=3|páginas=037101|bibcode=2012PhRvE..86c7101A|doi=10.1103/PhysRevE.86.037101|pmid=23031054|arxiv=1207.2573}}</ref> 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]].<ref>{{cite journal|title=Worm epidemics in wireless ad hoc networks|last1=Nekovee|first1=Maziar|date=2007-06-28|journal=New Journal of Physics|volume=9|issue=6|pages=189|bibcode=2007NJPh....9..189N|doi=10.1088/1367-2630/9/6/189|arxiv=0707.2293|s2cid=203944}}</ref> Además estas son usadas para realizar puntos de referencia para algoritmos de grafos (externos).

== Definición ==
[[Archivo:Random_Geometric_Graph.gif|alt=|miniaturadeimagen|300x300px|Generación de un grafo geométrico aleatorio para diferentes parámetros de conectividad r.]]
De ahora en adelante {{Math|1=''G'' = (''V'', ''E'')}} denota un [[grafo]] indirecto con un conjunto de vértices V y un conjunto de lados{{Nowrap begin}}{{Math|E ⊆ V × V}}{{Nowrap end}}
Los tamaños del conjunto está denotado por <math>\left \vert V \right \vert = n</math> y <math>\left \vert E \right \vert = m</math>. Adicionalmente, si no es especificado, el espacio métrico <math>[0, 1)^d</math> se considera la [[Distancia euclidiana|distancia euclídea]], por ejemplo, para cualquier punto <math>x, y \in [0, 1)^d</math> la distancia euclídea de x y y se define como

: .<math>d(x, y) = ||x - y||_2 = \sqrt{\sum_{i=1}^d (x_{i} - y_{i})^2}</math>

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 <math>[0, 1)^d</math>.<ref>{{Cite book|title=Random geometric graphs|last=Penrose, Mathew.|date=2003|publisher=Oxford University Press|isbn=0198506260|location=Oxford|oclc=51316118}}</ref> Dos vértices {{Math|p, q ∈ V}} están conectados si y solo sí, su distancia es menos que la previamente especificada mediante el parámetro {{Math|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 <math display="inline">\frac{n(n-1)}{2}</math> posibles conexiones que deben ser verificadas, la complejidad temporal del algoritmo ingenuo es <math display="inline">\Theta(n^2)</math>. Las muestras son generadas usando un [[generador de números aleatorios]] (GNA) en <math>[0, 1)^d</math>. Prácticamente, uno puede implementar esto utilizando generadores de números aleatorios en <math>[0, 1)</math>, 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.<ref name=":02">{{Cite arXiv|last1=von Looz|first1=Moritz|last2=Strash|first2=Darren|last3=Schulz|first3=Christian|last4=Penschuck|first4=Manuel|last5=Sanders|first5=Peter|last6=Meyer|first6=Ulrich|last7=Lamm|first7=Sebastian|last8=Funke|first8=Daniel|date=2017-10-20|title=Communication-free Massively Distributed Graph Generation|class=cs.DC|language=en|eprint=1710.07565v3}}</ref> Este divide un cuadrado de lado 1 en celdas del mismo tamaño de al menos <math>r</math>. Para un número dado <math>P = p^2</math> de procesadores, a cada procesador se le asigna <math display="inline">{k \over p} \times {k \over p}</math> celdas, donde <math display="inline">k = \left \lfloor {1/r} \right \rfloor.</math> Por simplicidad, <math display="inline">P</math> se asume como el cuadrado de un número, pero puede ser generalizado para cualquier número de procesadores. Cada procesador genera <math display="inline">\frac{n}{P}</math> 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 [[Quicksort|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 <math display="inline">O(\frac{n}{P}\log{\frac{n}{P}})</math>. Un límite superior para el costo de comunicación de este algoritmo está dado por <math>T_{all-to-all}(n/P, P) + T_{all-to-all}(1, P) + T_{point-to-point}(n/(k\cdot{P}) + 2)</math>dónde <math>T_{all-to-all}(l, c)</math> denota el tiempo para una comunicación de todos-con-todos con mensajes de longitud {{var|l}} bits con {{var|c}} compañeros de comunicación.

Debido a que este algoritmo no es de comunicación libre, Funke et. al. propusieron<ref name=":04">{{Cite arXiv|last1=von Looz|first1=Moritz|last2=Strash|first2=Darren|last3=Schulz|first3=Christian|last4=Penschuck|first4=Manuel|last5=Sanders|first5=Peter|last6=Meyer|first6=Ulrich|last7=Lamm|first7=Sebastian|last8=Funke|first8=Daniel|date=2017-10-20|title=Communication-free Massively Distributed Graph Generation|class=cs.DC|language=en|eprint=1710.07565v3}}</ref> 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<ref name=":05">{{Cite arXiv|last1=von Looz|first1=Moritz|last2=Strash|first2=Darren|last3=Schulz|first3=Christian|last4=Penschuck|first4=Manuel|last5=Sanders|first5=Peter|last6=Meyer|first6=Ulrich|last7=Lamm|first7=Sebastian|last8=Funke|first8=Daniel|date=2017-10-20|title=Communication-free Massively Distributed Graph Generation|class=cs.DC|language=en|eprint=1710.07565v3}}</ref> es similar a la usada por Holtgrewe: Dividir un cubo de lado unitario en pedazos del mismo tamaño de por lo menos {{var|r}}. En d = 2 serían cuadrados, en d = 3 estos serían cubos. Como  puede encajar  <math display="inline">{\left \lfloor {1/r} \right \rfloor}</math> pedazos por dimensión, es número de pedazos está limitado a <math display="inline">{\left \lfloor {1/r} \right \rfloor}^d</math>. Como antes, a cada procesador se le asigna <math display="inline">{\left \lfloor {1/r} \right \rfloor}^d \over P</math> 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 [[Función hash|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 <math display="inline">O(\frac{m+n}{P} + \log{P})</math>, sin costo de comunicación entre las unidades de procesamiento. 

== Referencias ==
{{listaref}}

{{Control de autoridades}}
[[Categoría:Grafos geométricos]]