A survey of statistical network models

Anna Goldenberg; Alice X Zheng; Stephen E Fienberg; Edoardo M Airoldi

Source-linked AI summary

A survey of statistical network models

Anna Goldenberg, Alice X Zheng, Stephen E Fienberg, Edoardo M Airoldi

arXiv:0912.5410v1Dec 29, 2009stat.MEcs.LGphysics.soc-phq-bio.MNstat.ML

TL;DR

Network research spans diverse fields, but statistical tools for estimating and assessing model fit remain limited, while common network summaries can mislead when data are biased or noisy. This survey charts the field’s historical development, formal models, interconnections, estimation, and open challenges.

Problem
Statistical tools for estimating and assessing the fit of many network models remain lacking, and common graphical summaries may inadequately describe real, biased, or noisy network data.
Method
The paper surveys seventy years of statistical network modeling, covering examples, prominent static and dynamic models, parameter interpretation, estimation, and interconnections across major approaches.
Results
The survey outlines major schools of thought, network-modeling approaches, their interconnections, and statistical gaps that motivate future research directions.
Takeaways & Limitations
The review provides an entry point to network-modeling literature and identifies open problems and challenges for machine learning and statistics.
Takeaways & Limitations
The survey is selective rather than comprehensive and excludes topics including agent-based modeling and efficient computation on networks.

Abstract

from arXiv · show

Networks are ubiquitous in science and have become a focal point for discussion in everyday life. Formal statistical models for the analysis of network data have emerged as a major topic of interest in diverse areas of study, and most of these involve a form of graphical representation. Probability models on graphs date back to 1959. Along with empirical studies in social psychology and sociology from the 1960s, these early works generated an active network community and a substantial literature in the 1970s. This effort moved into the statistical literature in the late 1970s and 1980s, and the past decade has seen a burgeoning network literature in statistical physics and computer science. The growth of the World Wide Web and the emergence of online networking communities such as Facebook, MySpace, and LinkedIn, and a host of more specialized professional network communities has intensified interest in the study of networks and network data. Our goal in this review is to provide the reader with an entry point to this burgeoning literature. We begin with an overview of the historical development of statistical network modeling and then we introduce a number of examples that have been studied in the network literature. Our subsequent discussion focuses on a number of prominent static and dynamic network models and their interconnections. We emphasize formal model descriptions, and pay special attention to the interpretation of parameters and their estimation. We end with a description of some open problems and challenges for machine learning and statistics.

Introduction

This survey selectively charts statistical network modeling across several disciplines, organizing prominent approaches and their historical development. It distinguishes static models of a single network snapshot from dynamic models concerned with changes over time.

The survey covers statistical network modeling in social sciences, computer science, physics, and biology.
Because the literature spans many books, papers, and proceedings, the authors provide a selective rather than comprehensive survey.
The review charts historical progress, outlines major modeling schools and their interconnections, and identifies statistical gaps.
Static models explain links in a single network snapshot, whereas dynamic models address mechanisms governing network changes over time.

1.1 Overview of Modeling Approaches

Statistical network modeling developed from foundational sociological, probabilistic, and mathematical work into models addressing network structure, dynamics, and large-scale applications. The literature includes random graphs, exponential random graph models, physics-inspired models, and machine-learning approaches.

Early network modeling combined sociological studies, mathematical graph structures, and probability models such as Erdős–Rényi random graphs.
At λ = pN = 1, the Erdős–Rényi–Gilbert model undergoes a phase change from many small tree components to a giant connected component.
The p1 model added popularity, expansiveness, and reciprocation effects, while retaining a log-linear form that facilitated maximum-likelihood estimation.
Early social-science network studies were usually small and static, with few datasets collected at multiple time points to study network evolution.
Late-1990s physics models modified random graphs to produce hubs, local clustering, and network growth or differential edge addition and deletion.
A major concern is that estimation and model-fit tools for statistical-physics and stochastic-process models are often lacking, while summary features can mislead.

1.2 What This Survey Does Not Cover

