Grafos aleatórios exponenciais

Ciência da Rede
Teoria
Grafo Rede complexa Contágio Redes de pequeno mundo Scale-free Estrutura comunitária Percolação Evolução Difusão de inovações (redes sociais) Controlabilidade Desenho grafo Capital social Análise de links Otimização Reciprocidade Transitividade Ligação preferencial Teoria do equilíbrio Efeito de rede Influência social
Tipos de Rede
Rede de computadores Telecomunicação Rede social Neural Artificial Interdependente Semântico Dependência Fluxo
Grafos
Caraterísticas Clique Componente Corte Ciclo Estrutura de dados Aresta Laço Vizinhança Caminho Vértice Lista de adjacência / matriz Incidência Lista / matrix Tipos Grafo bipartido Grafo completo Grafo orientado Hipergrafo Multigrafo Aleatórios Ponderado
Métricas & Algoritmos
Centralidade Grau Betweenness Proximidade PageRank Clustering Centralidades Baseadas na Dissimilaridades Distribuição de Graus Correlação de Graus Assortatividade Distância Modularidade
Modelos
Grafo Aleatório Erdös–Rényi Barabási–Albert Watts–Strogatz Exponencial Aleatório (ERGM) Epidemia Hierárquica
Categorias
Teoria dos grafos Teoria das redes complexas
v d e

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

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

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 ${\displaystyle Y}$ consiste de um conjunto de nós ${\displaystyle n}$ e díades (arestas) ${\displaystyle m}$ ${\displaystyle \{Y_{ij}:i=1,\dots ,n;j=1,\dots ,n\}}$ onde ${\displaystyle Y_{ij}=1}$ se os nós ${\displaystyle (i,j)}$ são conectados e ${\displaystyle Y_{ij}=0}$ de outro modo.

O pressuposto básico desses modelos é que a estrutura em um grafo observado ${\displaystyle y}$ pode ser explicado por qualquer estatística ${\displaystyle 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:

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

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

Esses modelos representam uma distribuição de probabilidade em cada rede possível nos nós ${\displaystyle n}$. No entanto, o tamanho do conjunto de redes possíveis para uma rede não direcionada (grafo simples) de tamanho ${\displaystyle n}$ é ${\displaystyle 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

Leitura adicional

• 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 

• Portal de probabilidade e estatística