Modelo de gráfico aleatorio de máxima entropía

Los modelos de gráficos aleatorios de máxima entropía son modelos de gráficos aleatorios utilizados para estudiar redes complejas sujetas al principio de máxima entropía bajo un conjunto de restricciones estructurales, ^[1] que pueden ser globales, distributivas o locales.

Cualquier modelo de gráfico aleatorio (en un conjunto fijo de valores de parámetros) da como resultado una distribución de probabilidad en los gráficos , y aquellos que son de máxima entropía dentro de la clase considerada de distribuciones tienen la propiedad especial de ser modelos nulos máximamente imparciales para la inferencia de redes ^[2] (por ejemplo, inferencia de redes biológicas ). Cada modelo define una familia de distribuciones de probabilidad en el conjunto de gráficos de tamaño (para cada uno para algún finito ), parametrizado por una colección de restricciones en observables definidos para cada gráfico (como grado promedio esperado fijo , distribución de grados de una forma particular o secuencia de grados específica ), impuesta en la distribución del gráfico junto con la maximización de la entropía por el método de multiplicadores de Lagrange . Nótese que en este contexto, "máxima entropía" no se refiere a la entropía de un solo gráfico , sino a la entropía de todo el conjunto probabilístico de gráficos aleatorios. ${\displaystyle n}$${\displaystyle n>n_{0}}$${\displaystyle n_{0}}$${\displaystyle J}$${\displaystyle \{Q_{j}(G)\}_{j=1}^{J}}$${\displaystyle G}$

Varios modelos de redes aleatorias comúnmente estudiados son de hecho de máxima entropía, por ejemplo, los gráficos ER y (cada uno de los cuales tiene una restricción global en el número de aristas), así como el modelo de configuración (CM). ^[3] y el modelo de configuración suave (SCM) (cada uno de los cuales tiene restricciones locales, una para cada valor de grado de nodo). En los dos pares de modelos mencionados anteriormente, una distinción importante ^{[4] [5]} es si la restricción es aguda (es decir, satisfecha por cada elemento del conjunto de gráficos de tamaño con probabilidad distinta de cero en el conjunto), o suave (es decir, satisfecha en promedio en todo el conjunto). El primer caso (agudo) corresponde a un conjunto microcanónico ^[6] , la condición de máxima entropía produce todos los gráficos que satisfacen como equiprobables; el último caso (suave) es canónico ^[7], produciendo un modelo de gráfico aleatorio exponencial (ERGM). ${\displaystyle G(n,m)}$${\displaystyle G(n,p)}$${\displaystyle n}$${\displaystyle n}$${\displaystyle G}$${\displaystyle Q_{j}(G)=q_{j}\forall j}$

Supongamos que estamos construyendo un modelo de grafo aleatorio que consiste en una distribución de probabilidad en el conjunto de grafos simples con vértices. La entropía de Gibbs de este conjunto estará dada por ${\displaystyle \mathbb {P} (G)}$${\displaystyle {\mathcal {G}}_{n}}$${\displaystyle n}$ ${\displaystyle S[G]}$

${\displaystyle S[G]=-\sum _{G\in {\mathcal {G}}_{n}}\mathbb {P} (G)\log \mathbb {P} (G).}$

Nos gustaría que los valores promedio del conjunto de observables (como el grado promedio , la agrupación promedio o la longitud promedio de la ruta más corta ) fueran ajustables, por lo que imponemos restricciones "suaves" en la distribución del gráfico: ${\displaystyle \{\langle Q_{j}\rangle \}_{j=1}^{J}}$${\displaystyle \{Q_{j}(G)\}_{j=1}^{J}}$${\displaystyle J}$

${\displaystyle \langle Q_{j}\rangle =\sum _{G\in {\mathcal {G}}_{n}}\mathbb {P} (G)Q_{j}(G)=q_{j},}$

donde se etiquetan las restricciones. La aplicación del método de multiplicadores de Lagrange para determinar la distribución que maximiza mientras se satisface , y la condición de normalización da como resultado lo siguiente: ^[1]${\displaystyle j=1,...,J}$${\displaystyle \mathbb {P} (G)}$${\displaystyle S[G]}$${\displaystyle \langle Q_{j}\rangle =q_{j}}$${\displaystyle \sum _{G\in {\mathcal {G}}_{n}}\mathbb {P} (G)=1}$

