Maximum-entropy random graph model
Maximum-entropy random graph models are random graph models used to study complex networks subject to the principle of maximum entropy under a set of structural constraints, which may be global, distributional, or local.
Overview
Any random graph model results in a probability distribution on graphs, and those that are maximum entropy within the considered class of distributions have the special property of being maximally unbiased null models for network inference. Each model defines a family of probability distributions on the set of graphs of size , parameterized by a collection of constraints on observables defined for each graph , enforced in the graph distribution alongside entropy maximization by the method of Lagrange multipliers. Note that in this context "maximum entropy" refers not to the entropy of a single graph, but rather the entropy of the whole probabilistic ensemble of random graphs.Several commonly studied random network models are in fact maximum entropy, for example the ER graphs and , as well as the configuration model. and soft configuration model . In the two pairs of models mentioned above, an important distinction is in whether the constraint is sharp, or soft. The former case corresponds to a microcanonical ensemble, the condition of maximum entropy yielding all graphs satisfying as equiprobable; the latter case is canonical, producing an exponential random graph model.
| Model | Constraint type | Constraint variable | Probability distribution |
| ER, | Sharp, global | Total edge-count | |
| ER, | Soft, global | Expected total edge-count | |
| Configuration model | Sharp, local | Degree of each vertex, | |
| Soft configuration model | Soft, local | Expected degree of each vertex, |
Canonical ensemble of graphs (general framework)
Suppose we are building a random graph model consisting of a probability distribution on the set of simple graphs with vertices. The Gibbs entropy of this ensemble will be given byWe would like the ensemble-averaged values of observables to be tunable, so we impose "soft" constraints on the graph distribution:
where label the constraints. Application of the method of Lagrange multipliers to determine the distribution that maximizes while satisfying, and the normalization condition results in the following:
where is a normalizing constant and are parameters coupled to the correspondingly indexed graph observables, which may be tuned to yield graph samples with desired values of those properties, on average; the result is an exponential family and canonical ensemble; specifically yielding an ERGM.
The Erdős–Rényi model
In the canonical framework above, constraints were imposed on ensemble-averaged quantities. Although these properties will on average take on values specifiable by appropriate setting of, each specific instance may have, which may be undesirable. Instead, we may impose a much stricter condition: every graph with nonzero probability must satisfy exactly. Under these "sharp" constraints, the maximum-entropy distribution is determined. We exemplify this with the Erdős–Rényi model.The sharp constraint in is that of a fixed number of Glossary of [graph theory terms#edge|edges], that is, for all graphs drawn from the ensemble. This restricts the sample space from to the subset. This is in direct analogy to the microcanonical ensemble in classical statistical mechanics, wherein the system is restricted to a thin manifold in the phase space of all states of a particular energy value.
Upon restricting our sample space to, we have no external constraints to satisfy, and thus we'll select to maximize without making use of Lagrange multipliers. It is well known that the entropy-maximizing distribution in the absence of external constraints is the Discrete [uniform distribution|uniform distribution] over the sample space, from which we obtain:
where the last expression in terms of binomial coefficients is the number of ways to place edges among possible edges, and thus is the cardinality of.