The survey focuses on statistical network models and applications, while deliberately excluding several adjacent literatures. These exclusions include simulation, mathematical random-graph theory, efficient graph computation, sampling, neural networks, economic theory, relational networks, and bipartite graphs.

The survey primarily addresses statistical network models and applications, so several related topics receive little or no coverage.
The survey does not cover efficient computation on networks, including shortest paths, diameter, centrality, and clustering calculations.
Network-based sampling, neural networks, and the links between networks, economic theory, and game theory are outside the survey’s scope.
Relational networks are excluded because their probabilistic graphical models represent uncertainty, whereas the networks reviewed are treated as given or arising from the studied system.
Bipartite graphs are largely excluded because they are seldom considered the best representation except for some binary measurements or comparable populations.
Excluded topics include agent-based modeling and probability theory associated with random graph models.

2.1 Motivations for Network Analysis

Network analysis serves different purposes across disciplines, including interpreting relations, explaining formation mechanisms, finding hidden groups, predicting missing information, and modeling propagation. The relevant questions depend on what network structure represents and what outcome is sought.

Social scientists model the meanings and structures of edges, including friendliness, strategic alliance, obligation, hierarchy, and transitivity.
Physicists seek parsimonious mechanisms explaining how networks acquire properties such as degree distributions or diameter at time t.
Computational biology uses networks to find hidden protein groups, annotate gene function, and identify common subgraphs across species.
Finding hidden groups and node roles supports applications such as detecting latent terrorist cells, identity disambiguation, and business organization analysis.
Machine-learning applications predict missing links or attributes, including product purchases inferred from friends’ purchasing patterns.
Network analysis models the propagation of viruses, HIV infection, marketing, gossip, disease, and information.

2.2 Sample Datasets

The review surveys network datasets spanning social relationships, communication, biology, health, and scholarly collaboration. It introduces six examples and highlights the questions and structures each dataset supports.

Network analysis draws on datasets covering interpersonal relations, email, protein interactions, health-related ties, and academic co-authorship.
The review presents six network examples, describes their data, and articulates specific questions of interest for each.
Sampson’s “Monastery” Study: Sampson’s monastery data record novices’ rankings of one another across four sociometric relations and four epochs.
The Enron Email Corpus: The Enron corpus includes multiple versions of email data, including roughly 225,000 messages among the top 151 executives from 1997 to 2004.
The Budding Yeast Protein Interaction Network: The budding-yeast example represents a protein interaction network used to study complexes and functional roles.
The Add Health Adolescent Relationship and HIV Transmission Study: The Add Health study constructed timed sexual-relationship networks from 14,738 adolescents and found a structure resembling a spanning tree.

Static Network Models

Static network models analyze a single realized network through local and global statistics. The review contrasts random-graph generalizations with statistical models developed for social networks.

Static network models focus on network statistics and on how well models capture important features of observed networks.
One modeling lineage extends the Erdös-Rényi-Gilbert model toward scale-free degree distributions and exchangeable graphs with structured dependence.
A second lineage includes the p1 model and exponential random graph models for social-network structure.

3.1 Basic Notation and Terminology

The review represents a network through nodes and measurements on node pairs, usually stored in an adjacency matrix. Nodes denote units, while edges encode relationships or interactions.

A statistical network is represented as nodes together with pairwise measurements, commonly an N × N matrix.
The review primarily uses binary adjacency matrices for networks with directed edges.
Nodes may represent individuals, organizations, or other study units, while edges represent links, relationships, or interactions.
Edges may be directed, as in the Holland-Leinhardt model, or undirected, as in the Erdös-Rényi-Gilbert model.
The review generally follows computer-science terminology, using nodes and edges rather than actors and ties.

3.2 The Erd¨os-R´enyi-Gilbert Random Graph Model

The Erdös-Rényi-Gilbert family assigns edges through simple random-graph mechanisms and studies connectivity as edge probability changes. Its central asymptotic transition occurs at λ = pN = 1.

