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 (at a fixed set of parameter values) 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 (e.g. biological network inference). Each model defines a family of probability distributions on the set of graphs  of size formula_1 (for each formula_2 for some finite formula_3), parameterized by a collection of constraints on formula_4 observables formula_5 defined for each graph formula_6 (such as fixed expected average degree, degree distribution of a particular form, or specific degree sequence), 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 formula_7  and formula_8 (which each have one global constraint on the number of edges), as well as the configuration model (CM). and soft configuration model (SCM) (which each have formula_1 local constraints, one for each nodewise degree-value). In the two pairs of models mentioned above, an important distinction is in whether the constraint is sharp (i.e. satisfied by every element of the set of size-formula_1 graphs with nonzero probability in the ensemble), or soft (i.e. satisfied on average across the whole ensemble). The former (sharp) case corresponds to a microcanonical ensemble, the condition of maximum entropy yielding all graphs  formula_6 satisfying formula_12 as equiprobable; the latter (soft) case is canonical, producing an exponential random graph model (ERGM). </math> Canonical ensemble of graphs (general framework). Suppose we are building a random graph model consisting of a probability distribution formula_17 on the set formula_18 of simple graphs with formula_1 vertices. The Gibbs entropy formula_20 of this ensemble will be given by We would like the ensemble-averaged values formula_22 of observables formula_5 (such as average degree, average clustering, or average shortest path length) to be tunable, so we impose formula_4 "soft" constraints on the graph distribution: where formula_26 label  the constraints. Application of the method of Lagrange multipliers to determine the distribution formula_17 that maximizes formula_20 while satisfying formula_29, and the normalization condition formula_30 results in the following: where formula_32 is a normalizing constant (the partition function) and formula_33 are parameters (Lagrange multipliers) 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 formula_7. In the canonical framework above, constraints were imposed on ensemble-averaged quantities formula_35. Although these  properties will on average take on values specifiable by appropriate setting of formula_33, each specific instance formula_6 may have formula_38, which may be undesirable. Instead, we may impose a much stricter condition: every graph with nonzero probability must satisfy formula_39 exactly. Under these "sharp" constraints, the maximum-entropy distribution is determined. We exemplify this with the Erdős–Rényi model formula_7. The sharp constraint in formula_7 is that of a fixed number of edges formula_42, that is formula_43, for all graphs formula_6 drawn from the ensemble (instantiated with a probability denoted formula_45). This restricts the sample space from formula_18 (all graphs  on formula_1 vertices) to the subset formula_48. 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 formula_49, we have no external constraints (besides normalization) to satisfy, and thus we'll select formula_45 to maximize formula_20 without making use of Lagrange multipliers. It is well known that the entropy-maximizing distribution in the absence of external constraints is the uniform distribution over the sample space (see maximum entropy probability distribution ), from which we obtain: where the last expression in terms of binomial coefficients is the number of ways to place formula_42 edges among formula_54 possible edges, and thus is the cardinality of formula_49. Generalizations. A variety of maximum-entropy ensembles have been studied on generalizations of simple graphs. These include, for example, ensembles of simplicial complexes, and weighted random graphs with a given expected degree sequence