Graphon

Una realización de un gráfico aleatorio intercambiable definido por un grafón . El gráfico se muestra como un mapa de calor magenta (abajo a la derecha). Se genera un gráfico aleatorio de tamaño asignando independientemente 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,l)}$${\displaystyle f(U_{k},U_{l})}$${\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 simétrica medible , que es importante en el estudio de grafos densos . Los grafones surgen como una noción natural del límite de una secuencia de gráficos densos y como los objetos fundamentales que definen los modelos de gráficos aleatorios intercambiables . Los grafones están ligados a gráficos densos por el siguiente par de observaciones: los modelos de gráficos aleatorios definidos por grafones dan lugar a gráficos densos casi con seguridad y, por el lema de regularidad , los grafones capturan la estructura de gráficos densos grandes 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 grafón define un modelo de grafo 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. El borde 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 solo si se puede definir en términos de un gráfico (posiblemente aleatorio) de esta manera. El modelo basado en un grafo fijo a veces se denota , por analogía con el modelo de grafos aleatorios de Erdős-Rényi . Un gráfico generado a partir de un grafo de esta manera se denomina 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 grafos aleatorios intercambiables son casi con seguridad densos. ^[1]${\displaystyle W\neq 0}$

Ejemplos de

El ejemplo más simple de grafón es para alguna constante . En este caso el modelo gráfico azar intercambiable asociado es el Erdős-Rényi modelo que incluye cada borde independientemente 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 por:

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

el modelo gráfico azar intercambiable resultante es la comunidad modelo de bloques estocástico , 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 y se incluye de forma independiente con probabilidad . ${\displaystyle k}$${\displaystyle k}$${\displaystyle p_{ll}}$${\displaystyle (l,l)}$${\displaystyle (m,m)}$${\displaystyle p_{lm}}$

Muchos otros modelos de gráficos aleatorios populares pueden entenderse como modelos de gráficos aleatorios intercambiables definidos por algún gráfico; en Orbanz y Roy se incluye una encuesta detallada. ^[1]

Matrices de adyacencia intercambiables conjuntamente

Un gráfico de tamaño aleatorio se puede representar 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 las submatrices de la parte superior izquierda de algún arreglo infinito de variables aleatorias; esto nos permite generar agregando un nodo y muestreando los bordes para . Con 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 la configuración de gráfico aleatorio. 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 grafo aleatorio no cambia por 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 en conjunto y, en esta configuración, afirma que la matriz aleatoria se genera mediante:${\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 es un grafo (posiblemente aleatorio). Es decir, un modelo de gráfico aleatorio tiene una matriz de adyacencia intercambiable en conjunto si y solo si es un modelo de gráfico aleatorio intercambiable en conjunto definido en términos de algún grafo.${\displaystyle W:[0,1]^{2}\to [0,1]}$

Estimación Graphon

Debido a problemas de identificación, es imposible estimar la función grafónica o las posiciones latentes de los nodos y hay dos direcciones principales de estimación grafónica. 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 un stepfunction , definidos por partición en intervalos tales que tiene un 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)}$$

y para cada uno , ajuste igual a la entrada de . Esta función es el grafo asociado del gráfico .${\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áficos donde el número de vértices de va al infinito, podemos analizar el comportamiento limitante de la secuencia considerando el comportamiento limitante de las funciones . Si estos gráficos convergen (de acuerdo con alguna definición adecuada de convergencia ), entonces esperamos que el límite de estos gráficos 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 gráficos. Resulta que para secuencias de gráficos 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 de

Ejemplo 1: Tome una secuencia aleatoria de gráficos 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 los bordes de estos gráficos.${\displaystyle (G_{n})}$${\displaystyle G_{n}=G(n,p)}$${\displaystyle p}$${\displaystyle n}$

En el espacio de los grafones, resulta que tal secuencia converge casi con seguridad a la constante , que captura la intuición anterior.${\displaystyle W(x,y)\equiv p}$

Ejemplo 2: Tome la secuencia de medios gráficos , definida tomando como gráfico bipartito en los vértices y tal que sea ​​adyacente a cuándo exactamente . 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 viene 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". Coincidiendo con esta intuición, la secuencia converge al medio grafón definido por cuándo y de otro modo. ${\displaystyle n}$${\displaystyle (H_{n})}$${\displaystyle W}$${\displaystyle W(x,y)=1}$${\displaystyle |x-y|\geq 1/2}$${\displaystyle W(x,y)=0}$

Ejemplo 3: tome la secuencia de gráficos bipartitos completos con partes del mismo tamaño. Si ordenamos los vértices colocando todos los vértices en 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 viene 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}}.}$

Como se hace más grande, esta estructura de bloques de la matriz de adyacencia se mantiene constante, de modo que esta secuencia de gráficos converge a un GraphOn "completa bipartito" definido por cada vez y , y el establecimiento de otra manera. ${\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}$

Ejemplo 4: Considere la secuencia del ejemplo anterior nuevamente. 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 viene 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 crece, 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 resulte en 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 las reetiquetas de los vértices.${\displaystyle n}$${\displaystyle (K_{n,n})}$