G(N, p) treats each possible edge as independently present with probability p, whereas G(N, E) fixes the number of edges.
The G(N, p) model has a binomial likelihood, while G(N, E) induces a uniform distribution over graphs with the specified edge count.
The key asymptotic parameter is λ = pN, and the model exhibits a phase change at λ = 1.
If λ < 1, the graph has no connected component larger than the logarithmic regime described by the model’s threshold results.
If λ tends to c > 1, a unique giant component contains a positive fraction of nodes, while every other component has at most O(log N) nodes almost surely.
The review notes that the model gives every node approximately the same number of neighbors, unlike the structure of many observed networks.

3.3 The Exchangeable Graph Model

The exchangeable graph model extends random graphs by giving nodes unobserved binary attributes that induce weakly dependent, exchangeable edges. The review uses this model to connect graph connectivity with node variability, structured components, information-based comparison, and model complexity.

Model construction: Node-specific K-bit binary strings generate directed edges through q, inducing edges that are conditionally independent given incident-node strings and exchangeable overall.The binary strings are equally probable, while the induced edge probabilities differ.
Model construction: The hypercube parameters μ⃗, σ, and α control bit frequency, variability, and correlation, while q maps binary-string pairs to [0, 1].A larger α increases negative bit correlation and produces a sparser network.
Interpretation: The model’s K bits capture graph complexity, with K < N providing graph compression and application-specific bits encoding properties such as protein domains.The distribution of I-bit matches can yield p-values for unexpected binding events among proteins sharing domain combinations.
Connectivity: A giant component forms when components connect through node strings matching on two bits, while three-component bridges are unlikely in a 100-node graph.Figure 3.1 illustrates bridge nodes between two connected components and the absence of nodes bridging three components.
Inference and comparison: Fitted exchangeable graph models support minimum-description-length assessments of bit complexity and information retained at different bit lengths.The model also enables comparisons based on sampled graph summaries such as information profiles and entropy histograms.
Interpretation: The model introduces controlled weak edge dependence to produce structured connectivity and enable information-theoretic comparison while linking connectivity to node attributes.Its stated focus is the technical link between graph connectivity and node attributes rather than modeling complexity itself.

3.4 The p1 Model for Social Networks

The p1 model represents directed social-network dyads through four possible edge states, with parameters for expansiveness, popularity, baseline structure, and reciprocation. Its log-linear and contingency-table formulations support estimation and extensions, but general reciprocation parameters lack identification and node-specific effects lack standard asymptotics.

Model formulation: The p1 model records whether each directed dyad contains no edge, one directed edge in either direction, or reciprocal edges.These four dyadic states form the basis of its probability specification.
Model formulation: Parameters represent outgoing expansiveness α_i, incoming popularity β_j, baseline dyad normalization λ_ij, and reciprocation ρ_ij.The model is log-linear in these effects.
Reciprocation: Reciprocation ρ_ij multiplies the odds of a mutual dyad by exp(ρ_ij) beyond independent-edge expectations.Constant reciprocation uses one common ρ, whereas edge-dependent reciprocation adds node-specific effects.
Identifiability: Special identifiable cases include no node effects or no reciprocal effect, while the unrestricted p1 representation has unidentifiable reciprocation parameters.The no-reciprocity case focuses on in- and out-degree distributions.
Estimation: The likelihood has exponential-family form, with dyadic degree and mutuality statistics serving as minimal sufficient statistics for iterative maximum-likelihood estimation.Contingency-table representations provide an alternative formulation for dyad data and multiple relations.
Limitations: Because the numbers of expansiveness and popularity effects grow with network size, standard asymptotics and simple goodness-of-fit tests are unavailable for p1 maximum-likelihood estimates.The literature describes ad hoc fixes for this problem.
Extensions: p2 models reinterpret node expansiveness and popularity effects as draws from underlying distributions, while Bayesian p1 extensions can also randomize other unknown quantities and add hierarchy.MCMC implementations have been applied to networks with 1,232 pupils across 20 Dutch high schools.

3.6 Exponential Random Graph Models

Exponential random graph models represent network distributions through statistics counting structures such as edges, triangles, and stars. Their estimation and interpretation are complicated by overlapping statistics, likelihood degeneracy, and sensitivity to approximations that ignore dependence.

