{"id":2098,"date":"2014-09-14T13:25:25","date_gmt":"2014-09-14T12:25:25","guid":{"rendered":"http:\/\/www.blopig.com\/blog\/?p=2098"},"modified":"2014-09-14T12:52:39","modified_gmt":"2014-09-14T11:52:39","slug":"the-origins-of-exponential-random-graph-models","status":"publish","type":"post","link":"https:\/\/www.blopig.com\/blog\/2014\/09\/the-origins-of-exponential-random-graph-models\/","title":{"rendered":"The origins of exponential random graph models"},"content":{"rendered":"

The article\u00a0An Exponential Family of Probability Distributions for Directed Graphs<\/em>, published by Holland and Leinhardt (1981), set the foundation for the now known exponential random graph models (ERGM) or p<\/em>* models, which model jointly the whole adjacency matrix (or graph) \"X\". In this article they proposed an exponential family of probability distributions to model \"P(X=x)\", where \"x\" is a possible realisation of the random matrix \"X\".<\/p>\n

The article is mainly focused on directed graphs (although the theory can be extended to undirected graphs). Two main effects<\/em> or patterns<\/em>\u00a0are considered in the article:\u00a0Reciprocity<\/strong><\/em>, which relates to appearance of symmetric interactions (\"X_{ij}=1) (see nodes 3-5 of the Figure below).<\/p>\n

\"Stochastic_block_model_directed\"<\/p>\n

and, the\u00a0Differential<\/em> attractiveness<\/em><\/strong> of each node in the graph, which relates to the amount of interactions each\u00a0node “receives” (in-degree) and the amount of interactions that each node “produces” (out-degree) (the Figure below illustrates the differential attractiveness of two groups of nodes).<\/p>\n

\"Stochastic_block_model_directed2\"<\/a>\u00a0The model of\u00a0Holland and Leinhardt (1981), called p<\/em>1 model, that considers jointly the reciprocity of the graph and the differential attractiveness of each node is:<\/p>\n

\"p_1(x)=P(X=x)<\/p>\n

where \"\rho,\theta,\alpha_i,\beta_j are parameters, and \"\alpha_*=\beta_*=0 (identifying constrains).\u00a0\u00a0\"\rho can be interpreted as the mean tendency of reciprocation<\/strong>,\u00a0\"\theta\" can be interpreted as the density<\/strong> (size) of the network,\u00a0\"\alpha_i can be interpreted as as the productivity<\/strong> (out-degree) of a node,\u00a0\"\beta_j can be interpreted as the attractiveness<\/strong> (in-degree) of a node.<\/p>\n

The values \"m, and \"x_{*j}\" are: the number of reciprocated edges in the observed graph, the number of edges, the out-degree of node i and the in-degree of node j; respectively.<\/p>\n

Taking \"D_{ij}=(X_{ij},X_{ji})\", the model assumes that all\u00a0\"D_{ij}\" with \"i<j are independent.<\/p>\n

\n

 <\/p>\n

To better understand the model, let’s review its derivation:<\/p>\n

Consider the pairs \"D_{ij}=(X_{i,j},X_{j,i}),\,i<j and describe the joint distribution of \"\{D_{ij}\}_{ij}\", assuming all \"D_{ij}\" are statistically\u00a0independent. This\u00a0can be done by parameterizing the probabilities<\/p>\n

\"P(D_{ij}=(1,1))=m_{ij}<\/p>\n

\"P(D_{ij}=(1,0))=a_{ij}<\/p>\n

\"P(D_{ij}=(0,0))=n_{ij}<\/p>\n

where \"m_{ij}+a_{ij}+a_{ji}+n_{ij}=1,\,.<\/p>\n

Hence leading<\/p>\n

\"P(X=x)=\prod_{i<j}<\/p>\n

where \"\rho_{ij}=log(m_{ij}n_{ij} for \"i<j\", and \"\theta_{ij}=log(a_{ij}\/n_{ij})\" for \"i\neq.<\/p>\n

It can be seen that the parameters \"\rho_{ij}\" and \"\theta_{ij}\" can be interpreted as the reciprocity and differential attractiveness, respectively. With a bit of algebra we get:<\/p>\n

\"exp(\rho_{ij})=[
\nand
\n\"exp(\theta_{ij})=P(X_{ij}=1|X_{ji}=0)\/P(X_{ij}=0|X_{ji}=0).<\/p>\n

Now, if we consider the following restrictions:<\/p>\n

\"\rho_{ij}=\rho,\,, and \"\theta_{ij}=\theta+\alpha_i where \"\alpha_*=\beta_*=0.<\/p>\n

With some algebra we get the proposed form of the model<\/p>\n

\"p_1(x)=P(X=x)<\/p>\n

 <\/p>\n

 <\/p>\n","protected":false},"excerpt":{"rendered":"

The article\u00a0An Exponential Family of Probability Distributions for Directed Graphs, published by Holland and Leinhardt (1981), set the foundation for the now known exponential random graph models (ERGM) or p* models, which model jointly the whole adjacency matrix (or graph) . In this article they proposed an exponential family of probability distributions to model , […]<\/p>\n","protected":false},"author":26,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"nf_dc_page":"","wikipediapreview_detectlinks":true,"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"ngg_post_thumbnail":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[10],"tags":[],"ppma_author":[514],"class_list":["post-2098","post","type-post","status-publish","format-standard","hentry","category-groupmeetings"],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"authors":[{"term_id":514,"user_id":26,"is_guest":0,"slug":"luis","display_name":"Luis Ospina Forero","avatar_url":"https:\/\/secure.gravatar.com\/avatar\/310cef32cd5dac5a383fe35d2e6fa0ed40cb03d0712d2b5a5ef81092db812b3e?s=96&d=mm&r=g","0":null,"1":"","2":"","3":"","4":"","5":"","6":"","7":"","8":""}],"_links":{"self":[{"href":"https:\/\/www.blopig.com\/blog\/wp-json\/wp\/v2\/posts\/2098","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.blopig.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.blopig.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.blopig.com\/blog\/wp-json\/wp\/v2\/users\/26"}],"replies":[{"embeddable":true,"href":"https:\/\/www.blopig.com\/blog\/wp-json\/wp\/v2\/comments?post=2098"}],"version-history":[{"count":32,"href":"https:\/\/www.blopig.com\/blog\/wp-json\/wp\/v2\/posts\/2098\/revisions"}],"predecessor-version":[{"id":2136,"href":"https:\/\/www.blopig.com\/blog\/wp-json\/wp\/v2\/posts\/2098\/revisions\/2136"}],"wp:attachment":[{"href":"https:\/\/www.blopig.com\/blog\/wp-json\/wp\/v2\/media?parent=2098"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.blopig.com\/blog\/wp-json\/wp\/v2\/categories?post=2098"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.blopig.com\/blog\/wp-json\/wp\/v2\/tags?post=2098"},{"taxonomy":"author","embeddable":true,"href":"https:\/\/www.blopig.com\/blog\/wp-json\/wp\/v2\/ppma_author?post=2098"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}