Modelos de gráficos aleatorios familiares exponenciales.

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]} 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.

Fondo

Existen muchas métricas para describir las características estructurales de una red observada, como la densidad, la centralidad o la surtatividad. ^{[7] [8]} Sin embargo, estas métricas describen la red observada, que es solo una instancia de una gran cantidad 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 función de 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] [10]} Los modelos estadísticos alternativos deben reflejar la incertidumbre asociada con una observación determinada, permitir inferencias sobre la frecuencia relativa de las subestructuras de red de interés teórico, eliminar la ambigüedad de la influencia de procesos de confusión, representar eficientemente estructuras complejas y vincular procesos a nivel local. a propiedades a nivel global. ^[11] La aleatorización con preservación de grados , por ejemplo, es una forma específica en la que una red observada podría considerarse en términos de múltiples redes alternativas.

Definición

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

Formalmente un grafo aleatorio consta de un conjunto de nodos y una colección de variables ligadas , indexadas por pares de nodos , donde si los nodos están conectados por una arista y en caso contrario. Un par de nodos se llama pareja y una pareja 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 gráfico 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 forma, 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 asociados y es una constante de normalización. ${\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 nodos. Sin embargo, el tamaño del conjunto de redes posibles para una red no dirigida (gráfico simple) de tamaño es . 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 . ^[12] ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle 2^{n(n-1)/2}}$

Ejemplo

Sea un conjunto de tres nodos y sea el conjunto de todos los gráficos no dirigidos y sin bucles en . Sin bucle implica que para todos es y no dirigido implica que para todos es , de modo que hay tres variables binarias vinculantes ( ) y gráficos diferentes 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 en el gráfico y se define como el número de triángulos cerrados en . Finalmente, definamos el vector de parámetros 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, hay solo cuatro clases de isomorfismo de gráficos : el gráfico con cero aristas, tres gráficos con exactamente una arista, tres gráficos con exactamente dos aristas y el gráfico con tres aristas. Dado que los gráficos isomórficos tienen el mismo número de aristas y el mismo número 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 de normalización ). ${\displaystyle y}$ ${\displaystyle x(y)=\exp(-\ln 2\cdot edges(y)+\ln 3\cdot triangles(y))}$ ${\displaystyle y}$ ${\displaystyle c(\theta )}$

Si es la gráfica con aristas cero , 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 una gráfica 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 una gráfica 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 la gráfica 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 produce: ${\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 gráfica viene dada por . Explícitamente, obtenemos que el gráfico con cero aristas tiene probabilidad , cada gráfico con exactamente una arista tiene probabilidad , cada gráfico con exactamente dos aristas tiene probabilidad y el gráfico 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 patrones típicos de redes sociales o de otro tipo . El parámetro negativo ( ) 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 a menudo se encuentra en las redes empíricas, es decir, que el número empírico de aristas generalmente 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 mayor probabilidad 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 suma de cada arista divide la probabilidad por dos. Sin embargo, al pasar de un gráfico con dos aristas a un 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 el número de gráficos diferentes aumenta exponencialmente en el número de variables vinculadas, que a su vez aumenta cuadráticamente en el número de nodos, calcular la constante de normalización es en general computacionalmente intratable , ya para un número moderado de nodos.

Muestreo de un ERGM

El muestreo exacto de un ERGM determinado es computacionalmente intratable en general, ya que calcular la constante de normalización requiere una suma total . Se puede realizar un muestreo aproximado eficiente de un ERGM mediante cadenas de Markov y se aplica en los métodos actuales para aproximar los valores esperados y estimar los parámetros del ERGM. ^[13] De manera informal, dado un ERGM en un conjunto de gráficos con función de masa de probabilidad , se selecciona un gráfico inicial (que podría ser elegido de manera arbitraria o aleatoria o podría representar una red observada) e implícitamente define las probabilidades de transición (o probabilidades de salto) , que son las probabilidades condicionales de que la cadena de Markov esté en el gráfico después del Paso , dado que está en el gráfico después del Paso . Las probabilidades de transición no dependen de las gráficas de los 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 modo 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 de la gráfica inicial . Si esto se logra, 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 un número finito 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 ERGM con cadenas de Markov ^[13] generalmente definen un paso de actualización en dos subpasos: primero, seleccionar aleatoriamente un candidato en una vecindad del gráfico actual y, segundo, aceptarlo con una probabilidad que depende de la probabilidad relación del gráfico actual y el candidato . (Si el candidato no es aceptado, la cadena de Markov permanece en el gráfico actual ). Si el conjunto de gráficos no tiene restricciones (es decir, contiene cualquier combinación de valores en las variables binarias de enlace), un método simple para la selección de candidatos es elegir uno vincular la variable uniformemente 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 del gráfico 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 )}$

Referencias

