Grafos aleatórios exponenciais

Modelos de grafos aleatórios exponenciais (ERGMs) são uma família de modelos estatísticos para analisar dados de redes sociais e outros tipos de rede.

Contexto[editar | editar código-fonte]

Existem muitas métricas para descrever as características estruturais de uma rede observada como densidade, centralidade ou assortatividade.^[1]^[2] No entanto, essas métricas descrevem a rede observada, que é apenas uma instância de um grande número de redes alternativas possíveis. Esse conjunto de redes alternativas pode ter características estruturais similares ou não. Para creditar uma inferência estatística sobre os processos que influenciam a formação das estruturas de rede, um modelo estatístico deve considerar o conjunto de todas as possíveis redes alternativas ponderadas em sua similaridade com uma rede observada. No entanto, porque os dados de uma rede são inerentementes relacionais, eles violam os pressupostos de independência e distribuição idêntica de modelos estatísticos como a regressão linear.^[3] Modelos estatísticos alternativos devem refletir a incerteza associada a uma dada observação, permitir inferência sobre a frequência relativa sobre as subestrututras de rede de interesse teórico, eliminar ambiguidades na influência de processos de confundimento, representar eficientemente estruturas complexas e ligar processos de nível local com propriedades de nível global.^[4] Randomização com preservação de grau, por exemplo, é uma forma específica em que uma rede observada pode ser considerada em termos de múltiplas redes alternativas.

Definição[editar | editar código-fonte]

A família exponencial é uma família abrangente de modelos para cobrir muitos tipos de dados, não apenas de redes. Um ERGM é um modelo desta família que descreve redes.

Formalmente, um grafo aleatório $Y$ consiste de um conjunto de nós $n$ e díades (arestas) $m$ $\{Y_{ij}:i=1,\dots ,n;j=1,\dots ,n\}$ onde $Y_{ij}=1$ se os nós $(i,j)$ são conectados e $Y_{ij}=0$ de outro modo.

O pressuposto básico desses modelos é que a estrutura em um grafo observado $y$ pode ser explicado por qualquer estatística $s(y)$ dependendo da rede observada e seus atributos nodais. Desse modo, é possível descrever qualquer tipo de dependência entre as variáveis diádicas:

$P(Y=y|\theta )={\frac {\exp(\theta ^{T}s(y))}{c(\theta )}}$

onde $\theta$ é um vetor de parâmetros do modelo associados com $s(y)$ e $c(\theta )$ é uma constante de normalização.

Esses modelos representam uma distribuição de probabilidade em cada rede possível nos nós $n$ . No entanto, o tamanho do conjunto de redes possíveis para uma rede não direcionada (grafo simples) de tamanho $n$ é $2^{n(n-1)/2}$ . Porque o número de redes possíveis no conjunto supera vastamente o número de parâmetro que podem restringir o modelo, a distribuição de probabilidade ideal é a que maximiza a entropia de Gibbs.^[5]

Referências[editar | editar código-fonte]

↑ Wasserman, Stanley; Faust, Katherine (1994). Social Network Analysis: Methods and Applications. [S.l.: s.n.] ISBN 978-0-521-38707-1
↑ Newman, M.E.J. «The Structure and Function of Complex Networks». SIAM Review. 45 (2): 167–256. doi:10.1137/S003614450342480
↑ Contractor, Noshir; Wasserman, Stanley; Faust, Katherine. «Testing Multitheoretical, Multilevel Hypotheses About Organizational Networks: An Analytic Framework and Empirical Example». Academy of Management Review. 31 (3): 681–703. doi:10.5465/AMR.2006.21318925
↑ Robins, G.; Pattison, P.; Kalish, Y.; Lusher, D. (2007). «An introduction to exponential random graph models for social networks». Social Networks. 29: 173–191. doi:10.1016/j.socnet.2006.08.002
↑ Newman, M.E.J. «Other Network Models». Networks. [S.l.: s.n.] pp. 565–585. ISBN 978-0-19-920665-0

Leitura adicional[editar | editar código-fonte]

