Grafón

Una realización de un gráfico aleatorio intercambiable definido por un grafón . El grafón se muestra como un mapa de calor magenta (abajo a la derecha). Se genera un gráfico aleatorio de tamaño asignando de forma independiente a cada vértice una variable aleatoria latente (valores a lo largo del eje vertical) e incluyendo cada arista de forma independiente con probabilidad . Por ejemplo, la arista (verde, punteada) está presente con probabilidad ; los cuadros verdes en el cuadrado de la derecha representan los valores de y . El panel superior izquierdo muestra la realización del gráfico como una matriz de adyacencia. ${\displaystyle n}$ ${\displaystyle k\in \{1,\dotsc ,n\}}$ ${\displaystyle U_{k}\sim \mathrm {U} (0,1)}$ ${\displaystyle (k,\ell )}$ ${\displaystyle f(U_{k},U_{\ell })}$ ${\displaystyle (3,5)}$ ${\displaystyle f(0.72,0.9)}$ ${\displaystyle (u_{3},u_{5})}$ ${\displaystyle (u_{5},u_{3})}$

En teoría de grafos y estadística , un grafón (también conocido como límite de grafo ) es una función medible simétrica , que es importante en el estudio de grafos densos . Los grafones surgen tanto como una noción natural para el límite de una secuencia de grafos densos, como los objetos definitorios fundamentales de los modelos de grafos aleatorios intercambiables . Los grafones están vinculados a los grafos densos por el siguiente par de observaciones: los modelos de grafos aleatorios definidos por grafones dan lugar a grafos densos casi con seguridad y, por el lema de regularidad , los grafones capturan la estructura de grafos densos arbitrarios grandes. ${\displaystyle W:[0,1]^{2}\to [0,1]}$

Formulación estadística

Un grafón es una función medible simétrica . Por lo general, se entiende que un grafón define un modelo de gráfico aleatorio intercambiable según el siguiente esquema: ${\displaystyle W:[0,1]^{2}\to [0,1]}$

1. A cada vértice del gráfico se le asigna un valor aleatorio independiente ${\displaystyle j}$ ${\displaystyle u_{j}\sim U[0,1]}$
2. Edge se incluye independientemente en el gráfico con probabilidad . ${\displaystyle (i,j)}$ ${\displaystyle W(u_{i},u_{j})}$

Un modelo de grafo aleatorio es un modelo de grafo aleatorio intercambiable si y solo si puede definirse en términos de un grafo (posiblemente aleatorio) de esta manera. El modelo basado en un grafo fijo a veces se denota , por analogía con el modelo de Erdős–Rényi de grafos aleatorios. Un grafo generado a partir de un grafo de esta manera se llama grafo -aleatorio. ${\displaystyle W}$ ${\displaystyle \mathbb {G} (n,W)}$ ${\displaystyle W}$ ${\displaystyle W}$

De esta definición y de la ley de los grandes números se desprende que, si , los modelos de gráficos aleatorios intercambiables son densos casi con toda seguridad. ^[1] ${\displaystyle W\neq 0}$

Ejemplos

El ejemplo más simple de un grafón es el de una constante . En este caso, el modelo de grafo aleatorio intercambiable asociado es el modelo de Erdős–Rényi , que incluye cada arista de forma independiente con probabilidad . ${\displaystyle W(x,y)\equiv p}$ ${\displaystyle p\in [0,1]}$ ${\displaystyle G(n,p)}$ ${\displaystyle p}$

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

1. dividiendo el cuadrado unitario en bloques, y ${\displaystyle k\times k}$
2. Ajuste igual a en el bloque, ${\displaystyle W}$ ${\displaystyle p_{lm}}$ ${\displaystyle (\ell ,m)^{\text{th}}}$

El modelo de gráfico aleatorio intercambiable resultante es el modelo de bloque estocástico comunitario , una generalización del modelo de Erdős–Rényi. Podemos interpretarlo como un modelo de gráfico aleatorio que consta de distintos gráficos de Erdős–Rényi con parámetros respectivamente, con bigrafos entre ellos donde cada posible borde entre bloques y se incluye de forma independiente con probabilidad . ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle p_{\ell \ell }}$ ${\displaystyle (\ell ,\ell )}$ ${\displaystyle (m,m)}$ ${\displaystyle p_{\ell m}}$

Muchos otros modelos de gráficos aleatorios populares pueden entenderse como modelos de gráficos aleatorios intercambiables definidos por algún grafón; se incluye un estudio detallado en Orbanz y Roy. ^[1]

Matrices de adyacencia intercambiables conjuntamente

