Modelos de grafos aleatorios de familia exponencial

Los modelos de gráficos aleatorios exponenciales (ERGM) son una familia de modelos estadísticos para analizar datos de redes sociales y de otro tipo . ^{[1] [2]} Los ejemplos de redes examinadas utilizando ERGM incluyen redes de conocimiento, ^[3] redes organizacionales, ^[4] redes de colegas, ^[5] redes de medios sociales, redes de desarrollo científico, ^[6] y otras.

Existen muchas métricas para describir las características estructurales de una red observada, como la densidad, la centralidad o la asortatividad. ^{[7] [8]} Sin embargo, estas métricas describen la red observada, que es solo una instancia de un gran número de posibles redes alternativas. Este conjunto de redes alternativas puede tener características estructurales similares o diferentes. Para respaldar la inferencia estadística sobre los procesos que influyen en la formación de la estructura de la red, un modelo estadístico debe considerar el conjunto de todas las redes alternativas posibles ponderadas en su similitud con una red observada. Sin embargo, debido a que los datos de la red son inherentemente relacionales, violan los supuestos de independencia y distribución idéntica de los modelos estadísticos estándar como la regresión lineal . ^{[9] [2]} Los modelos estadísticos alternativos deben reflejar la incertidumbre asociada con una observación dada, permitir la inferencia sobre la frecuencia relativa de las subestructuras de la red de interés teórico, desambiguando la influencia de los procesos de confusión, representando eficientemente estructuras complejas y vinculando los procesos de nivel local con las propiedades de nivel global. ^[10] La aleatorización que preserva el grado , por ejemplo, es una forma específica en la que una red observada podría considerarse en términos de múltiples redes alternativas.

La familia exponencial es una amplia familia de modelos que abarcan muchos tipos de datos, no solo redes. Un ERGM es un modelo de esta familia que describe redes.

Formalmente, un grafo aleatorio consiste en un conjunto de nodos y una colección de variables de enlace , indexadas por pares de nodos , donde si los nodos están conectados por una arista y en caso contrario. Un par de nodos se denomina díada y una díada es una arista si . ${\displaystyle Y\in {\mathcal {Y}}}$${\displaystyle n}$${\displaystyle \{Y_{ij}:i=1,\dots ,n;j=1,\dots ,n\}}$${\displaystyle ij}$${\displaystyle Y_{ij}=1}$${\displaystyle (i,j)}$${\displaystyle Y_{ij}=0}$${\displaystyle ij}$${\displaystyle Y_{ij}=1}$

El supuesto básico de estos modelos es que la estructura de un grafo observado puede explicarse mediante un vector dado de estadísticas suficientes que son función de la red observada y, en algunos casos, de atributos nodales. De esta manera, es posible describir cualquier tipo de dependencia entre las variables no diádicas: ${\displaystyle y}$ ${\displaystyle s(y)}$

${\displaystyle P(Y=y|\theta )={\frac {\exp(\theta ^{T}s(y))}{c(\theta )}},\quad \forall y\in {\mathcal {Y}}}$

donde es un vector de parámetros del modelo asociado con y es una constante normalizadora. ${\displaystyle \theta }$${\displaystyle s(y)}$${\displaystyle c(\theta )=\sum _{y'\in {\mathcal {Y}}}\exp(\theta ^{T}s(y'))}$

Estos modelos representan una distribución de probabilidad en cada red posible en los nodos. Sin embargo, el tamaño del conjunto de redes posibles para una red no dirigida (grafo simple) de tamaño es . Debido a que la cantidad de redes posibles en el conjunto supera ampliamente la cantidad de parámetros que pueden restringir el modelo, la distribución de probabilidad ideal es la que maximiza la entropía de Gibbs . ^[11]${\displaystyle n}$${\displaystyle n}$${\displaystyle 2^{n(n-1)/2}}$

Sea un conjunto de tres nodos y sea el conjunto de todos los grafos no dirigidos y sin bucles en . Sin bucles implica que para todos es y no dirigido implica que para todos es , de modo que hay tres variables de empate binarias ( ) y diferentes grafos en este ejemplo. ${\displaystyle V=\{1,2,3\}}$${\displaystyle {\mathcal {Y}}}$${\displaystyle V}$${\displaystyle i=1,2,3}$${\displaystyle Y_{ii}=0}$${\displaystyle i,j=1,2,3}$${\displaystyle Y_{ij}=Y_{ji}}$${\displaystyle Y_{12},Y_{13},Y_{23}}$${\displaystyle 2^{3}=8}$