Ejemplo 5: tome una secuencia aleatoria de gráficos aleatorios dibujando un gráfico fijo . Entonces, al igual que en el primer ejemplo de esta sección, resulta que converge casi con seguridad.${\displaystyle (G_{n})}$ W {\displaystyle W} ${\displaystyle G_{n}\sim \mathbb {G} (n,W)}$${\displaystyle W}$${\displaystyle (G_{n})}$${\displaystyle W}$

Ejemplo 6: Dado un gráfico con un grafo asociado , podemos recuperar las propiedades teóricas del grafo y los parámetros de integrando transformaciones de .${\displaystyle G}$${\displaystyle W=W_{G}}$${\displaystyle G}$${\displaystyle W}$

Por ejemplo, la densidad de borde (es decir, grado medio dividido por el número de vértices) de está dada por la integral Esto es porque se -valued, y cada borde en corresponde a una región de área donde iguales .${\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 el número 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

Hay muchas formas 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 deberíamos restringir nuestra atención a las métricas que identifican gráficos aleatorios como similares. Por ejemplo, si dibujamos al azar 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 alta probabilidad para grandes .${\displaystyle G(n,p)}$${\displaystyle p}$${\displaystyle n}$

Hay dos métricas naturales que se comportan bien en gráficos aleatorios densos, en este sentido. La primera es una 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 una métrica de discrepancia de bordes , que dice que dos gráficos están cerca cuando sus densidades de bordes están cerca en todos sus subconjuntos de vértices correspondientes.

Milagrosamente, una secuencia de gráficos converge con respecto a una distancia precisamente cuando converge con respecto a la otra. Además, los objetos límite a ambas distancias resultan en grafones. La equivalencia de estas dos nociones de convergencia refleja cómo varias nociones de gráficos cuasialeatorios son equivalentes. ^[7]

Recuentos de subgrafos

Una forma de medir la distancia entre dos gráficos y es comparar sus recuentos subgrafo relativos. Es decir, para cada gráfico podemos comparar el número de copias de in y in . Si estos números están cerca para cada gráfico , entonces intuitivamente y son gráficos de apariencia similar.${\displaystyle G}$${\displaystyle H}$${\displaystyle F}$${\displaystyle F}$${\displaystyle G}$${\displaystyle F}$${\displaystyle H}$${\displaystyle F}$${\displaystyle G}$${\displaystyle H}$

Densidades de homomorfismo

En lugar de tratar 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 subgráficos y el número de homomorfismos de gráfico de un gráfico fijo son asintóticamente iguales.

Dados dos gráficos y , la densidad de homomorfismo de in se define como el número de homomorfismos de gráfico de a . 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 las densidades de homomorfismo. De hecho, dado un gráfico con 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, asumida la unidad hipercubo . Esto se sigue de la definición de un grafó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}$

Límites en términos de densidad de homomorfismo

Dada esta configuración, decimos que una secuencia de gráficos converge si para cada gráfico fijo , la secuencia de densidades de homomorfismo converge. Aunque no es evidente a partir de la definición solo, 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)}$$

simultaneamente.

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 restringir a subconjuntos del conjunto de vértices, y para cada uno de esos pares, los subconjuntos comparan el número de aristas desde hacia adentro con el número de aristas entre y hacia adentro . Si estos números son similares para cada par de subconjuntos (en relación con el número total de vértices), eso sugiere y 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}$

Para formalizar esto, para cualquier función simétrica y mensurable , defina la norma de corte de ser 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|}$

tomado sobre todos los subconjuntos medibles del intervalo unitario. ^[6] Esta norma captura nuestra noción anterior de distancia, porque para dos gráficos y con el mismo conjunto de vértices de tamaño , la norma de corte con los grafones asociados${\displaystyle S,T}$${\displaystyle G}$${\displaystyle H}$${\displaystyle V}$${\displaystyle |V|=n}$

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

nos permite calcular la máxima discrepancia de las densidades de los bordes entre y . Tenga en cuenta que esta definición se puede seguir utilizando incluso cuando los gráficos que se comparan no comparten un conjunto de vértices.${\displaystyle G}$${\displaystyle 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 isomorfos tengan una distancia cero, debemos calcular la norma de corte mínimo sobre todas las posibles "reetiquetas" de los vértices. Esto motiva la definición de la distancia de corte entre dos grafones y ser${\displaystyle W}$${\displaystyle U}$

${\displaystyle \delta _{\square }(U,W)=\inf _{\varphi }\lVert U-W^{\varphi }\rVert _{\square }}$

donde es la composición de con el mapa , y el mínimo se toma sobre todas las biyecciones que preservan la medida desde el intervalo de la unidad a sí mismo. ^[8] La distancia de corte entre dos gráficos se define como la distancia de corte entre sus grafones asociados.${\displaystyle W^{\varphi }(x,y)=W(\varphi (x),\varphi (y))}$${\displaystyle W}$${\displaystyle \varphi }$

Como espacio métrico

Para convertir la distancia de corte en una métrica, tomamos el conjunto de todos los grafones e identificamos dos grafones cuando sea . 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 {\tilde {\mathcal {W}}}_{0}}$${\displaystyle \delta _{\square }}$