Un gráfico aleatorio de tamaño puede representarse como una matriz de adyacencia aleatoria . Para imponer consistencia (en el sentido de proyectividad) entre gráficos aleatorios de diferentes tamaños, es natural estudiar la secuencia de matrices de adyacencia que surgen como submatrices superiores izquierdas de algún arreglo infinito de variables aleatorias; esto nos permite generar agregando un nodo a y muestreando los bordes para . Con esta perspectiva, los gráficos aleatorios se definen como arreglos simétricos infinitos aleatorios . ${\displaystyle n}$ ${\displaystyle n\times n}$ ${\displaystyle n\times n}$ ${\displaystyle G_{n}}$ ${\displaystyle G_{n-1}}$ ${\displaystyle (j,n)}$ ${\displaystyle j<n}$ ${\displaystyle (X_{ij})}$

Siguiendo la importancia fundamental de las secuencias intercambiables en la probabilidad clásica, es natural buscar una noción análoga en el contexto de los gráficos aleatorios. Una de esas nociones está dada por las matrices intercambiables conjuntamente; es decir, matrices aleatorias que satisfacen

${\displaystyle (X_{ij})\ {\overset {d}{=}}\,(X_{\sigma (i)\sigma (j)})}$

para todas las permutaciones de los números naturales, donde las medias son iguales en distribución . Intuitivamente, esta condición significa que la distribución del grafo aleatorio no cambia con un reetiquetado de sus vértices: es decir, las etiquetas de los vértices no contienen información. ${\displaystyle \sigma }$ ${\displaystyle {\overset {d}{=}}}$

Existe un teorema de representación para matrices de adyacencia aleatorias intercambiables de forma conjunta, análogo al teorema de representación de De Finetti para secuencias intercambiables. Este es un caso especial del teorema de Aldous-Hoover para matrices intercambiables de forma conjunta y, en este contexto, afirma que la matriz aleatoria se genera mediante: ${\displaystyle (X_{ij})}$

1. Muestrear de forma independiente ${\displaystyle u_{j}\sim U[0,1]}$
2. ${\displaystyle X_{ij}=X_{ji}=1}$independientemente al azar con probabilidad ${\displaystyle W(u_{i},u_{j}),}$

donde es un grafón (posiblemente aleatorio). Es decir, un modelo de grafo aleatorio tiene una matriz de adyacencia intercambiable conjuntamente si y solo si es un modelo de grafo aleatorio intercambiable conjuntamente definido en términos de algún grafón. ${\displaystyle W:[0,1]^{2}\to [0,1]}$

Estimación de grafones

Debido a problemas de identificabilidad, es imposible estimar ni la función de grafo ni las posiciones latentes de los nodos y hay dos direcciones principales de estimación de grafones. Una dirección apunta a estimar hasta una clase de equivalencia, ^{[2] [3]} o estimar la matriz de probabilidad inducida por . ^{[4] [5]} ${\displaystyle W}$ ${\displaystyle u_{i},}$ ${\displaystyle W}$ ${\displaystyle W}$

Formulación analítica

Cualquier grafo sobre vértices puede identificarse con su matriz de adyacencia . Esta matriz corresponde a una función escalonada , definida por la partición en intervalos tales que tiene interior y para cada , fijando igual a la entrada de . Esta función es el grafón asociado del grafo . ${\displaystyle n}$ ${\displaystyle \{1,2,\dots ,n\}}$ ${\displaystyle A_{G}}$ ${\displaystyle W_{G}:[0,1]^{2}\to [0,1]}$ ${\displaystyle [0,1]}$ ${\displaystyle I_{1},I_{2},\dots ,I_{n}}$ ${\displaystyle I_{j}}$ $${\displaystyle \left({\frac {j-1}{n}},{\frac {j}{n}}\right)}$$ ${\displaystyle (x,y)\in I_{i}\times I_{j}}$ ${\displaystyle W_{G}(x,y)}$ ${\displaystyle (i,j)^{\text{th}}}$ ${\displaystyle A_{G}}$ ${\displaystyle W_{G}}$ ${\displaystyle G}$

En general, si tenemos una secuencia de grafos donde el número de vértices de tiende a infinito, podemos analizar el comportamiento límite de la secuencia considerando el comportamiento límite de las funciones . Si estos grafos convergen (según alguna definición adecuada de convergencia ), entonces esperamos que el límite de estos grafos corresponda al límite de estas funciones asociadas. ${\displaystyle (G_{n})}$ ${\displaystyle G_{n}}$ ${\displaystyle (W_{G_{n}})}$

Esto motiva la definición de un grafón (abreviatura de "función gráfica") como una función medible simétrica que captura la noción de un límite de una secuencia de grafos. Resulta que para secuencias de grafos densos, varias nociones aparentemente distintas de convergencia son equivalentes y bajo todas ellas el objeto límite natural es un grafón. ^[6] ${\displaystyle W:[0,1]^{2}\to [0,1]}$

