Modelos de grafos aleatorios de la familia exponencial

Los modelos de grafos aleatorios de la familia exponencial (ERGM) son un conjunto de modelos estadísticos utilizados para estudiar la estructura y los patrones dentro de las redes , como las de contextos sociales, organizacionales o científicos. ^{[ 1 ] [ 2 ] [ 3 ]} Analizan cómo se forman las conexiones ( aristas ) entre individuos o entidades ( nodos ) modelando la probabilidad de características de la red, como la agrupación o la centralidad , en diversos ejemplos que incluyen redes de conocimiento , ^{[ 4 ]} redes organizacionales, ^{[ 5 ]} redes de colegas, ^{[ 6 ]} redes de redes sociales , redes de colaboración científica, ^{[ 7 ]} y más. Como parte de la familia exponencial de distribuciones, los ERGM ayudan a los investigadores a comprender y predecir el comportamiento de la red en campos que van desde la sociología hasta la ciencia de datos .

Existen muchas métricas para describir las características estructurales de una red observada, como la densidad, la centralidad o la asortatividad . ^{[ 8 ] [ 9 ]} Sin embargo, estas métricas describen la red observada, que es solo una instancia de un gran número de posibles redes alternativas. ^{[ 10 ]} 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 debería considerar el conjunto de todas las posibles redes alternativas ponderadas según su similitud con una red observada. Sin embargo, debido a que los datos de 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 . ^{[ 11 ] [ 2 ]} Los modelos estadísticos alternativos deberían reflejar la incertidumbre asociada con una observación dada, permitir la inferencia sobre la frecuencia relativa de las subestructuras de red de interés teórico, desambiguar la influencia de procesos confusos , representar eficientemente estructuras complejas y vincular los procesos de nivel local con las propiedades de nivel global. ^{[ 12 ]} 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 gama de modelos que abarcan diversos tipos de datos, no solo redes. Un modelo ERGM pertenece a esta familia y describe redes.

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

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

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

dónde${\displaystyle \theta }$es un vector de parámetros del modelo asociados con${\displaystyle s(y)}$y${\displaystyle c(\theta )=\sum _{y'\in {\mathcal {Y}}}\exp(\theta ^{T}s(y'))}$es una constante de normalización.

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

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

Defina un vector bidimensional de estadísticas mediante${\displaystyle s(y)=[s_{1}(y),s_{2}(y)]^{T}}$, dónde${\ Displaystyle s_ {1} (y) = bordes (y)}$se define como el número de aristas en el grafo${\displaystyle y}$y${\displaystyle s_{2}(y)=triángulos(y)}$se define como el número de triángulos cerrados en${\displaystyle y}$. Finalmente, sea el vector de parámetros definido por${\displaystyle \theta =(\theta _{1},\theta _{2})^{T}=(-\ln 2,\ln 3)^{T}}$, de modo que la probabilidad de cada gráfico${\displaystyle y\in {\mathcal {Y}}}$En este ejemplo viene dado por:

${\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 el mismo número de aristas y el mismo número de triángulos, también tienen la misma probabilidad en este ejemplo de ERGM. Para un representante${\displaystyle y}$de cada clase de isomorfismo, primero calculamos el término${\displaystyle x(y)=\exp(-\ln 2\cdot edges(y)+\ln 3\cdot triangles(y))}$, que es proporcional a la probabilidad de${\displaystyle y}$(hasta la constante de normalización)${\displaystyle c(\theta )}$).

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

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

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

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

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

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

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