Defina un vector bidimensional de estadísticas por , donde se define como el número de aristas del gráfico y se define como el número de triángulos cerrados en . Por último, dejemos que el vector de parámetros se defina por , de modo que la probabilidad de cada gráfico en este ejemplo esté dada por: ${\displaystyle s(y)=[s_{1}(y),s_{2}(y)]^{T}}$${\displaystyle s_{1}(y)=edges(y)}$${\displaystyle y}$${\displaystyle s_{2}(y)=triangles(y)}$${\displaystyle y}$${\displaystyle \theta =(\theta _{1},\theta _{2})^{T}=(-\ln 2,\ln 3)^{T}}$${\displaystyle y\in {\mathcal {Y}}}$

${\displaystyle P(Y=y|\theta )={\frac {\exp(-\ln 2\cdot edges(y)+\ln 3\cdot triangles(y))}{c(\theta )}}}$

Observamos que en este ejemplo, solo hay cuatro clases de isomorfismo de grafos : el grafo con cero aristas, tres grafos con exactamente una arista, tres grafos con exactamente dos aristas y el grafo con tres aristas. Dado que los grafos isomorfos tienen la misma cantidad de aristas y la misma cantidad de triángulos, también tienen la misma probabilidad en este ejemplo ERGM. Para un representante de cada clase de isomorfismo, primero calculamos el término , que es proporcional a la probabilidad de (hasta la constante normalizadora ). ${\displaystyle y}$${\displaystyle x(y)=\exp(-\ln 2\cdot edges(y)+\ln 3\cdot triangles(y))}$${\displaystyle y}$${\displaystyle c(\theta )}$

Si es el gráfico con cero aristas , entonces es y , de modo que ${\displaystyle y}$${\displaystyle edges(y)=0}$${\displaystyle triangles(y)=0}$

${\displaystyle x(y)=\exp(-\ln 2\cdot 0+\ln 3\cdot 0)=\exp(0)=1.}$

Si es un gráfico con exactamente una arista , entonces es y , de modo que ${\displaystyle y}$${\displaystyle edges(y)=1}$${\displaystyle triangles(y)=0}$

${\displaystyle x(y)=\exp(-\ln 2\cdot 1+\ln 3\cdot 0)={\frac {\exp(0)}{\exp(\ln 2)}}={\frac {1}{2}}.}$

Si es un gráfico con exactamente dos aristas , entonces es y , de modo que ${\displaystyle y}$${\displaystyle edges(y)=2}$${\displaystyle triangles(y)=0}$

${\displaystyle x(y)=\exp(-\ln 2\cdot 2+\ln 3\cdot 0)={\frac {\exp(0)}{\exp(\ln 2)^{2}}}={\frac {1}{4}}.}$

Si es el gráfico con exactamente tres aristas , entonces es y , de modo que ${\displaystyle y}$${\displaystyle edges(y)=3}$${\displaystyle triangles(y)=1}$

${\displaystyle x(y)=\exp(-\ln 2\cdot 3+\ln 3\cdot 1)={\frac {\exp(\ln 3)}{\exp(\ln 2)^{3}}}={\frac {3}{8}}.}$

La constante de normalización se calcula sumando los ocho gráficos diferentes . Esto da como resultado: ${\displaystyle x(y)}$${\displaystyle y\in {\mathcal {Y}}}$

${\displaystyle c(\theta )=1+3\cdot {\frac {1}{2}}+3\cdot {\frac {1}{4}}+{\frac {3}{8}}={\frac {29}{8}}.}$