Ejemplos

Grafón constante

Tomemos una secuencia de grafos aleatorios de Erdős–Rényi con algún parámetro fijo . Intuitivamente, como tiende al infinito, el límite de esta secuencia de grafos está determinado únicamente por la densidad de aristas de estos grafos. En el espacio de grafones, resulta que dicha secuencia converge casi con seguridad a la constante , lo que captura la intuición anterior. ${\displaystyle (G_{n})}$ ${\displaystyle G_{n}=G(n,p)}$ ${\displaystyle p}$ ${\displaystyle n}$ ${\displaystyle W(x,y)\equiv p}$

Medio grafo

Tomemos la secuencia de semigrafos , definida al tomar como el grafo bipartito en vértices y tal que es adyacente a precisamente cuando . Si los vértices se enumeran en el orden presentado, entonces la matriz de adyacencia tiene dos esquinas de matrices de bloques de "medio cuadrado" llenas de unos, con el resto de las entradas iguales a cero. Por ejemplo, la matriz de adyacencia de está dada por ${\displaystyle (H_{n})}$ ${\displaystyle H_{n}}$ ${\displaystyle 2n}$ ${\displaystyle u_{1},u_{2},\dots ,u_{n}}$ ${\displaystyle v_{1},v_{2},\dots ,v_{n}}$ ${\displaystyle u_{i}}$ ${\displaystyle v_{j}}$ ${\displaystyle i\leq j}$ ${\displaystyle A_{H_{n}}}$ ${\displaystyle H_{3}}$

$${\displaystyle {\begin{bmatrix}0&0&0&1&1&1\\0&0&0&0&1&1\\0&0&0&0&0&1\\1&0&0&0&0&0\\1&1&0&0&0&0\\1&1&1&0&0&0\end{bmatrix}}.}$$

A medida que se hace más grande, estos vértices se "suavizan". Siguiendo esta intuición, la secuencia converge al semigrafo definido por cuándo y de otra manera. ${\displaystyle n}$ ${\displaystyle (H_{n})}$ ${\displaystyle W}$ ${\displaystyle W(x,y)=1}$ ${\displaystyle |x-y|\geq 1/2}$ ${\displaystyle W(x,y)=0}$

Grafón bipartito completo

Tomemos la secuencia de grafos bipartitos completos con partes de igual tamaño. Si ordenamos los vértices colocando todos los vértices de una parte al principio y colocando los vértices de la otra parte al final, la matriz de adyacencia de parece una matriz de bloques fuera de la diagonal, con dos bloques de unos y dos bloques de ceros. Por ejemplo, la matriz de adyacencia de está dada por ${\displaystyle (K_{n,n})}$ ${\displaystyle (K_{n,n})}$ ${\displaystyle K_{2,2}}$

$${\displaystyle {\begin{bmatrix}0&0&1&1\\0&0&1&1\\1&1&0&0\\1&1&0&0\end{bmatrix}}.}$$

A medida que se hace más grande, esta estructura de bloques de la matriz de adyacencia permanece constante, de modo que esta secuencia de gráficos converge a un grafón "bipartito completo" definido por siempre que y , y estableciendo en caso contrario. ${\displaystyle n}$ ${\displaystyle W}$ ${\displaystyle W(x,y)=1}$ ${\displaystyle \min(x,y)\leq 1/2}$ ${\displaystyle \max(x,y)>1/2}$ ${\displaystyle W(x,y)=0}$

Si, en cambio, ordenamos los vértices de alternando entre las partes, la matriz de adyacencia tiene una estructura de tablero de ajedrez de ceros y unos. Por ejemplo, bajo este ordenamiento, la matriz de adyacencia de está dada por ${\displaystyle K_{n,n}}$ ${\displaystyle K_{2,2}}$

$${\displaystyle {\begin{bmatrix}0&1&0&1\\1&0&1&0\\0&1&0&1\\1&0&1&0\end{bmatrix}}.}$$

A medida que se hace más grande, las matrices de adyacencia se convierten en un tablero de ajedrez cada vez más fino. A pesar de este comportamiento, todavía queremos que el límite de sea único y dé como resultado el grafón del ejemplo 3. Esto significa que cuando definimos formalmente la convergencia para una secuencia de grafos, la definición de un límite debe ser independiente de los reetiquetados de los vértices. ${\displaystyle n}$ ${\displaystyle (K_{n,n})}$

Límite de gráficos W-aleatorios

Tome una secuencia aleatoria de W {\displaystyle W} -grafos aleatorios dibujando para algún grafo fijo . Entonces, tal como en el primer ejemplo de esta sección, resulta que converge a casi con seguridad. ${\displaystyle (G_{n})}$ ${\displaystyle G_{n}\sim \mathbb {G} (n,W)}$ ${\displaystyle W}$ ${\displaystyle (G_{n})}$ ${\displaystyle W}$

