Maximum-entropy random graph models arerandom graph models used to studycomplex networks subject to theprinciple of maximum entropy under a set of structural constraints,^[1] which may be global, distributional, or local.

Any random graph model (at a fixed set of parameter values) results in aprobability distribution ongraphs, and those that are maximumentropy within the considered class of distributions have the special property of being maximallyunbiasednull models for network inference^[2] (e.g.biological network inference). Each model defines a family of probability distributions on the set of graphs of size${\displaystyle n}$ (for each${\displaystyle n>n_0}$ for some finite${\displaystyle n_0}$), parameterized by a collection of constraints on${\displaystyle J}$ observables${\displaystyle \{Q_j(G){\}}_{j=1}^J}$ defined for each graph${\displaystyle G}$ (such as fixed expected averagedegree,degree distribution of a particular form, or specificdegree sequence), enforced in the graph distribution alongside entropy maximization by themethod of Lagrange multipliers. Note that in this context "maximum entropy" refers not to theentropy 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 theER graphs${\displaystyle G(n,m)}$ and${\displaystyle G(n,p)}$ (which each have one global constraint on the number of edges), as well as theconfiguration model (CM).^[3] andsoft configuration model (SCM) (which each have${\displaystyle n}$ local constraints, one for each nodewise degree-value). In the two pairs of models mentioned above, an important distinction^[4][5] is in whether the constraint is sharp (i.e. satisfied by every element of the set of size-${\displaystyle n}$ graphs with nonzero probability in the ensemble), or soft (i.e. satisfied on average across the whole ensemble). The former (sharp) case corresponds to amicrocanonical ensemble,^[6] the condition of maximum entropy yielding all graphs${\displaystyle G}$ satisfying${\displaystyle Q_j(G)=q_j\mathrm{\forall }j}$ as equiprobable; the latter (soft) case iscanonical,^[7] producing anexponential random graph model (ERGM).

Model	Constraint type	Constraint variable	Probability distribution
ER,${\displaystyle G(n,m)}$	Sharp, global	Total edge-count${\displaystyle |E(G)|}$	${\displaystyle 1/(\genfrac{}{}{0ex}{}{(\genfrac{}{}{0ex}{}{n}{2})}{m});m=|E(G)|}$
ER,${\displaystyle G(n,p)}$	Soft, global	Expected total edge-count${\displaystyle |E(G)|}$	${\displaystyle p^{|E(G)|}(1-p{)}^{(\genfrac{}{}{0ex}{}{n}{2})-|E(G)|}}$
Configuration model	Sharp, local	Degree of each vertex,${\displaystyle \{{\hat{k}}_j{\}}_{j=1}^n}$	${\displaystyle 1/\left|\mathrm{\Omega }(\{{\hat{k}}_j{\}}_{j=1}^n)\right|;\mathrm{\Omega }(\{k_j{\}}_{j=1}^n)=\{g\in {\mathcal{G}}_n:k_j(g)={\hat{k}}_j\mathrm{\forall }j\}\subset {\mathcal{G}}_n}$
Soft configuration model	Soft, local	Expected degree of each vertex,${\displaystyle \{{\hat{k}}_j{\}}_{j=1}^n}$	${\displaystyle Z^{-1}\exp \left[-\sum _{j=1}^n{\psi }_j{k}_j(G)\right];-\frac{\mathrm{\partial }\ln Z}{\mathrm{\partial }{\psi }_j}={\hat{k}}_j}$

Suppose we are building a random graph model consisting of a probability distribution${\displaystyle \mathbb{P}(G)}$ on the set${\displaystyle {\mathcal{G}}_n}$ ofsimple graphs with${\displaystyle n}$ vertices. TheGibbs entropy${\displaystyle S[G]}$ of this ensemble will be given by

${\displaystyle S[G]=-\sum _{G\in {\mathcal{G}}_n}\mathbb{P}(G)\log \mathbb{P}(G).}$

We would like the ensemble-averaged values${\displaystyle \{⟨Q_j⟩{\}}_{j=1}^J}$ of observables${\displaystyle \{Q_j(G){\}}_{j=1}^J}$ (such as averagedegree, averageclustering, oraverage shortest path length) to be tunable, so we impose${\displaystyle J}$ "soft" constraints on the graph distribution:

${\displaystyle ⟨Q_j⟩=\sum _{G\in {\mathcal{G}}_n}\mathbb{P}(G)Q_j(G)=q_j,}$

where${\displaystyle j=1,...,J}$ label the constraints. Application of the method of Lagrange multipliers to determine the distribution${\displaystyle \mathbb{P}(G)}$ that maximizes${\displaystyle S[G]}$ while satisfying${\displaystyle ⟨Q_j⟩=q_j}$, and the normalization condition${\displaystyle \sum _{G\in {\mathcal{G}}_n}\mathbb{P}(G)=1}$ results in the following:^[1]

${\displaystyle \mathbb{P}(G)=\frac{1}{Z}\exp \left[-\sum _{j=1}^J{\psi }_j{Q}_j(G)\right],}$

where${\displaystyle Z}$ is a normalizing constant (thepartition function) and${\displaystyle \{{\psi }_j{\}}_{j=1}^J}$ 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 andcanonical ensemble; specifically yielding anERGM.

In the canonical framework above, constraints were imposed on ensemble-averaged quantities${\displaystyle ⟨Q_j⟩}$. Although these properties will on average take on values specifiable by appropriate setting of${\displaystyle \{{\psi }_j{\}}_{j=1}^J}$, each specific instance${\displaystyle G}$ may have${\displaystyle Q_j(G)\ne q_j}$, which may be undesirable. Instead, we may impose a much stricter condition: every graph with nonzero probability must satisfy${\displaystyle Q_j(G)=q_j}$ exactly. Under these "sharp" constraints, the maximum-entropy distribution is determined. We exemplify this with the Erdős–Rényi model${\displaystyle G(n,m)}$.

The sharp constraint in${\displaystyle G(n,m)}$ is that of a fixed number ofedges${\displaystyle m}$,^[8] that is${\displaystyle |\mathrm{E}(G)|=m}$, for all graphs${\displaystyle G}$ drawn from the ensemble (instantiated with a probability denoted${\displaystyle {\mathbb{P}}_{n,m}(G)}$). This restricts the sample space from${\displaystyle {\mathcal{G}}_n}$ (all graphs on${\displaystyle n}$ vertices) to the subset${\displaystyle {\mathcal{G}}_{n,m}=\{g\in {\mathcal{G}}_n;|\mathrm{E}(g)|=m\}\subset {\mathcal{G}}_n}$. This is in direct analogy to themicrocanonical ensemble in classicalstatistical mechanics, wherein the system is restricted to a thin manifold in thephase space of all states of a particularenergy value.

Upon restricting our sample space to${\displaystyle {\mathcal{G}}_{n,m}}$, we have no external constraints (besides normalization) to satisfy, and thus we'll select${\displaystyle {\mathbb{P}}_{n,m}(G)}$ to maximize${\displaystyle S[G]}$ without making use of Lagrange multipliers. It is well known that the entropy-maximizing distribution in the absence of external constraints is theuniform distribution over the sample space (seemaximum entropy probability distribution), from which we obtain:

${\displaystyle {\mathbb{P}}_{n,m}(G)=\frac{1}{|{\mathcal{G}}_{n,m}|}={(\genfrac{}{}{0ex}{}{(\genfrac{}{}{0ex}{}{n}{2})}{m})}^{-1},}$

where the last expression in terms ofbinomial coefficients is the number of ways to place${\displaystyle m}$ edges among${\displaystyle (\genfrac{}{}{0ex}{}{n}{2})}$ possibleedges, and thus is thecardinality of${\displaystyle {\mathcal{G}}_{n,m}}$.

A variety of maximum-entropy ensembles have been studied on generalizations of simple graphs. These include, for example, ensembles of simplicial complexes,^[9] and weighted random graphs with a given expected degree sequence^[10]

• Principle of maximum entropy
• Maximum entropy probability distribution
• Method of Lagrange multipliers
• Null model
• Random graph
• Exponential random graph model
• Canonical ensemble
• Microcanonical ensemble

• Random graphs