Finalmente, la probabilidad de cada grafo está dada por . Explícitamente, obtenemos que el grafo con cero aristas tiene probabilidad , cada grafo con exactamente una arista tiene probabilidad , cada grafo con exactamente dos aristas tiene probabilidad y el grafo con exactamente tres aristas tiene probabilidad en este ejemplo. ${\displaystyle y\in {\mathcal {Y}}}$${\displaystyle P(Y=y|\theta )={\frac {x(y)}{c(\theta )}}}$${\displaystyle {\frac {8}{29}}}$${\displaystyle {\frac {4}{29}}}$${\displaystyle {\frac {2}{29}}}$${\displaystyle {\frac {3}{29}}}$

Intuitivamente, la estructura de las probabilidades gráficas en este ejemplo de ERGM es consistente con los patrones típicos de las redes sociales u otras redes . El parámetro negativo ( ) asociado con el número de aristas implica que, en igualdad de condiciones, las redes con menos aristas tienen una probabilidad mayor que las redes con más aristas. Esto es consistente con la escasez que a menudo se encuentra en las redes empíricas, es decir, que el número empírico de aristas normalmente crece a un ritmo más lento que el número máximo posible de aristas. El parámetro positivo ( ) asociado con el número de triángulos cerrados implica que, en igualdad de condiciones, las redes con más triángulos tienen una probabilidad mayor que las redes con menos triángulos. Esto es consistente con una tendencia al cierre triádico que a menudo se encuentra en ciertos tipos de redes sociales. Compare estos patrones con las probabilidades gráficas calculadas anteriormente. La adición de cada arista divide la probabilidad por dos. Sin embargo, al pasar de un gráfico con dos aristas al gráfico con tres aristas, el número de triángulos aumenta en uno, lo que además multiplica la probabilidad por tres. ${\displaystyle \theta _{1}=-\ln 2}$${\displaystyle \theta _{2}=\ln 3}$

Observamos que el cálculo explícito de todas las probabilidades de los gráficos solo es posible porque hay muy pocos gráficos diferentes en este ejemplo. Dado que la cantidad de gráficos diferentes aumenta exponencialmente en la cantidad de variables de enlace (que a su vez aumenta cuadráticamente en la cantidad de nodos), calcular la constante de normalización es, en general, computacionalmente intratable , incluso para una cantidad moderada de nodos.