Recuperación de parámetros gráficos a partir de grafones

Dado un grafo con grafona asociada , podemos recuperar las propiedades y parámetros de la teoría de grafos mediante la integración de transformaciones de . Por ejemplo, la densidad de aristas (es decir, el grado promedio dividido por el número de vértices) de está dada por la integral Esto se debe a que tiene un valor de , y cada arista en corresponde a una región de área donde es igual a . ${\displaystyle G}$ ${\displaystyle W=W_{G}}$ ${\displaystyle G}$ ${\displaystyle W}$ ${\displaystyle G}$ $${\displaystyle \int _{0}^{1}\int _{0}^{1}W(x,y)\;\mathrm {d} x\,\mathrm {d} y.}$$ ${\displaystyle W}$ ${\displaystyle \{0,1\}}$ ${\displaystyle (i,j)}$ ${\displaystyle G}$ ${\displaystyle I_{i}\times I_{j}}$ ${\displaystyle 1/n^{2}}$ ${\displaystyle W}$ ${\displaystyle 1}$

Un razonamiento similar muestra que la densidad de triángulos en es igual a ${\displaystyle G}$ $${\displaystyle {\frac {1}{6}}\int _{0}^{1}\int _{0}^{1}\int _{0}^{1}W(x,y)W(y,z)W(z,x)\;\mathrm {d} x\,\mathrm {d} y\,\mathrm {d} z.}$$

Nociones de convergencia

Existen muchas formas diferentes de medir la distancia entre dos grafos. Si nos interesan las métricas que "conservan" las propiedades extremales de los grafos, entonces deberíamos restringir nuestra atención a las métricas que identifican grafos aleatorios como similares. Por ejemplo, si extraemos aleatoriamente dos grafos de forma independiente a partir de un modelo de Erdős–Rényi para algún , la distancia entre estos dos grafos bajo una métrica "razonable" debería ser cercana a cero con alta probabilidad para . ${\displaystyle G(n,p)}$ ${\displaystyle p}$ ${\displaystyle n}$

De manera ingenua, dados dos gráficos en el mismo conjunto de vértices, se podría definir su distancia como la cantidad de aristas que se deben agregar o quitar para llegar de un gráfico al otro, es decir, su distancia de edición . Sin embargo, la distancia de edición no identifica gráficos aleatorios como similares; de hecho, dos gráficos dibujados independientemente de tienen una distancia de edición esperada (normalizada) de . ${\displaystyle G(n,{\tfrac {1}{2}})}$ ${\displaystyle {\tfrac {1}{2}}}$

Hay dos métricas naturales que se comportan bien en gráficos aleatorios densos en el sentido que queremos. La primera es una métrica de muestreo, que dice que dos gráficos están cerca si sus distribuciones de subgráficos son cercanas. La segunda es una métrica de discrepancia de aristas , que dice que dos gráficos están cerca cuando sus densidades de aristas son cercanas en todos sus subconjuntos correspondientes de vértices.

Milagrosamente, una secuencia de grafos converge con respecto a una métrica precisamente cuando converge con respecto a la otra. Además, los objetos límite bajo ambas métricas resultan ser grafones. La equivalencia de estas dos nociones de convergencia refleja cómo son equivalentes varias nociones de grafos cuasialeatorios . ^[7]

Densidades de homomorfismo

Una forma de medir la distancia entre dos grafos y es comparar sus recuentos relativos de subgrafos. Es decir, para cada grafo podemos comparar el número de copias de en y en . Si estos números son cercanos para cada grafo , entonces intuitivamente y son grafos de apariencia similar. Sin embargo, en lugar de tratar directamente con subgrafos, resulta más fácil trabajar con homomorfismos de grafos. Esto está bien cuando se trata con grafos grandes y densos, ya que en este escenario el número de subgrafos y el número de homomorfismos de grafos de un grafo fijo son asintóticamente iguales. ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle F}$ ${\displaystyle F}$ ${\displaystyle G}$ ${\displaystyle F}$ ${\displaystyle H}$ ${\displaystyle F}$ ${\displaystyle G}$ ${\displaystyle H}$

Dados dos grafos y , la densidad de homomorfismos de en se define como el número de homomorfismos de grafos de a . En otras palabras, es la probabilidad de que una función elegida aleatoriamente de los vértices de a los vértices de envíe vértices adyacentes en a vértices adyacentes en . ${\displaystyle F}$ ${\displaystyle G}$ ${\displaystyle t(F,G)}$ ${\displaystyle F}$ ${\displaystyle G}$ ${\displaystyle F}$ ${\displaystyle G}$ ${\displaystyle t(F,G)}$ ${\displaystyle F}$ ${\displaystyle G}$ ${\displaystyle F}$ ${\displaystyle G}$