${\displaystyle \mathbb {P} (G)={\frac {1}{Z}}\exp \left[-\sum _{j=1}^{J}\psi _{j}Q_{j}(G)\right],}$

donde es una constante normalizadora (la función de partición ) y son parámetros (multiplicadores de Lagrange) acoplados a los observables gráficos indexados correspondientemente, que pueden ajustarse para producir muestras gráficas con valores deseados de esas propiedades, en promedio; el resultado es una familia exponencial y un conjunto canónico ; produciendo específicamente un ERGM . ${\displaystyle Z}$${\displaystyle \{\psi _{j}\}_{j=1}^{J}}$

En el marco canónico anterior, se impusieron restricciones a las cantidades promediadas por conjunto . Aunque estas propiedades tomarán en promedio valores especificables mediante la configuración apropiada de , cada instancia específica puede tener , lo que puede ser indeseable. En cambio, podemos imponer una condición mucho más estricta: cada gráfico con probabilidad distinta de cero debe satisfacer exactamente . Bajo estas restricciones "afiladas", se determina la distribución de máxima entropía. Ejemplificamos esto con el modelo de Erdős–Rényi . ${\displaystyle \langle Q_{j}\rangle }$${\displaystyle \{\psi _{j}\}_{j=1}^{J}}$${\displaystyle G}$${\displaystyle Q_{j}(G)\neq q_{j}}$${\displaystyle Q_{j}(G)=q_{j}}$${\displaystyle G(n,m)}$

La restricción estricta en es la de un número fijo de aristas , ^[8] es decir , para todos los grafos extraídos del conjunto (instanciados con una probabilidad denotada ). Esto restringe el espacio muestral de (todos los grafos en vértices) al subconjunto . Esto está en analogía directa con el conjunto microcanónico en la mecánica estadística clásica , donde el sistema está restringido a una variedad delgada en el espacio de fase de todos los estados de un valor de energía particular . ${\displaystyle G(n,m)}$ ${\displaystyle m}$${\displaystyle |\operatorname {E} (G)|=m}$${\displaystyle G}$${\displaystyle \mathbb {P} _{n,m}(G)}$${\displaystyle {\mathcal {G}}_{n}}$${\displaystyle n}$${\displaystyle {\mathcal {G}}_{n,m}=\{g\in {\mathcal {G}}_{n};|\operatorname {E} (g)|=m\}\subset {\mathcal {G}}_{n}}$

Al restringir nuestro espacio muestral a , no tenemos restricciones externas (además de la normalización) que satisfacer, y por lo tanto seleccionaremos maximizar sin hacer uso de multiplicadores de Lagrange. Es bien sabido que la distribución que maximiza la entropía en ausencia de restricciones externas es la distribución uniforme en el espacio muestral (ver distribución de probabilidad de máxima entropía ), de la cual obtenemos: ${\displaystyle {\mathcal {G}}_{n,m}}$${\displaystyle \mathbb {P} _{n,m}(G)}$${\displaystyle S[G]}$

${\displaystyle \mathbb {P} _{n,m}(G)={\frac {1}{|{\mathcal {G}}_{n,m}|}}={\binom {\binom {n}{2}}{m}}^{-1},}$

donde la última expresión en términos de coeficientes binomiales es el número de formas de colocar aristas entre aristas posibles , y por lo tanto es la cardinalidad de . ${\displaystyle m}$${\displaystyle {\binom {n}{2}}}$${\displaystyle {\mathcal {G}}_{n,m}}$

Se han estudiado diversos conjuntos de máxima entropía a partir de generalizaciones de grafos simples. Entre ellos se incluyen, por ejemplo, conjuntos de complejos simpliciales ^[9] y grafos aleatorios ponderados con una secuencia de grados esperada dada ^[10].

• Principio de máxima entropía
• Distribución de probabilidad de máxima entropía
• Método de multiplicadores de Lagrange
• Modelo nulo
• Gráfico aleatorio
• Modelo de gráfico aleatorio exponencial
• Conjunto canónico
• Conjunto microcanónico