Este espacio resulta compacto . Además, contiene el conjunto de todos los gráficos finitos como un subconjunto denso . Aquí, los gráficos se identifican como funciones escalonadas valoradas en el cuadrado unitario. Estas observaciones muestran que el espacio de grafones es una terminación del espacio de gráficos con respecto a la distancia de corte.${\displaystyle \{0,1\}}$

Aplicaciones

Lema de regularidad

Usando la compacidad del espacio de grafones , se pueden probar versiones más fuertes del lema de regularidad de Szemerédi .${\displaystyle ({\tilde {\mathcal {W}}}_{0},\delta _{\square })}$

La conjetura de Sidorenko

Artículo principal: la conjetura de Sidorenko

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

Por ejemplo, la conjetura de Sidorenko es un gran problema abierto en la teoría de grafos extremos , que afirma que para cualquier grafo en vértices con grado promedio (para algunos ) y grafo bipartito en vértices y aristas, el número de homomorfismos de a es al menos . ^[9] Dado que esta cantidad es el número esperado de subgrafos etiquetados de en un gráfico aleatorio , la conjetura se puede interpretar 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 sobre todo gráficos con alguna densidad de borde 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. ^[10]

Generalizaciones

Los grafones se asocian naturalmente con gráficos densos y simples. Hay extensiones de este modelo a los gráficos densos dirigidos ponderados, a menudo denominados grafones decorados. ^[11] También hay extensiones recientes al régimen de gráficos dispersos, tanto desde la perspectiva de los modelos de gráficos aleatorios ^[12] como desde la teoría del límite de los gráficos. ^{[13] [14]}

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 de máquinas . 37 (2): 437–461. arXiv : 1312.7857 . doi : 10.1109 / tpami.2014.2334607 . PMID  26353253 .
2. Wolfe, Patrick J .; Olhede, Sofia C. (23 de septiembre de 2013). "Estimación de grafon no paramétrico". arXiv : 1309.5936 [ math.ST ].
3. Choi, David; Wolfe, Patrick J. (febrero de 2014). "Co-agrupamiento de datos de red intercambiables por separado". The Annals of Statistics . 42 (1): 29–63. arXiv : 1212.4093 . doi : 10.1214 / 13-AOS1173 . ISSN 0090-5364 . 
4. Gao, Chao; Lu, Yu; Zhou, Harrison H. (diciembre de 2015). "Estimación de Graphon de tasa óptima". The Annals of Statistics . 43 (6): 2624–2652. arXiv : 1410.5837 . doi : 10.1214 / 15-AOS1354 . ISSN 0090-5364 . 
5. Yuan, Zhang; Elizaveta, Levina; Ji, Zhu (2017). "Estimación de probabilidades de borde de red mediante suavizado de vecindario" . 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 cuasialeatorios" . Combinatorica . 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. Sidorenko, A. (1993). "Una desigualdad de correlación para gráficos bipartitos" . Gráficos y Combinatoria . 9 (2–4): 201–204. doi : 10.1007 / BF02988307 .
10. Hatami, H. (2010). "Normas gráficas y conjetura de Sidorenko" . Revista de Matemáticas de Israel . 175 (1): 125-150. arXiv : 0806.0047 . doi : 10.1007 / s11856-010-0005-1 .
11. Haupt, Andreas; Schultz, Thomas; Khatami, Mohammed; Tran, Ngoc (17 de julio de 2020). "Clasificación en grandes redes: un límite cuantitativo a través de motivos y grafones (investigación)". En Acu, Bahar; Danialli, Donatella; Lewicka, Marta; Pati, Arati; RV, Saraswathy; Teboh-Ewungkem, Miranda (eds.). Avances en Ciencias Matemáticas . Serie de la Asociación de Mujeres en Matemáticas. 21 . Springer, Cham. arXiv : 1710.08878 . doi : 10.1007 / 978-3-030-42687-3_7 . ISBN 978-3-030-42687-3.
12. Veitch, V .; Roy, DM (2015). "La clase de gráficos aleatorios que surgen de medidas aleatorias intercambiables". arXiv : 1512.03099 [ math.ST ].
13. Borgs, C .; Chayes, JT; Cohn, H .; Zhao, Y. (2019). "Una teoría de L ^p de convergencia de gráfico disperso I: límites, modelos de gráfico aleatorio disperso y distribuciones de ley de potencia". Transacciones de la American Mathematical Society . 372 (5): 3019–3062. arXiv : 1401.2906 . doi : 10.1090 / tran / 7543 .
14. Borgs, C .; Chayes, JT; Cohn, H .; Zhao, Y. (2018). "Una teoría de L ^p de convergencia de gráfico disperso II: convergencia LD, cocientes y convergencia derecha". Los anales de la probabilidad . 46 (2018): 337–396. arXiv : 1408.0744 . doi : 10.1214 / 17-AOP1187 .