Los grafones ofrecen una forma sencilla de calcular densidades de homomorfismo. De hecho, dado un grafo con un grafón asociado y otro , tenemos ${\displaystyle G}$ ${\displaystyle W_{G}}$ ${\displaystyle F}$

$${\displaystyle t(F,G)=\int \prod _{(i,j)\in E(F)}W_{G}(x_{i},x_{j})\;\left\{\mathrm {d} x_{i}\right\}_{i\in V(F)}}$$

donde la integral es multidimensional, tomada sobre el hipercubo unitario . Esto se desprende de la definición de un grafón asociado, considerando cuando el integrando anterior es igual a . Luego podemos extender la definición de densidad de homomorfismo a grafones arbitrarios , utilizando la misma integral y definiendo ${\displaystyle [0,1]^{V(F)}}$ ${\displaystyle 1}$ ${\displaystyle W}$

$${\displaystyle t(F,W)=\int \prod _{(i,j)\in E(F)}W(x_{i},x_{j})\;\left\{\mathrm {d} x_{i}\right\}_{i\in V(F)}}$$

para cualquier gráfico . ${\displaystyle F}$

Dada esta configuración, decimos que una secuencia de grafos es convergente por la izquierda si para cada grafo fijo , la secuencia de densidades de homomorfismo converge. Aunque no es evidente a partir de la definición sola, si converge en este sentido, entonces siempre existe un grafón tal que para cada grafo , tenemos simultáneamente. ${\displaystyle (G_{n})}$ ${\displaystyle F}$ ${\displaystyle \left(t(F,G_{n})\right)}$ ${\displaystyle (G_{n})}$ ${\displaystyle W}$ ${\displaystyle F}$ $${\displaystyle \lim _{n\to \infty }t(F,G_{n})=t(F,W)}$$

Distancia de corte

Tomemos dos grafos y en el mismo conjunto de vértices. Debido a que estos grafos comparten los mismos vértices, una forma de medir su distancia es restringirlos a subconjuntos del conjunto de vértices y, para cada par de subconjuntos, comparar la cantidad de aristas de a en con la cantidad de aristas entre y en . Si estos números son similares para cada par de subconjuntos (en relación con la cantidad total de vértices), entonces eso sugiere que y son grafos similares. ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle X,Y}$ ${\displaystyle e_{G}(X,Y)}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle G}$ ${\displaystyle e_{H}(X,Y)}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle H}$

Como formalización preliminar de esta noción de distancia, para cualquier par de grafos y en el mismo conjunto de vértices de tamaño , definamos la distancia de corte etiquetada entre y como ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle V}$ ${\displaystyle |V|=n}$ ${\displaystyle G}$ ${\displaystyle H}$

$${\displaystyle d_{\square }(G,H)={\frac {1}{n^{2}}}\max _{X,Y\subseteq V}\left|e_{G}(X,Y)-e_{H}(X,Y)\right|.}$$

En otras palabras, la distancia de corte etiquetada codifica la discrepancia máxima de las densidades de aristas entre y . Podemos generalizar este concepto a los grafones expresando la densidad de aristas en términos del grafón asociado , dando la igualdad ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle {\tfrac {1}{n^{2}}}e_{G}(X,Y)}$ ${\displaystyle W_{G}}$

$${\displaystyle d_{\square }(G,H)=\max _{X,Y\subseteq V}\left|\int _{I_{X}}\int _{I_{Y}}W_{G}(x,y)-W_{H}(x,y)\;\mathrm {d} x\,\mathrm {d} y\right|}$$

donde son uniones de intervalos correspondientes a los vértices en y . Nótese que esta definición puede seguir utilizándose incluso cuando los gráficos que se comparan no comparten un conjunto de vértices. Esto motiva la siguiente definición más general. ${\displaystyle I_{X},I_{Y}\subseteq [0,1]}$ ${\displaystyle X}$ ${\displaystyle Y}$

Definición 1. Para cualquier función simétrica y medible , defina la norma de corte de como la cantidad ${\displaystyle f:[0,1]^{2}\to \mathbb {R} }$ ${\displaystyle f}$

$${\displaystyle \lVert f\rVert _{\square }=\sup _{S,T\subseteq [0,1]}\left|\int _{S}\int _{T}f(x,y)\;\mathrm {d} x\,\mathrm {d} y\right|}$$se hace cargo de todos los subconjuntos mensurables del intervalo unitario. ^[6] ${\displaystyle S,T}$

Esto captura nuestra noción anterior de distancia de corte etiquetada, ya que tenemos la igualdad . ${\displaystyle \lVert W_{G}-W_{H}\rVert _{\square }=d_{\square }(G,H)}$