Model basis: Markov graph distributions assume that two possible edges are dependent only when they share a node.This assumption characterizes a class of undirected Markov graphs.
Model formulation: ERGMs generalize Markov graphs by replacing selected structure counts with arbitrary graph statistics in exponential-family likelihoods.The statistics count graph structures, including edges, triangles, and k-stars.
Model formulation: Overlapping statistics create parameter dependence because edges belong to 2-stars, while 2-stars can belong to triangles and three-stars.These dependencies complicate interpretation and estimation.
Estimation: Pseudo-likelihood estimation treats overlapping graph statistics as independent, causing extreme sensitivity of predicted edge counts to small parameter changes.Later variants mitigate but do not eliminate the double-counting problem.
Limitations: A central limitation is near-degeneracy: some parameter combinations yield multiple distinct likelihood modes and only a few radically different networks with nonzero probability.This complicates maximum-likelihood estimation and goodness-of-fit assessment.
Estimation: ERGMs can use variational approximations and Monte Carlo methods to make derivatives, likelihood calculations, and EM procedures feasible, although computational cost may remain high.The exponential-family formulation supports these methodological tools.

3.7 Random Graph Models with Fixed Degree Distribution

Fixed-degree-distribution random graph models extend the symmetric Erdős–Rényi–Gilbert model toward hubs, local clustering, triadic closure, and prescribed degree sequences. Conditioning on degree-related statistics is used to address degeneracies, but exact sampling remains technically difficult.

Model extensions: The Erdős–Rényi–Gilbert model gives every node the same expected degree, whereas extensions allow node degrees to vary.Its expected degree follows a binomial distribution.
Model extensions: Preferential attachment models capture hubs, while small-world models interpolate between ordered lattices and random graphs to produce local clustering and triadic closure.These are natural extensions of the Erdős–Rényi–Gilbert model.
Degree distributions: Statistical-physics network models often emphasize empirical degree distributions and may fix degree-distribution parameters or condition distributions on degree sequences.This literature includes variations that control network growth or differential edge addition and deletion.
Connections: In p1 models, α_i and β_i represent node out-degree and in-degree effects, linking degree-distribution modeling to statistical network parameters.This connects statistical-physics treatments with sociological network models.
Limitations: Conditioning on degree-related statistics is used to avoid degeneracies and near-degeneracies associated with unconditional maximum likelihood in exponential random graph models.Related conditional-generation algorithms require careful handling of Markov bases and may not reach all possible tables.
Connections: Efficient mechanisms exist for generating random graphs with fixed degree sequences, explicitly linking statistical-physics and sociological network literatures.The cited work contrasts fixed-degree graph generation with maximum-likelihood approaches.

3.8 Blockmodels, Stochastic Blockmodels and Community Discovery

Blockmodels group nodes by similar connectivity patterns to other blocks rather than necessarily by direct ties. The review covers their historical foundations, stochastic and mixed-membership formulations, inference challenges, and community-discovery implications.

Structural equivalence: Blockmodels formalize structural equivalence by grouping nodes whose connectivity patterns with nodes in other blocks are similar.The definition depends on a partition into K blocks and a suitable distance metric for comparing connectivity patterns.
Structural equivalence: Unlike ordinary clustering, structurally equivalent nodes need not connect directly to one another; they may instead share directed connectivity patterns to other blocks.In the example, green nodes have no direct connections among themselves but connect to blue nodes and receive connections from red nodes.
Stochastic blockmodels: A blockmodel uses a K × K block-connectivity matrix B and a node-to-block membership mapping Π to represent global relations and node memberships.The entry B(g, h) can specify the average probability of directed connections from block g to block h.
Stochastic blockmodels: Mixed-membership blockmodels allow context-dependent group membership, with separate latent memberships for sending and receiving interactions.The two membership indicators need not be equal, which supports asymmetric interaction networks; equality can be imposed for symmetric networks.
Inference: Inference is difficult because the likelihood’s outer integral is analytically intractable and the number of observations scales as O(N^2).The review describes nested variational inference as an approximation because exact inference is unavailable and MCMC is often too slow for real-size networks.
Community discovery: Bickel and Chen show that modularity-based community detection can be asymptotically biased, whereas blockmodel likelihood methods are asymptotically unbiased under their result.Their proof uses exchangeability results applied to paired measurements and concerns even large graphs with substantial communities.

