Grafón

Una realización de un gráfico aleatorio intercambiable definido por un grabón . El gráfico se muestra como un mapa de calor magenta (abajo a la derecha). Un gráfico aleatorio de tamaño se genera asignando de forma independiente a cada vértice una variable aleatoria latente (valores a lo largo del eje vertical) e incluyendo cada borde de forma independiente con probabilidad . Por ejemplo, el borde (verde, punteado) 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 grafon (también conocido como límite de gráfico ) es una función simétrica medible , que es importante en el estudio de gráficos densos . Los grafones surgen como una noción natural del límite de una secuencia de gráficos densos y como los objetos definitorios fundamentales de los modelos de gráficos aleatorios intercambiables . Los grafones están vinculados a gráficos densos mediante el siguiente par de observaciones: los modelos de gráficos aleatorios definidos por grafones dan lugar a gráficos densos casi con seguridad y, según el lema de regularidad , los grafones capturan la estructura de gráficos densos grandes y arbitrarios. ${\displaystyle W:[0,1]^{2}\to [0,1]}$

Formulación estadística

Un grafón es una función simétrica medible . Por lo general, se entiende que un grabón define un modelo de gráfico aleatorio intercambiable de acuerdo con 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 de forma independiente en el gráfico con probabilidad . ${\displaystyle (i,j)}$ ${\displaystyle W(u_{i},u_{j})}$

Un modelo de gráfico aleatorio es un modelo de gráfico aleatorio intercambiable si y sólo si se puede definir en términos de un grabón (posiblemente aleatorio) de esta manera. El modelo basado en un grafo fijo a veces se denomina , por analogía con el modelo Erdős-Rényi de gráficos aleatorios. Un gráfico generado a partir de un grabón de esta manera se llama gráfico 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 deduce que, si , los modelos de gráficos aleatorios intercambiables son casi con seguridad densos. ^[1] ${\displaystyle W\neq 0}$

Ejemplos

El ejemplo más simple de grabón es para alguna constante . En este caso, el modelo de gráfico aleatorio intercambiable asociado es el modelo 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 grafon que es constante por partes por:

1. dividir el cuadrado unitario en bloques, y ${\displaystyle k\times k}$
2. estableciendo 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 bloques estocástico comunitario , una generalización del modelo Erdős-Rényi. Podemos interpretar esto como un modelo de gráfico aleatorio que consta de distintos gráficos Erdős-Rényi con parámetros respectivamente, con bigrafos entre ellos donde cada posible borde entre bloques 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 grabón; Orbanz y Roy incluyen una encuesta detallada. ^[1]

Matrices de adyacencia intercambiables conjuntamente