Esta medida de distancia aún tiene una limitación importante: puede asignar una distancia distinta de cero a dos grafos isomorfos. Para asegurarnos de que los grafos isomorfos tengan una distancia cero, debemos calcular la norma de corte mínima sobre todos los posibles "reetiquetados" de los vértices. Esto motiva la siguiente definición de la distancia de corte.

Definición 2. Para cualquier par de grafones y , defina su distancia de corte como ${\displaystyle U}$ ${\displaystyle W}$

$${\displaystyle \delta _{\square }(U,W)=\inf _{\varphi }\lVert U-W^{\varphi }\rVert _{\square }}$$donde es la composición de con el mapa , y el ínfimo se toma sobre todas las biyecciones que preservan la medida desde el intervalo unitario hasta sí mismo. ^[8] ${\displaystyle W^{\varphi }(x,y)=W(\varphi (x),\varphi (y))}$ ${\displaystyle W}$ ${\displaystyle \varphi }$

La distancia de corte entre dos gráficos se define como la distancia de corte entre sus grafones asociados.

Decimos ahora que una secuencia de grafos es convergente bajo la distancia de corte si es una secuencia de Cauchy bajo la distancia de corte . Aunque no es una consecuencia directa de la definición, si dicha secuencia de grafos es de Cauchy, entonces siempre converge a algún grafon . ${\displaystyle (G_{n})}$ ${\displaystyle \delta _{\square }}$ ${\displaystyle W}$

Equivalencia de convergencia

Resulta que, para cualquier secuencia de grafos , la convergencia a la izquierda es equivalente a la convergencia bajo la distancia de corte y, además, el grafón límite es el mismo. También podemos considerar la convergencia de los grafones mismos utilizando las mismas definiciones, y la misma equivalencia es verdadera. De hecho, ambas nociones de convergencia están relacionadas más fuertemente a través de lo que se denominan lemas de conteo . ^[6] ${\displaystyle (G_{n})}$ ${\displaystyle W}$

Lema de conteo. Para cualquier par de grafones y , tenemos ${\displaystyle U}$ ${\displaystyle W}$

$${\displaystyle |t(F,U)-t(F,W)|\leq e(F)\delta _{\square }(U,W)}$$para todos los gráficos . ${\displaystyle F}$

El nombre "lema de conteo" proviene de los límites que este lema da a las densidades de homomorfismo , que son análogas a los conteos de subgrafos de grafos. Este lema es una generalización del lema de conteo de grafos que aparece en el campo de las particiones de regularidad , y muestra inmediatamente que la convergencia bajo la distancia de corte implica convergencia a la izquierda. ${\displaystyle t(F,W)}$

Lema de conteo inverso. Para cada número real , existe un número real y un entero positivo tales que para cualquier par de grafones y con ${\displaystyle \varepsilon >0}$ ${\displaystyle \eta >0}$ ${\displaystyle k}$ ${\displaystyle U}$ ${\displaystyle W}$

$${\displaystyle |t(F,U)-t(F,W)|\leq \eta }$$Para todos los gráficos que satisfacen , debemos tener . ${\displaystyle F}$ ${\displaystyle v(F)\leq k}$ ${\displaystyle \delta _{\square }(U,W)<\varepsilon }$

Este lema muestra que la convergencia a la izquierda implica convergencia bajo la distancia de corte.

El espacio de los grafones

Podemos convertir la distancia de corte en una métrica tomando el conjunto de todos los grafones e identificando dos grafones siempre que . El espacio de grafones resultante se denota y junto con forma un espacio métrico . ${\displaystyle U\sim W}$ ${\displaystyle \delta _{\square }(U,W)=0}$ ${\displaystyle {\widetilde {\mathcal {W}}}_{0}}$ ${\displaystyle \delta _{\square }}$

Este espacio resulta ser compacto . Además, contiene el conjunto de todos los grafos finitos, representados por sus grafones asociados, como un subconjunto denso . Estas observaciones muestran que el espacio de grafones es una completitud del espacio de grafos con respecto a la distancia de corte. Una consecuencia inmediata de esto es la siguiente.

Corolario 1. Para cada número real , existe un entero tal que para cada grafo , existe un grafo con como máximo vértices tal que . ${\displaystyle \varepsilon >0}$ ${\displaystyle N}$ ${\displaystyle W}$ ${\displaystyle G}$ ${\displaystyle N}$ ${\displaystyle \delta _{\square }(W,W_{G})<\varepsilon }$