Caimo, A.; Friel, N (2011). «Bayesian inference for exponential random graph models». Social Networks. 33: 41–55. doi:10.1016/j.socnet.2010.09.004
Erdős, P.; Rényi, A (1959). «On random graphs». Publicationes Mathematicae. 6: 290–297
Fienberg, S. E.; Wasserman, S. (1981). «Discussion of An Exponential Family of Probability Distributions for Directed Graphs by Holland and Leinhardt». Journal of the American Statistical Association. 76: 54–57. doi:10.1080/01621459.1981.10477600
Frank, O.; Strauss, D (1986). «Markov Graphs». Journal of the American Statistical Association. 81: 832–842. doi:10.2307/2289017
Handcock, M. S.; Hunter, D. R.; Butts, C. T.; Goodreau, S. M.; Morris, M. (2008). «statnet: Software Tools for the Representation, Visualization, Analysis and Simulation of Network Data». Journal of Statistical Software. 24: 1–11
Hunter, D. R.; Goodreau, S. M.; Handcock, M. S. (2008). «Goodness of Fit of Social Network Models». Journal of the American Statistical Association. 103: 248–258. doi:10.1198/016214507000000446
Hunter, D. R; Handcock, M. S. (2006). «Inference in curved exponential family models for networks». Journal of Computational and Graphical Statistics. 15: 565–583. doi:10.1198/106186006X133069
Hunter, D. R.; Handcock, M. S.; Butts, C. T.; Goodreau, S. M.; Morris, M. (2008). «ergm: A Package to Fit, Simulate and Diagnose Exponential-Family Models for Networks». Journal of Statistical Software. 24: 1–29
Jin, I.H.; Liang, F. (2012). «Fitting social networks models using varying truncation stochastic approximation MCMC algorithm». Journal of Computational and Graphical Statistics. doi:10.1080/10618600.2012.680851
Koskinen, J. H.; Robins, G. L.; Pattison, P. E. (2010). «Analysing exponential random graph (p-star) models with missing data using Bayesian data augmentation». Statistical Methodology. 7: 366–384. doi:10.1016/j.stamet.2009.09.007
Morris, M.; Handcock, M. S.; Hunter, D. R. (2008). «Specification of Exponential-Family Random Graph Models: Terms and Computational Aspects». Journal of Statistical Software. 24
Rinaldo, A.; Fienberg, S. E.; Zhou, Y. (2009). «On the geometry of descrete exponential random families with application to exponential random graph models». Electronic Journal of Statistics. 3: 446–484. doi:10.1214/08-EJS350
Robins, G.; Snijders, T.; Wang, P.; Handcock, M.; Pattison, P (2007). «Recent developments in exponential random graph (p*) models for social networks». Social Networks. 29: 192–215. doi:10.1016/j.socnet.2006.08.003
Snijders, T. A. B. (2002). «Markov chain Monte Carlo estimation of exponential random graph models» (PDF). Journal of Social Structure. 3
Snijders, T. A. B.; Pattison, P. E.; Robins, G. L. (2006). «New specifications for exponential random graph models». Sociological Methodology. 36: 99–153. doi:10.1111/j.1467-9531.2006.00176.x
Strauss, D; Ikeda, M (1990). «Pseudolikelihood estimation for social networks». Journal of the American Statistical Association. 5: 204–212. doi:10.2307/2289546
van Duijn, M. A.; Snijders, T. A. B.; Zijlstra, B. H. (2004). «p2: a random effects model with covariates for directed graphs». Statistica Neerlandica. 58: 234–254. doi:10.1046/j.0039-0402.2003.00258.x
van Duijn, M. A. J.; Gile, K. J.; Handcock, M. S. (2009). «A framework for the comparison of maximum pseudo-likelihood and maximum likelihood estimation of exponential family random graph models». Social Networks. 31: 52–62. doi:10.1016/j.socnet.2008.10.003

[1] Wasserman, Stanley; Faust, Katherine (1994). Social Network Analysis: Methods and Applications. [S.l.: s.n.] ISBN 978-0-521-38707-1

[2] Newman, M.E.J. «The Structure and Function of Complex Networks». SIAM Review. 45 (2): 167–256. doi:10.1137/S003614450342480

[Contractor-3] Contractor, Noshir; Wasserman, Stanley; Faust, Katherine. «Testing Multitheoretical, Multilevel Hypotheses About Organizational Networks: An Analytic Framework and Empirical Example». Academy of Management Review. 31 (3): 681–703. doi:10.5465/AMR.2006.21318925

[Intro-4] Robins, G.; Pattison, P.; Kalish, Y.; Lusher, D. (2007). «An introduction to exponential random graph models for social networks». Social Networks. 29: 173–191. doi:10.1016/j.socnet.2006.08.002

[Newman-5] Newman, M.E.J. «Other Network Models». Networks. [S.l.: s.n.] pp. 565–585. ISBN 978-0-19-920665-0

[1]

[2]

[3]

[4]

[5]