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 n {\displaystyle n} (for each n > n 0 {\displaystyle n>n_{0}} for some finite n 0 {\displaystyle n_{0}} ), parameterized by a collection of constraints on J {\displaystyle J} observables { Q j ( G ) } j = 1 J {\displaystyle \{Q_{j}(G)\}_{j=1}^{J}} defined for each graph G {\displaystyle G} (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 G ( n , m ) {\displaystyle G(n,m)} and G ( n , p ) {\displaystyle G(n,p)} (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 n {\displaystyle n} 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- n {\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 a microcanonical ensemble, the condition of maximum entropy yielding all graphs G {\displaystyle G} satisfying Q j ( G ) = q j ∀ j {\displaystyle Q_{j}(G)=q_{j}\forall j} as equiprobable; the latter (soft) case is canonical, producing an exponential random graph model (ERGM).
Canonical ensemble of graphs (general framework) Suppose we are building a random graph model consisting of a probability distribution P ( G ) {\displaystyle \mathbb {P} (G)} on the set G n {\displaystyle {\mathcal {G}}_{n}} of simple graphs with n {\displaystyle n} vertices. The Gibbs entropy S [ G ] {\displaystyle S[G]} of this ensemble will be given by
S [ G ] = − ∑ G ∈ G n P ( G ) log P ( G ) . {\displaystyle S[G]=-\sum _{G\in {\mathcal {G}}_{n}}\mathbb {P} (G)\log \mathbb {P} (G).}
We would like the ensemble-averaged values { ⟨ Q j ⟩ } j = 1 J {\displaystyle \{\langle Q_{j}\rangle \}_{j=1}^{J}} of observables { Q j ( G ) } j = 1 J {\displaystyle \{Q_{j}(G)\}_{j=1}^{J}} (such as average degree, average clustering, or average shortest path length) to be tunable, so we impose J {\displaystyle J} "soft" constraints on the graph distribution:
⟨ Q j ⟩ = ∑ G ∈ G n P ( G ) Q j ( G ) = q j , {\displaystyle \langle Q_{j}\rangle =\sum _{G\in {\mathcal {G}}_{n}}\mathbb {P} (G)Q_{j}(G)=q_{j},}
… excerpt ends here. Continue reading the full article.