Para ver por qué, sea el conjunto de grafos. Considere para cada grafo la bola abierta que contiene todos los grafones tales que . El conjunto de bolas abiertas para todos los grafos cubre , por lo que la compacidad implica que hay una subcobertura finita para algún subconjunto finito . Ahora podemos tomar como el mayor número de vértices entre los grafos en . ${\displaystyle {\mathcal {G}}}$ ${\displaystyle G\in {\mathcal {G}}}$ ${\displaystyle B_{\square }(G,\varepsilon )}$ ${\displaystyle W}$ ${\displaystyle \delta _{\square }(W,W_{G})<\varepsilon }$ ${\displaystyle {\widetilde {\mathcal {W}}}_{0}}$ ${\displaystyle \{B_{\square }(G,\varepsilon )\mid G\in {\mathcal {G}}_{0}\}}$ ${\displaystyle {\mathcal {G}}_{0}\subset {\mathcal {G}}}$ ${\displaystyle N}$ ${\displaystyle {\mathcal {G}}_{0}}$

Aplicaciones

Lema de regularidad

La compacidad del espacio de grafones puede considerarse como una formulación analítica del lema de regularidad de Szemerédi ; de hecho, un resultado más fuerte que el lema original. ^[9] El lema de regularidad de Szemeredi se puede traducir al lenguaje de los grafones de la siguiente manera. Defina una función escalonada como un grafo que es constante por partes, es decir, para alguna partición de , es constante en para todo . La afirmación de que un grafo tiene una partición de regularidad es equivalente a decir que su grafono asociado está cerca de una función escalonada. ${\displaystyle ({\widetilde {\mathcal {W}}}_{0},\delta _{\square })}$ ${\displaystyle W}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle [0,1]}$ ${\displaystyle W}$ ${\displaystyle S\times T}$ ${\displaystyle S,T\in {\mathcal {P}}}$ ${\displaystyle G}$ ${\displaystyle W_{G}}$

La prueba de compacidad requiere únicamente el lema de regularidad débil :

Lema de regularidad débil para grafones. Para cada grafón y , existe una función escalonada con, como máximo, pasos tales que . ${\displaystyle W}$ ${\displaystyle \varepsilon >0}$ ${\displaystyle W'}$ ${\displaystyle \lceil 4^{1/\varepsilon ^{2}}\rceil }$ ${\displaystyle \lVert W-W'\rVert _{\square }\leq \varepsilon }$

pero puede usarse para demostrar resultados de regularidad más fuertes, como el lema de regularidad fuerte :

Lema de regularidad fuerte para grafones. Para cada secuencia de números reales positivos, existe un entero positivo tal que para cada grafón , existe un grafón y una función escalonada con pasos tales que y ${\displaystyle \mathbf {\varepsilon } =(\varepsilon _{0},\varepsilon _{1},\dots )}$ ${\displaystyle S}$ ${\displaystyle W}$ ${\displaystyle W'}$ ${\displaystyle U}$ ${\displaystyle k<S}$ ${\displaystyle \lVert W-W'\rVert _{1}\leq \varepsilon _{0}}$ ${\displaystyle \lVert W'-U\rVert _{\square }\leq \varepsilon _{k}.}$

La prueba del lema de regularidad fuerte es similar en concepto al Corolario 1 anterior. Resulta que cada grafono puede aproximarse con una función escalonada en la norma , mostrando que el conjunto de bolas cubre . Estos conjuntos no son abiertos en la métrica, pero pueden ampliarse ligeramente para que sean abiertos. Ahora, podemos tomar una subcubierta finita y podemos demostrar que se cumple la condición deseada. ${\displaystyle W}$ ${\displaystyle U}$ ${\displaystyle L_{1}}$ ${\displaystyle B_{1}(U,\varepsilon _{0})}$ ${\displaystyle {\widetilde {\mathcal {W}}}_{0}}$ ${\displaystyle \delta _{\square }}$

La conjetura de Sidorenko

La naturaleza analítica de los grafones permite una mayor flexibilidad para atacar desigualdades relacionadas con homomorfismos.

Por ejemplo, la conjetura de Sidorenko es un importante problema abierto en la teoría de grafos extremales , que afirma que para cualquier grafo sobre vértices con grado medio (para algún ) y grafo bipartito sobre vértices y aristas, el número de homomorfismos de a es al menos . ^[10] Dado que esta cantidad es el número esperado de subgrafos etiquetados de en un grafo aleatorio , la conjetura puede interpretarse como la afirmación de que para cualquier grafo bipartito , el grafo aleatorio logra (en expectativa) el número mínimo de copias de sobre todos los grafos con alguna densidad de aristas fija. ${\displaystyle G}$ ${\displaystyle n}$ ${\displaystyle pn}$ ${\displaystyle p\in [0,1]}$ ${\displaystyle H}$ ${\displaystyle v}$ ${\displaystyle e}$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle p^{e}n^{v}}$ ${\displaystyle H}$ ${\displaystyle G(n,p)}$ ${\displaystyle H}$ ${\displaystyle H}$