3.9 Latent Space Models

Latent space models represent nodes as points in a low-dimensional space, with relational probabilities shaped by distances, covariates, and model parameters. The review compares these models with clustering and blockmodel approaches, emphasizing interpretability, inference, and scalability.

Latent space formulation: Latent space models represent each node as a point in a low-dimensional space, where edge existence depends on pairwise distance and node-level covariates.For binary networks, closer latent representations make edges more likely in the model described.
Latent space formulation: In Hoff et al.’s model, each relationship is sampled from a Bernoulli distribution whose natural parameter depends on latent positions, pair-specific covariates, and parameters.The log-odds combines an intercept, covariate effects, and a distance penalty.
Model extensions: Latent space models can extend to weighted networks through generalized linear models that specify an error model, linear predictor, and link function.The reviewed examples include Bernoulli models for binary edges and Poisson models for nonnegative integer edge weights.
Inference and scalability: MCMC inference has reached networks with several thousand nodes, but scalability remains unresolved for larger networks.Variational methods for mixed-membership models can scale to very large matrices, though the associated accuracy cost is described as unknown.
Clustering and comparison: The original latent space model has no explicit clustering component, so inferred latent positions must be clustered separately to identify groups.A joint extension combines latent positions with a finite Gaussian mixture model, while mixed-membership blockmodels use latent membership vectors.
Clustering and comparison: Latent space models are interpretable through distances, whereas eigenmodels can capture more connectivity patterns at comparable complexity but are less interpretable.Latent class models are described as the easiest to interpret because their patterns correspond to blocks or tight micro-communities.

Appendix: Phase Transition Behavior of the Erd¨os-R´enyi-Gilbert Model

The appendix explains the Erdős–Rényi–Gilbert model’s phase transition through branching processes. When branching supports intersect with high probability, a giant component emerges in which every node can reach every other.

Phase transition: At λ = 1, giant-component emergence can be analyzed as a branching process started from every node.For suitable λ values, the branching processes continue growing with high probability.
Phase transition: A giant component forms when the supports of growing branching processes intersect with high probability.The resulting component G contains nodes reachable from every other node.
Formal argument: The formal argument explores a graph from a selected node by repeatedly adding unsaturated nodes and their previously unseen neighbors to a list.A node is saturated in G when it is connected to all nodes in G.

Dynamic Models for Longitudinal Data

Dynamic network models describe changing network structure, support inference about evolving latent positions and relationships, and can explain or predict network states over time. The review also emphasizes unresolved challenges in model fit, missing data, scalability, and identifiable mechanisms.

Dynamic latent space models: Dynamic latent-position models track researchers over time, providing insight into the evolution of the machine learning community.
Dynamic latent space models: Kalman-filter-like inference can estimate posterior distributions for author positions while simultaneously embedding authors and words in a two-mode network.The procedure was applied to a simulated NIPS dataset.
Dynamic latent space models: Dynamic latent models can explain the network at each time step and efficiently predict its future state, enabling analysis of large dynamic data collections.The approach lacks an explicit mechanism explaining the dynamics behind real networks.
Dynamic contextual friendship models: The Dynamic Contextual Friendship Model generates varied degree distributions and relationship dynamics, including temporary resumption of past relationships, at the cost of added complexity.
Open problems and challenges: Dynamic network modeling remains constrained by missing-data assumptions, limited predictive evaluation, and the absence of standard asymptotics for goodness-of-fit and model comparison.Missing-at-random assumptions are not generally correct, while network dependence and increasing parameter counts complicate inference.
Review scope and synthesis: The review maps connections among statistical network models while contrasting inference-oriented statistical approaches with physics-inspired models focused on generative mechanisms.