Grafon (teoría de grafos)

Un grafón  es un modelo de gráfico aleatorio, una generalización del modelo de Erdős-Rényi . Los grafones surgen naturalmente en el estudio del comportamiento límite de una secuencia de grafos .

Definición

Un grafón es una función medible simétrica .

Un grafón se suele entender como un modelo de un grafo aleatorio según el siguiente esquema:

  1. A cada vértice del gráfico se le asigna un valor aleatorio independiente
  2. Una arista se incluye de forma independiente en el gráfico con probabilidad .

El modelo basado en grafón a veces se denota como , por analogía con el modelo de gráfico aleatorio de Erdős-Rényi . Una gráfica creada a partir de un grafón de esta manera se llama gráfica aleatoria.

Ejemplos

El ejemplo más simple de un grafón: para alguna constante . En este caso, el modelo de sustitución asociado del grafo aleatorio es el modelo de Erdős-Rényi que incluye cada arista de forma independiente con probabilidad .

Si en cambio comenzamos con un grafón constante por partes:

  1. división del cuadrado unitario en bloques y
  2. parámetro igual al bloque,

entonces el modelo de gráfico aleatorio resultante es una generalización de bloques estocásticos del modelo de Erdős-Rényi. Podemos interpretarlo como un modelo de gráfico aleatorio que consta de diferentes gráficos de Erdős-Rényi con parámetros respectivamente, con bígrafos entre ellos, donde cada borde posible entre bloques y también se incluye de forma independiente con probabilidad .

Un grafón puede definir muchos otros modelos de gráficos aleatorios. [una]

Conceptos de convergencia

Hay muchas maneras diferentes de medir la distancia entre dos gráficos. Si estamos interesados ​​en métricas que preservan las propiedades extremas de los gráficos, entonces debemos limitar nuestra atención a las métricas que identifican gráficos aleatorios como cercanos. Por ejemplo, si construimos aleatoriamente dos gráficos de forma independiente usando el modelo de Erdős-Rényi para un valor fijo , entonces la distancia entre estos dos gráficos para una métrica razonable debe ser cercana a cero con una alta probabilidad de que sea grande .

En este sentido, hay dos métricas naturales que funcionan bien en gráficos aleatorios. La primera es la métrica de muestreo, que dice que dos gráficos están cerca si sus distribuciones de subgráficos están cerca. La segunda es la métrica de divergencia de borde, que dice que dos gráficos están cerca cuando sus densidades de borde están cerca en todos sus subconjuntos de vértices correspondientes.

Milagrosamente, una sucesión de gráficas converge con respecto a una distancia si, y sólo si, converge con respecto a otra. Además, los objetos límite en ambas métricas resultan ser grafones. La equivalencia de estas dos nociones de convergencia refleja la equivalencia de diferentes nociones de grafos cuasi-aleatorios. [2]

Literatura

  1. ↑ Orbanz, P. (2015). “Modelos bayesianos de grafos, matrices y otras estructuras aleatorias intercambiables”. Transacciones IEEE sobre análisis de patrones e inteligencia artificial . 37 (2): 437-461. arXiv : 1312.7857 . DOI : 10.1109/tpami.2014.2334607 . PMID  26353253 .
  2. ↑ Chung, Fan RK ; Graham, Ronald L .; Wilson, RM (1989). “Gráficos cuasi aleatorios” . Combinatoria . 9 (4): 345-362. DOI : 10.1007/BF02125347 .