Muchos enfoques de la conjetura de Sidorenko formulan el problema como una desigualdad integral en grafones, lo que luego permite atacar el problema utilizando otros enfoques analíticos. ^[11]

Generalizaciones

Los grafones se asocian naturalmente con grafos simples densos. Existen extensiones de este modelo a grafos ponderados dirigidos densos, a menudo denominados grafones decorados. ^[12] También existen extensiones recientes al régimen de grafos dispersos, tanto desde la perspectiva de los modelos de grafos aleatorios ^[13] como de la teoría de límites de grafos. ^{[14] [15]}

Referencias

1. Orbanz, P.; Roy, DM (2015). "Modelos bayesianos de gráficos, matrices y otras estructuras aleatorias intercambiables". IEEE Transactions on Pattern Analysis and Machine Intelligence . 37 (2): 437–461. arXiv : 1312.7857 . doi :10.1109/tpami.2014.2334607. PMID  26353253. S2CID  566759.
2. Wolfe, Patrick J.; Olhede, Sofia C. (23 de septiembre de 2013). "Estimación de grafones no paramétricos". arXiv : 1309.5936 [math.ST].
3. Choi, David; Wolfe, Patrick J. (febrero de 2014). "Co-agrupación de datos de red intercambiables por separado". Anales de estadística . 42 (1): 29–63. arXiv : 1212.4093 . doi :10.1214/13-AOS1173. ISSN  0090-5364. S2CID  16291079.
4. Gao, Chao; Lu, Yu; Zhou, Harrison H. (diciembre de 2015). "Estimación de grafones con velocidad óptima". Anales de estadística . 43 (6): 2624–2652. arXiv : 1410.5837 . doi :10.1214/15-AOS1354. ISSN  0090-5364. S2CID  14267617.
5. Yuan, Zhang; Elizaveta, Levina; Ji, Zhu (2017). "Estimación de probabilidades de borde de red mediante suavizado de vecindad". Biometrika . 104 (4): 771–783. doi :10.1093/biomet/asx042. ISSN  0006-3444.
6. Lovász, L. Grandes redes y límites de grafos . American Mathematical Society.
7. Chung, Fan RK ; Graham, Ronald L. ; Wilson, RM (1989). "Gráficos cuasi-aleatorios". Combinatorica . 9 (4): 345–362. doi : 10.1007/BF02125347 .
8. Glasscock, D. (2015). "¿Qué es un grafón?". Avisos de la American Mathematical Society . 62 (1): 46–48. arXiv : 1611.00718 .
9. Lovász, László ; Szegedy, Balázs (2007). "El lema de Szemerédi para el analista". Análisis Geométrico y Funcional . 17 : 252–270. doi :10.1007/s00039-007-0599-6. S2CID  15201345.
10. Sidorenko, A. (1993). "Una desigualdad de correlación para grafos bipartitos". Graphs and Combinatorics . 9 (2–4): 201–204. doi :10.1007/BF02988307.
11. Hatami, H. (2010). "Normas de grafos y conjetura de Sidorenko". Revista israelí de matemáticas . 175 (1): 125–150. arXiv : 0806.0047 . doi :10.1007/s11856-010-0005-1.
12. Haupt, Andreas; Schultz, Thomas; Jatamí, Mahoma; Tran, Ngoc (17 de julio de 2020). "Clasificación de grandes redes: un límite cuantitativo a través de motivos y grafones (investigación)". En Açu, Bahar; Danialli, Donatella; Lewicka, Marta; Pati, Arati; RV, Saraswathy; Teboh-Ewungkem, Miranda (eds.). Avances en Ciencias Matemáticas . Serie Asociación de Mujeres en Matemáticas. vol. 21. Springer, Cham. págs. 107-126. arXiv : 1710.08878 . doi : 10.1007/978-3-030-42687-3_7 . ISBN 978-3-030-42687-3.
13. Veitch, V.; Roy, DM (2015). "La clase de gráficos aleatorios que surgen de medidas aleatorias intercambiables". arXiv : 1512.03099 [math.ST].
14. Borgs, C.; Chayes, JT; Cohn, H.; Zhao, Y. (2019). "Una teoría L ^p de convergencia de grafos dispersos I: límites, modelos de grafos aleatorios dispersos y distribuciones de ley de potencia". Transacciones de la American Mathematical Society . 372 (5): 3019–3062. arXiv : 1401.2906 . doi :10.1090/tran/7543. S2CID  50704206.
15. Borgs, C.; Chayes, JT; Cohn, H.; Zhao, Y. (2018). "Una teoría L ^p de convergencia de grafos dispersos II: convergencia LD, cocientes y convergencia derecha". Anales de probabilidad . 46 (2018): 337–396. arXiv : 1408.0744 . doi :10.1214/17-AOP1187. S2CID  51786393.