${\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${\displaystyle x(y)}$en los ocho gráficos diferentes${\displaystyle y\in {\mathcal {Y}}}$Esto produce:

${\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 gráfico${\displaystyle y\in {\mathcal {Y}}}$es dado por${\displaystyle P(Y=y|\theta )={\frac {x(y)}{c(\theta )}}}$Explícitamente, obtenemos que el grafo con cero aristas tiene probabilidad${\displaystyle {\frac {8}{29}}}$, cada grafo con exactamente una arista tiene probabilidad${\displaystyle {\frac {4}{29}}}$, cada grafo con exactamente dos aristas tiene probabilidad${\displaystyle {\frac {2}{29}}}$y el grafo con exactamente tres aristas tiene probabilidad${\displaystyle {\frac {3}{29}}}$en este ejemplo.

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

Observamos que el cálculo explícito de todas las probabilidades de los grafos solo es posible debido a la escasa cantidad de grafos diferentes en este ejemplo. Dado que el número de grafos diferentes aumenta exponencialmente con el número de variables de enlace —que a su vez aumenta cuadráticamente con el número de nodos—, el cálculo de la constante de normalización resulta, en general, computacionalmente intratable , incluso para un número moderado de nodos. Por esta razón, la posibilidad de adoptar ERGM para el análisis de grandes redes está atrayendo cada vez más atención ^{[ 14 ] [ 15 ].}

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

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

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

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

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

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

• Modelos de atributos de actores autologísticos

• Byshkin, M.; Stivala, A.; Mira, A.; Krause, R.; Robins, G.; Lomi, A. (2016). "MCMC de parámetros auxiliares para modelos de grafos aleatorios exponenciales". Journal of Statistical Physics . 165 : 740–754 . doi : 10.1007/s10955-016-1509-4 (inactivo el 3 de julio de 2025).{{cite journal}}: CS1 maint: DOI inactivo desde julio de 2025 ( enlace )
• Borisenko, A.; Byshkin, M.; Lomi, A. (2019). "Un algoritmo simple para inferencia Monte Carlo escalable". arXiv : 1901.00533 [ stat.CO ].
• 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 Debrecen . 6 ( 3– 4): 290– 297. doi : 10.5486/PMD.1959.6.3-4.12 .
• Fienberg, SE; Wasserman, S. (1981). "Discusión de una familia exponencial de distribuciones de probabilidad para grafos dirigidos por Holland y Leinhardt". Journal of the American Statistical Association . 76 (373): 54– 57. doi : 10.1080/01621459.1981.10477600 .
• Frank, O.; Strauss, D (1986). "Markov Graphs". Journal of the American Statistical Association . 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" . Journal of Statistical Software . 24 (1): 1– 11. doi : 10.18637/jss.v024.i01 . PMC 2447931. PMID 18618019 .  
• Harris, Jenine K (2014). Introducción al modelado exponencial de grafos aleatorios . ISBN 978-1-4522-2080-2OCLC 870698788​​ 
• Hunter, DR; Goodreau, SM; Handcock, MS (2008). "Bondad de ajuste de los modelos de redes sociales". Journal of the American Statistical Association . 103 (481): 248– 258. Bibcode : 2008JASA..103..248H . CiteSeerX 10.1.1.206.396 . doi : 10.1198/016214507000000446 . 
• Hunter, D. R; Handcock, MS (2006). "Inferencia en modelos de la familia exponencial curva para redes". Journal of Computational and Graphical Statistics . 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 familia exponencial para redes" . Journal of Statistical Software . 24 (3): 1– 29. doi : 10.18637/jss.v024.i03 . PMC 2743438. PMID 19756229 .  
• Jin, IH; Liang, F. (2012). "Ajuste de modelos de redes sociales mediante el algoritmo MCMC de aproximación estocástica con truncamiento variable". Journal of Computational and Graphical Statistics . 22 (4): 927– 952. doi : 10.1080/10618600.2012.680851 .
• Koskinen, JH; Robins, GL; Pattison, PE (2010). "Análisis de modelos de grafos aleatorios exponenciales (p-estrella) 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 grafos 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" . Journal of the American Statistical Association . 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" . Journal of the 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". The Annals of Statistics . 48 (1): 374– 396. arXiv : 1702.01812 . doi : 10.1214/19-AOS1810 .
• Snijders, TAB (2002). "Estimación de modelos de grafos aleatorios exponenciales mediante cadenas de Markov Monte Carlo" (PDF) . Journal of Social Structure . 3 .
• Snijders, TAB; Pattison, PE; Robins, GL; Handcock, MS (2006). "Nuevas especificaciones para modelos de grafos aleatorios exponenciales". Sociological Methodology . 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" . Journal of the American Statistical Association . 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 estimación de máxima pseudoverosimilitud y máxima verosimilitud de modelos de grafos aleatorios de la familia exponencial" . Redes Sociales . 31 (1): 52– 62. doi : 10.1016/j.socnet.2008.10.003 . PMC 3500576. PMID 23170041 .  
• Zappa, P.; Lomi, A. (2015). "El análisis de redes multinivel en organizaciones: modelos y pruebas empíricas". Organizational Research Methods . 18 (3): 542– 569. doi : 10.1177/1094428115579225 .