El muestreo exacto de un ERGM dado es computacionalmente intratable en general ya que calcular la constante de normalización requiere la suma de todos los . El muestreo aproximado eficiente de un ERGM se puede hacer a través de cadenas de Markov y se aplica en los métodos actuales para aproximar valores esperados y estimar parámetros de ERGM. ^[12] De manera informal, dado un ERGM en un conjunto de grafos con función de masa de probabilidad , se selecciona un grafo inicial (que puede ser elegido arbitrariamente o aleatoriamente o puede representar una red observada) y se definen implícitamente probabilidades de transición (o probabilidades de salto) , que son las probabilidades condicionales de que la cadena de Markov esté en el grafo después del Paso , dado que está en el grafo después del Paso . Las probabilidades de transición no dependen de los grafos en pasos anteriores ( ), que es una propiedad definitoria de las cadenas de Markov , y no dependen de , es decir, la cadena de Markov es homogénea en el tiempo. El objetivo es definir las probabilidades de transición de manera que para todos sea ${\displaystyle y\in {\mathcal {Y}}}$${\displaystyle {\mathcal {Y}}}$${\displaystyle P(Y=y|\theta )={\frac {\exp(\theta ^{T}s(y))}{c(\theta )}}}$${\displaystyle y^{(0)}\in {\mathcal {Y}}}$${\displaystyle \pi (y,y')=P(Y^{(t+1)}=y'|Y^{(t)}=y)}$${\displaystyle y'}$${\displaystyle t+1}$${\displaystyle y}$${\displaystyle t}$${\displaystyle y^{(0)},\dots ,y^{(t-1)}}$${\displaystyle t}$${\displaystyle y\in {\mathcal {Y}}}$

${\displaystyle \lim _{t\to \infty }P(Y^{(t)}=y)={\frac {\exp(\theta ^{T}s(y))}{c(\theta )}},}$

independiente del gráfico inicial . Si se logra esto, se puede ejecutar la cadena de Markov durante una gran cantidad de pasos y luego devolver el gráfico actual como una muestra aleatoria del ERGM dado. La probabilidad de devolver un gráfico después de una cantidad finita pero grande de pasos de actualización es aproximadamente la probabilidad definida por el ERGM. ${\displaystyle y^{(0)}}$${\displaystyle y\in {\mathcal {Y}}}$

Los métodos actuales para el muestreo de ERGMs con cadenas de Markov ^[12] generalmente definen un paso de actualización mediante dos subpasos: primero, seleccionar aleatoriamente un candidato en un vecindario del grafo actual y, segundo, aceptar con una probabilidad que depende de la razón de probabilidad del grafo actual y el candidato . (Si el candidato no es aceptado, la cadena de Markov permanece en el grafo actual ). Si el conjunto de grafos no tiene restricciones (es decir, contiene cualquier combinación de valores en las variables binarias de empate), un método simple para la selección de candidatos es elegir una variable de empate de manera uniforme al azar y definir el candidato invirtiendo esta única variable (es decir, establecer ; todas las demás variables toman el mismo valor que en ). Una forma común de definir la probabilidad de aceptación es aceptar con la probabilidad condicional ${\displaystyle y'}$${\displaystyle y}$${\displaystyle y'}$${\displaystyle y}$${\displaystyle y'}$${\displaystyle y}$${\displaystyle {\mathcal {Y}}}$${\displaystyle y_{ij}}$${\displaystyle y'_{ij}=1-y_{ij}}$${\displaystyle y}$${\displaystyle y'}$

${\displaystyle P(Y=y'|Y=y'\vee Y=y)={\frac {P(Y=y')}{P(Y=y')+P(Y=y)}},}$

donde las probabilidades gráficas están definidas por el ERGM. Fundamentalmente, la constante de normalización se cancela en esta fracción, de modo que las probabilidades de aceptación se pueden calcular de manera eficiente. ${\displaystyle c(\theta )}$

• Byshkin, M.; Stivala, A.; Mira, A.; Robins, G.; Lomi, A. (2018). "Estimación rápida de máxima verosimilitud mediante expectativa de equilibrio para datos de redes grandes". Scientific Reports . 8 (1): 11509. arXiv : 1802.10311 . Bibcode :2018NatSR...811509B. doi :10.1038/s41598-018-29725-8. PMC  6068132 . PMID  30065311.
• Caimo, A.; Friel, N (2011). "Inferencia bayesiana para modelos de grafos aleatorios exponenciales". Redes sociales . 33 : 41–55. arXiv : 1007.5192 . doi :10.1016/j.socnet.2010.09.004.
• Erdős, P.; Rényi, A (1959). "Sobre gráficos aleatorios". Publicaciones Mathematicae . 6 : 290–297.
• Fienberg, SE; Wasserman, S. (1981). "Discusión de una familia exponencial de distribuciones de probabilidad para gráficos dirigidos por Holland y Leinhardt". Revista de la Asociación Estadounidense de Estadística . 76 (373): 54–57. doi :10.1080/01621459.1981.10477600.
• Frank, O.; Strauss, D (1986). "Gráficos de Markov". Revista de la Asociación Estadounidense de Estadística . 81 (395): 832–842. doi :10.2307/2289017. JSTOR  2289017.
• Handcock, MS; Hunter, DR; Butts, CT; Goodreau, SM; Morris, M. (2008). "statnet: herramientas de software para la representación, visualización, análisis y simulación de datos de red". Revista de software estadístico . 24 (1): 1–11. doi : 10.18637/jss.v024.i01 . PMC  2447931 . PMID  18618019.
• Harris, Jenine K (2014). Introducción al modelado de gráficos aleatorios exponenciales. Sage. ^[1]
• Hunter, DR; Goodreau, SM; Handcock, MS (2008). "Bondad de ajuste de los modelos de redes sociales". Revista de la Asociación Estadounidense de Estadística . 103 (481): 248–258. CiteSeerX  10.1.1.206.396 . doi :10.1198/016214507000000446.
• Hunter, D. R; Handcock, MS (2006). "Inferencia en modelos de familias exponenciales curvas para redes". Revista de estadística computacional y gráfica . 15 (3): 565–583. CiteSeerX  10.1.1.205.9670 . doi :10.1198/106186006X133069.
• Hunter, DR; Handcock, MS; Butts, CT; Goodreau, SM; Morris, M. (2008). "ergm: un paquete para ajustar, simular y diagnosticar modelos de la familia exponencial para redes". Journal of Statistical Software . 24 (3): 1–29. doi : 10.18637/jss.v024.i03 . PMC  2743438 .
• Jin, IH; Liang, F. (2012). "Ajuste de modelos de redes sociales utilizando el algoritmo MCMC de aproximación estocástica de truncamiento variable". Revista de estadística computacional y gráfica . 22 (4): 927–952. doi :10.1080/10618600.2012.680851.
• Koskinen, JH; Robins, GL; Pattison, PE (2010). "Análisis de modelos de gráficos aleatorios exponenciales (p-star) con datos faltantes mediante aumento de datos bayesiano". Metodología estadística . 7 (3): 366–384. doi :10.1016/j.stamet.2009.09.007.
• Morris, M.; Handcock, MS; Hunter, DR (2008). "Especificación de modelos de gráficos aleatorios de la familia exponencial: términos y aspectos computacionales". Journal of Statistical Software . 24 (4): 1548–7660. doi : 10.18637/jss.v024.i04 . PMC  2481518 . PMID  18650964.
• Rinaldo, A.; Fienberg, SE; Zhou, Y. (2009). "Sobre la geometría de familias aleatorias exponenciales discretas con aplicación a modelos de grafos aleatorios exponenciales". Revista electrónica de estadística . 3 : 446–484. arXiv : 0901.0026 . doi :10.1214/08-EJS350.
• Robins, G.; Snijders, T.; Wang, P.; Handcock, M.; Pattison, P (2007). "Desarrollos recientes en modelos de grafos aleatorios exponenciales (p*) para redes sociales" (PDF) . Redes sociales . 29 (2): 192–215. doi :10.1016/j.socnet.2006.08.003. hdl : 11370/abee7276-394e-4051-a180-7b2ff57d42f5 .
• Schweinberger, Michael (2011). "Inestabilidad, sensibilidad y degeneración de familias exponenciales discretas". Revista de la Asociación Estadounidense de Estadística . 106 (496): 1361–1370. doi :10.1198/jasa.2011.tm10747. PMC  3405854 . PMID  22844170.
• Schweinberger, Michael; Handcock, Mark (2015). "Dependencia local en modelos de grafos aleatorios: caracterización, propiedades e inferencia estadística". Revista de la Royal Statistical Society, Serie B . 77 (3): 647–676. doi :10.1111/rssb.12081. PMC  4637985 . PMID  26560142.
• Schweinberger, Michael; Stewart, Jonathan (2020). "Resultados de concentración y consistencia para modelos canónicos y de familia exponencial curva de grafos aleatorios". Anales de Estadística . 48 (1): 374–396. arXiv : 1702.01812 . doi :10.1214/19-AOS1810.
• Snijders, TAB (2002). "Estimación de Monte Carlo con cadena de Markov de modelos de grafos aleatorios exponenciales" (PDF) . Journal of Social Structure . 3 .
• Snijders, TAB; Pattison, PE; Robins, GL; Handcock, MS (2006). "Nuevas especificaciones para modelos de grafos aleatorios exponenciales". Metodología sociológica . 36 : 99–153. CiteSeerX  10.1.1.62.7975 . doi :10.1111/j.1467-9531.2006.00176.x.
• Strauss, D; Ikeda, M (1990). "Estimación de pseudoverosimilitud para redes sociales". Revista de la Asociación Estadounidense de Estadística . 5 (409): 204–212. doi :10.2307/2289546. JSTOR  2289546.
• van Duijn, MA; Snijders, TAB; Zijlstra, BH (2004). "p2: un modelo de efectos aleatorios con covariables para gráficos dirigidos". Statistica Neerlandica . 58 (2): 234–254. doi :10.1046/j.0039-0402.2003.00258.x.
• van Duijn, MAJ; Gile, KJ ; Handcock, MS (2009). "Un marco para la comparación de la máxima pseudoverosimilitud y la estimación de máxima verosimilitud de modelos de grafos aleatorios de familias exponenciales". Redes sociales . 31 (1): 52–62. doi :10.1016/j.socnet.2008.10.003. PMC  3500576 . PMID  23170041.