Un gráfico aleatorio de tamaño se puede representar como una matriz de adyacencia aleatoria . Para imponer coherencia (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 las submatrices superior izquierda de algún conjunto infinito de variables aleatorias; esto nos permite generar agregando un nodo y muestreando los bordes . Desde esta perspectiva, los gráficos aleatorios se definen como matrices simétricas infinitas aleatorias . ${\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 entorno de los gráficos aleatorios. Una de esas nociones viene dada por 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 significa igual en distribución . Intuitivamente, esta condición significa que la distribución del gráfico aleatorio no cambia al volver a etiquetar 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 conjuntamente, 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 conjuntamente y, en este contexto, afirma que la matriz aleatoria se genera por: ${\displaystyle (X_{ij})}$

1. Muestra 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 hay un grabón (posiblemente aleatorio). Es decir, un modelo de gráfico aleatorio tiene una matriz de adyacencia intercambiable conjuntamente si y sólo si es un modelo de gráfico aleatorio intercambiable conjuntamente definido en términos de algún grabón. ${\displaystyle W:[0,1]^{2}\to [0,1]}$

Estimación de grafones

Debido a problemas de identificabilidad, es imposible estimar la función del grafón o las posiciones latentes de los nodos y existen dos direcciones principales de estimación del grafón. 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 gráfico sobre vértices se puede identificar con su matriz de adyacencia . Esta matriz corresponde a una función escalonada , definida dividiendo en intervalos tales que tiene interior ${\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)}$$

grafon asociado ${\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 gráficas donde el número de vértices de llega al infinito, podemos analizar el comportamiento límite de la secuencia considerando el comportamiento límite de las funciones . Si estas gráficas convergen (de acuerdo con alguna definición adecuada de convergencia ), entonces esperamos que el límite de estas gráficas corresponda al límite de estas funciones asociadas. ${\displaystyle (G_{n})}$ ${\displaystyle G_{n}}$ ${\displaystyle (W_{G_{n}})}$

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

Ejemplos

Grafón constante

Tome una secuencia de gráficos aleatorios de Erdős-Rényi con algún parámetro fijo . Intuitivamente, como tiende al infinito, el límite de esta secuencia de gráficos está determinado únicamente por la densidad de bordes de estos gráficos. En el espacio de los grafones, resulta que tal 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 grafon

Tome la secuencia de semigráficos , definida al tomar como el gráfico bipartito en los vértices y tal que es adyacente precisamente a cuando . Si los vértices se enumeran en el orden presentado, entonces la matriz de adyacencia tiene dos esquinas de matrices de bloques "medio cuadrados" llenas de unos, y el resto de las entradas son 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 crece, estas esquinas se "suavizan". De acuerdo con esta intuición, la secuencia converge al semigrafón 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

Tome la secuencia de gráficas bipartitas completas con partes del mismo 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 crece, esta estructura de bloques de la matriz de adyacencia permanece constante, de modo que esta secuencia de gráficos converge en un grabón "bipartito completo" definido por cuando sea y y estableciendo lo 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 alternando entre partes, la matriz de adyacencia tiene una estructura de tablero de ajedrez de ceros y unos. Por ejemplo, bajo este orden, 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 crecen, 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 gráficos, 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} -gráficos aleatorios dibujando algún grabón fijo . Entonces, al igual que en el primer ejemplo de esta sección, resulta que converge casi con seguridad. ${\displaystyle (G_{n})}$ ${\displaystyle G_{n}\sim \mathbb {G} (n,W)}$ ${\displaystyle W}$ ${\displaystyle (G_{n})}$ ${\displaystyle W}$

Recuperar parámetros de gráficos de grafones

Dado un gráfico con un grafon asociado , podemos recuperar las propiedades y parámetros teóricos del gráfico integrando transformaciones de . Por ejemplo, la densidad de aristas (es decir, el grado promedio dividido por el número de vértices) de viene dada por la integral ${\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 del triángulo 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

Hay muchas formas diferentes de medir la distancia entre dos gráficas. Si estamos interesados ​​en métricas que "preservan" las propiedades extremas de los gráficos, entonces deberíamos restringir nuestra atención a las métricas que identifican gráficos aleatorios como similares. Por ejemplo, si dibujamos aleatoriamente dos gráficos independientemente de un modelo Erdős-Rényi para algunos fijos , la distancia entre estos dos gráficos bajo una métrica "razonable" debería ser cercana a cero con una alta probabilidad para grandes . ${\displaystyle G(n,p)}$ ${\displaystyle p}$ ${\displaystyle n}$

Ingenuamente, dados dos gráficos en el mismo conjunto de vértices, se podría definir su distancia como el número de aristas que se deben agregar o eliminar para pasar 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 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 son cercanos 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 de vértices correspondientes.

Milagrosamente, una secuencia de gráficos 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 gráficos cuasialeatorios . ^[7]

Densidades de homomorfismo

Una forma de medir la distancia entre dos gráficos es comparar sus recuentos relativos de subgrafos. Es decir, para cada gráfico podemos comparar el número de copias de in y in . Si estos números son cercanos para cada gráfico , entonces intuitivamente son gráficos de apariencia similar. Sin embargo, en lugar de trabajar directamente con subgrafos, resulta más fácil trabajar con homomorfismos de grafos. Esto está bien cuando se trata de gráficos grandes y densos, ya que en este escenario el número de subgrafos y el número de homomorfismos de gráficos de un gráfico 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 gráficos y , la densidad de homomorfismo de in se define como el número de homomorfismos de gráficos desde hasta . En otras palabras, ¿es la probabilidad de que un mapa elegido aleatoriamente desde los vértices de a los vértices de envíe vértices adyacentes 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 gráfico con grafon 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 grabón asociado, considerando cuándo el integrando anterior es igual a . Luego podemos extender la definición de densidad de homomorfismo a grafones arbitrarios , usando 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 gráficos es convergente a la izquierda si para cada gráfico 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 grafo tal que para cada grafo , tenemos ${\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

Tome dos gráficas y en el mismo conjunto de vértices. Debido a que estos gráficos comparten los mismos vértices, una forma de medir su distancia es restringirlos a subconjuntos del conjunto de vértices y, para cada uno de esos pares de subconjuntos, comparar el número de aristas desde hasta adentro con el número de aristas entre y en . Si estos números son similares para cada par de subconjuntos (en relación con el número total de vértices), entonces eso sugiere que son gráficos 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 gráficos y en el mismo conjunto de vértices de tamaño , defina la distancia de corte etiquetada entre y que será ${\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 los bordes entre y . Podemos generalizar este concepto a grafones expresando la densidad de aristas en términos del grabó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 están las uniones de intervalos correspondientes a los vértices en y . Tenga en cuenta que esta definición aún se puede utilizar 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|}$$

asumido todos los subconjuntos medibles 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 todavía tiene una limitación importante: puede asignar una distancia distinta de cero a dos gráficos isomórficos. Para asegurarnos de que los gráficos isomórficos tengan una distancia cero, debemos calcular la norma de corte mínima sobre todos los "reetiquetados" posibles 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 está la composición de con el mapa , y el mínimo se toma sobre todas las biyecciones que preservan la medida desde el intervalo unitario hacia 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.

Ahora decimos que una secuencia de gráficas 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 Cauchy, entonces siempre converge en algún grafo . ${\displaystyle (G_{n})}$ ${\displaystyle \delta _{\square }}$ ${\displaystyle W}$

Equivalencia de convergencia

Resulta que, para cualquier secuencia de gráficos , la convergencia por la izquierda es equivalente a la convergencia bajo la distancia de corte y, además, el grafo límite es el mismo. También podemos considerar la convergencia de los propios grafones usando las mismas definiciones, y la misma equivalencia es cierta. De hecho, ambas nociones de convergencia se relacionan más fuertemente a través de lo que se denomina lemas de conteo . ^[6] ${\displaystyle (G_{n})}$ ${\displaystyle W}$

Contando Lema. 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álogos a los recuentos de subgrafos de gráficos. Este lema es una generalización del lema de conteo de gráficos que aparece en el campo de las particiones de regularidad , e inmediatamente muestra 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 tal 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 que todos los gráficos satisfagan , debemos tener . ${\displaystyle F}$ ${\displaystyle v(F)\leq k}$ ${\displaystyle \delta _{\square }(U,W)<\varepsilon }$

Este lema muestra que la convergencia por 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 sea posible . El espacio resultante de grafones 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 compacto . Además, contiene el conjunto de todos los grafos finitos, representados por sus grafos asociados, como un subconjunto denso . Estas observaciones muestran que el espacio de grafones es una compleción 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 número entero tal que para cada grafón , existe un grafo con como máximo vértices tales 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 gráficas. Considere para cada gráfico la bola abierta que contiene todos los grafones tales que . El conjunto de bolas abiertas para todos los gráficos 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 gráficos 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 los grafones puede considerarse como una formulación analítica del lema de regularidad de Szemerédi ; de hecho, un resultado más sólido 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 grabón que es constante por partes, es decir, para alguna partición de , es constante para todos . La afirmación de que un grafo tiene una partición de regularidad equivale a decir que su grafo 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 sólo el lema de regularidad débil :

Lema de regularidad débil para grafones. Para cada grafon y , hay 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 se puede utilizar para demostrar resultados de regularidad más sólidos, 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 grabón se puede aproximar con una función escalonada en la norma , mostrando que el conjunto de bolas cubre . Estos conjuntos no están abiertos en el sistema métrico, pero se pueden ampliar ligeramente para que estén abiertos. Ahora, podemos tomar una subcobertura 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 problema abierto importante en la teoría de grafos extremos , que afirma que para cualquier gráfico en vértices con grado promedio (para algunos ) y gráfico bipartito en vértices y aristas, el número de homomorfismos desde a es al menos . ^[10] Dado que esta cantidad es el número esperado de subgrafos etiquetados en un gráfico aleatorio , la conjetura puede interpretarse como la afirmación de que para cualquier gráfico bipartito , el gráfico aleatorio alcanza (en expectativa) el número mínimo de copias de todo gráficos con cierta densidad de bordes fijos. ${\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 gráficos densos y simples. Hay extensiones de este modelo a gráficos densos ponderados dirigidos, a menudo denominados grafones decorados. ^[12] También hay extensiones recientes al régimen de gráficos dispersos, tanto desde la perspectiva de los modelos de gráficos aleatorios ^[13] como de la teoría del límite de gráficos. ^{[14] [15]}

Referencias

1. Orbanz, P.; Roy, DM (2015). "Modelos bayesianos de gráficos, 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. S2CID  566759.
2. Wolfe, Patrick J.; Olhede, Sofía C. (23 de septiembre de 2013). "Estimación de grafones no paramétricos". arXiv : 1309.5936 [matemáticas.ST].
3. Choi, David; Wolfe, Patrick J. (febrero de 2014). "Coagrupación de datos de red intercambiables por separado". Los anales de la 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 grafón de velocidad óptima". Los anales de la 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 las probabilidades de borde de la 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 gráficos . Sociedad Matemática Estadounidense.
7. Chung, Fan RK ; Graham, Ronald L .; Wilson, RM (1989). "Gráficos cuasi aleatorios". Combinatoria . 9 (4): 345–362. doi : 10.1007/BF02125347 .
8. Glasscock, D. (2015). "Qué es un grafón". Avisos de la Sociedad Matemática Estadounidense . 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 gráficos bipartitos". Gráficas y Combinatoria . 9 (2–4): 201–204. doi :10.1007/BF02988307.
11. Hatami, H. (2010). "Normas gráficas 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 [matemáticas.ST].
14. Borgs, C.; Chayés, JT; Cohn, H.; Zhao, Y. (2019). "Una teoría L ^p de convergencia de gráficos dispersos I: límites, modelos de gráficos aleatorios dispersos y distribuciones de leyes de potencia". Transacciones de la Sociedad Matemática Estadounidense . 372 (5): 3019–3062. arXiv : 1401.2906 . doi : 10.1090/tran/7543. S2CID  50704206.
15. Borgs, C.; Chayés, JT; Cohn, H.; Zhao, Y. (2018). "Una teoría L ^p de convergencia de gráficos dispersos II: convergencia LD, cocientes y convergencia derecha". Los anales de la probabilidad . 46 (2018): 337–396. arXiv : 1408.0744 . doi :10.1214/17-AOP1187. S2CID  51786393.