1. Lusher, decano; Koskinen, Johan; Robins, Garry (2012). Modelos de gráficos aleatorios exponenciales para redes sociales: teoría, métodos y aplicaciones (análisis estructural en las ciencias sociales) . doi :10.1017/CBO9780511894701. ISBN 9780521141383. OCLC  1120539699.
2. Harris, Jenine K (2014). Una introducción al modelado de gráficos aleatorios exponenciales . ISBN 9781452220802. OCLC  870698788.
3. Brennecke, Julia; Rango, Olaf (1 de mayo de 2017). "La red de conocimiento de la empresa y la transferencia de asesoramiento entre inventores corporativos: un estudio de red multinivel". Política de investigación . 46 (4): 768–783. doi :10.1016/j.respol.2017.02.002. ISSN  0048-7333.
4. Harris, Jenine K (2013). "Lazos de comunicación a través de la red nacional de departamentos de salud locales". AMEPRE Revista Americana de Medicina Preventiva . 44 (3): 247–253. doi :10.1016/j.amepre.2012.10.028. ISSN  0749-3797. OCLC  4937103196. PMID  23415121.
5. Brennecke, Julia (2019). "Lazos disonantes en redes intraorganizacionales: por qué las personas buscan ayuda de colegas difíciles para resolver problemas". Revista de la Academia de Gestión AMJ . ISSN  0001-4273. OCLC  8163488129.
6. Harris, Jenine K; Lucas, Douglas A; Shelton, Sarah C; Zuckerman, Rachael B (2009). "Cuarenta años de investigación sobre el humo de segunda mano. La brecha entre el descubrimiento y la entrega". Revista Estadounidense de Medicina Preventiva . 36 (6): 538–548. doi :10.1016/j.amepre.2009.01.039. ISSN  0749-3797. OCLC  6980180781. PMID  19372026.
7. Wasserman, Stanley ; Fausto, Katherine (1994). Análisis de redes sociales: métodos y aplicaciones . ISBN 978-0-521-38707-1.
8. Newman, MEJ (2003). "La estructura y función de redes complejas". Revisión SIAM . 45 (2): 167–256. arXiv : cond-mat/0303516 . Código Bib : 2003SIAMR..45..167N. doi :10.1137/S003614450342480.
9. Contratista, Noshir; Wasserman, Stanley; Fausto, Katherine (2006). "Prueba de hipótesis multiteóricas y multinivel sobre redes organizativas: un marco analítico y un ejemplo empírico" (PDF) . Revisión de la Academia de Gestión . 31 (3): 681–703. doi :10.5465/AMR.2006.21318925. S2CID  10837327. Archivado desde el original (PDF) el 25 de febrero de 2020.
10. Harris, Jenine K (2014). Una introducción al modelado de gráficos aleatorios exponenciales . ISBN 9781452220802. OCLC  870698788.
11. Petirrojos, G.; Pattison, P.; Kalish, Y.; Lusher, D. (2007). "Una introducción a los modelos de gráficos aleatorios exponenciales para redes sociales". Redes sociales . 29 (2): 173–191. doi :10.1016/j.socnet.2006.08.002. hdl : 1959.3/216571 .
12. Newman, MEJ (25 de marzo de 2010). "Otros modelos de red". Redes . págs. 565–585. ISBN 978-0-19-920665-0.
13. Hunter, DR; 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. 

Otras lecturas

• Byshkin, M.; Stivala, A.; Mira, A.; Robins, G.; Lomí, A. (2018). "Estimación rápida de máxima verosimilitud mediante expectativa de equilibrio para datos de redes grandes". Informes científicos . 8 (1): 11509. arXiv : 1802.10311 . Código Bib : 2018NatSR...811509B. doi :10.1038/s41598-018-29725-8. PMC  6068132 . PMID  30065311.
• Caimo, A.; Friel, N (2011). "Inferencia bayesiana para modelos de gráficos 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; Cazador, DR; Colillas, 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). Una introducción al modelado de gráficos aleatorios exponenciales. Sabio. ^[1]
• Cazador, 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, DR; 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.
• Cazador, DR; Handcock, MS; Colillas, CT; Goodreau, SM; Morris, M. (2008). "ergm: un paquete para ajustar, simular y diagnosticar modelos de familia exponencial para redes". Revista de software estadístico . 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; Petirrojos, GL; Pattison, PE (2010). "Análisis de modelos de gráficos aleatorios exponenciales (p-star) con datos faltantes mediante aumento de datos bayesianos". Metodología estadística . 7 (3): 366–384. doi :10.1016/j.stamet.2009.09.007.
• Morris, M.; Handcock, MS; Cazador, DR (2008). "Especificación de modelos de gráficos aleatorios de familia exponencial: términos y aspectos computacionales". Revista de software estadístico . 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 gráficos 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 gráficos 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 gráficos 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 de familia exponencial curva y canónica de gráficos aleatorios". Los anales de la estadística . 48 (1): 374–396. arXiv : 1702.01812 . doi :10.1214/19-AOS1810.
• Snijders, TAB (2002). "Estimación de Monte Carlo de la cadena de Markov de modelos de gráficos aleatorios exponenciales" (PDF) . Revista de Estructura Social . 3 .
• Snijders, TAB; Pattison, PE; Petirrojos, GL; Handcock, MS (2006). "Nuevas especificaciones para modelos de gráficos 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, MAYOR; 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 gráficos aleatorios familiares exponenciales". Redes sociales . 31 (1): 52–62. doi :10.1016/j.socnet.2008.10.003. PMC  3500576 . PMID  23170041.

1. Harris, Jenine K (2014). Una introducción al modelado de gráficos aleatorios exponenciales . ISBN 9781452220802. OCLC  870698788.