Algunos modelos de grafos aleatorios que me resultan curiosos

Question

G(n,p)

Estamos familiarizados con la noción estándar de grafos aleatorios en los que se fija el número n de vértices y se elige cada arista para que pertenezca al grafo con probabilidad 1/2 (o p) de forma independiente. Este modelo se denomina G(n,1/2) o más generalmente G(n,p).

Grafos aleatorios con comportamiento marginal prescrito

Ahora, supongamos que en lugar de prescribir la probabilidad para cada arista, prescribimos la probabilidad marginal para cada subgrafo inducido H en r vértices. (Por tanto, r debe ser un número entero pequeño, 3,4,5, etc.) Supongamos además que

a) la probabilidad $p_H$ no depende de la identidad de los r vértices,

y

b) Sólo depende del tipo de isomorfismo de $H$ .

Así, por ejemplo: para r=3 se puede pensar en el caso de que $p_H = 1/9$ si H es un triángulo o un grafo vacío y $p_H=7/54$ de lo contrario.

Una vez que estos $p_H$ se asignan se considera entre todas las distribuciones de probabilidad con este comportamiento marginal (si las hay) la de máxima entropía. (Pero esta elección es negociable ; si hay algo diferente que merezca la pena hacer también está bien).

Mis preguntas:

1) ¿Están estos modelos estudiados en la literatura?

2) ¿Cuándo se $p_H$ ¿Es factible?

3) Dada esa viabilidad $p_H$ digamos en grafos con 4 vértices, ¿existe un algoritmo rápido para muestrear a partir de la distribución de máxima entropía que permita experimentar con este modelo?

Fondo

Esta pregunta viene motivada por una reciente charla de Nati Linial en nuestro seminario de "nociones básicas" sobre teoría de grafos extremos. (Tal vez se trate de modelos bien estudiados que simplemente he olvidado, pero ahora no lo recuerdo).

Answer 1

La teoría Lovasz-Szegedy de la grafones es probable que sea relevante. Toda función simétrica medible $p: [0,1] \times [0,1] \to [0,1]$ (también conocido como grafón) determina un modelo de grafo aleatorio, en el que a cada vértice v se le asigna un color c(v) uniformemente al azar a partir del intervalo unitario [0,1], y entonces dos vértices cualesquiera v, w están conectados por una arista con una probabilidad independiente de p(c(v),c(w)). Estos son, en cierto sentido, los únicos modelos de grafos grandes en el sentido de que cualquier secuencia de grafos cada vez más grandes tiene una subsecuencia que converge a un grafón (en el sentido de que el $p_H$ estadísticas convergen).

Cada $p_H$ (en el límite asintótico $n \to \infty$ ) puede leerse en el grafón como una integral. Por ejemplo, la densidad de triángulos es $\int\int\int_{[0,1]^3} p(x,y) p(y,z) p(z,x)\ dx dy dz$ .

Si el $p_H$ se especifican para todos grafos finitos H, entonces esto determina p hasta cambio de variables (biyecciones preservadoras de medida sobre [0,1]) fuera de un conjunto de medida cero. Pero si sólo se especifica la $p_H$ para un número finito de H entonces hay múltiples opciones para p (y en algunos casos, ninguna opción en absoluto) y no es obvio para mí cómo encontrar una solución o incluso para determinar si cuando existe una solución. (Obsérvese que incluso para sólo dos opciones de H, siendo una de ellas una arista y la otra un grafo bipartito, la cuestión de determinar los posibles valores de $p_H$ es esencialmente la conjetura de Sidorenko, que aún no está totalmente resuelta). Pero quizá los métodos numéricos (recocido, descenso de gradiente, etc.) puedan encontrar soluciones algunas veces (aunque difícilmente serán "canónicas").

Answer 2

(No es una respuesta pero la pongo aquí porque estoy teniendo problemas para publicarla en los comentarios)

Hola Gil, pensando en la pregunta 3 me viene a la mente las medidas de Gibbs. No maximiza la entropía, pero es extrema en el sentido que describiré a continuación:

Sea $\Omega_n$ la colección de todos los subgrafos de $K_n$ y ser $E_n:\Omega\to\mathbb R$ una función que tiene los mismos valores cualquier par de subgrafos isomórficos. Por tanto, la medida de Gibbs determinada por $E_n$ es $$\mu_n(\{H\})=\frac{e^{-E_n(H)}}{Z_n}$$ , donde $Z_n=\sum_{H\in\Omega_n}e^{-E_n(H)}$ . Esta medida de probabilidad no tiene la propiedad de maximizar la entropía sino que resuelve el problema $$ \sup_{\mu\in \mathcal M} \left[ h(\mu)-\int_{\Omega_n} E_n d\mu\right]. $$ con la función $E_n$ escribiendo se podrían utilizar los algoritmos similares a los que tenemos para el modelo de Ising para muestrear los grafos aleatorios.

Answer 3

ERGM (el modelo de grafo aleatorio exponencial), bien estudiado en la literatura de sociología / análisis de redes sociales, hace algo así: fija un conjunto de vértices, asigna un peso a cada uno de un conjunto dado de características (que comúnmente incluyen pequeños subgrafos inducidos como sugieres) y establece la probabilidad de ver cualquier gráfico particular en el conjunto de vértices dado a ser exp(suma w_i)/Z donde Z es una constante normalizadora y los términos en la suma son los pesos de las características que están presentes en el gráfico.

Las características y sus pesos pueden depender de los vértices individuales, de modo que no todos los subgrafos inducidos de la misma clase de isomorfismo tienen el mismo efecto sobre la probabilidad, o pueden ser simétricos.

Por lo general, nada (ni siquiera Z) puede calcularse con exactitud, por lo que los científicos sociales recurren a los métodos de Monte Carlo con cadena de Markov para resolver problemas de inferencia estadística sobre estos modelos (por ejemplo, generar gráficos con las probabilidades correctas para un conjunto dado de ponderaciones, o inferir las ponderaciones a partir de un conjunto dado de datos). Más concretamente, se puede realizar un paseo aleatorio en el que en cada paso se utilice la regla de Metrópolis-Hastings para decidir si se añade o se elimina una arista elegida al azar; esto converge finalmente a la distribución correcta y a los sociólogos no parece preocuparles demasiado que no sepan realmente cuánto tarda en converger.