In applied mathematics, the soft configuration model (SCM) is a random graph model subject to the principle of maximum entropy under constraints on the expectation of the degree sequence of sampled graphs. Whereas the configuration model (CM) uniformly samples random graphs of a specific degree sequence, the SCM only retains the specified degree sequence on average over all network realizations; in this sense the SCM has very relaxed constraints relative to those of the CM ("soft" rather than "sharp" constraints). The SCM for graphs of size n {\displaystyle n} has a nonzero probability of sampling any graph of size n {\displaystyle n} , whereas the CM is restricted to only graphs having precisely the prescribed connectivity structure.
Model formulation The SCM is a statistical ensemble of random graphs G {\displaystyle G} having n {\displaystyle n} vertices ( n = | V ( G ) | {\displaystyle n=|V(G)|} ) labeled { v j } j = 1 n = V ( G ) {\displaystyle \{v_{j}\}_{j=1}^{n}=V(G)} , producing a probability distribution on G n {\displaystyle {\mathcal {G}}_{n}} (the set of graphs of size n {\displaystyle n} ). Imposed on the ensemble are n {\displaystyle n} constraints, namely that the ensemble average of the degree k j {\displaystyle k_{j}} of vertex v j {\displaystyle v_{j}} is equal to a designated value k ^ j {\displaystyle {\widehat {k}}_{j}} , for all v j ∈ V ( G ) {\displaystyle v_{j}\in V(G)} . The model is fully parameterized by its size n {\displaystyle n} and expected degree sequence { k ^ j } j = 1 n {\displaystyle \{{\widehat {k}}_{j}\}_{j=1}^{n}} . These constraints are both local (one constraint associated with each vertex) and soft (constraints on the ensemble average of certain observable quantities), and thus yields a canonical ensemble with an extensive number of constraints. The conditions ⟨ k j ⟩ = k ^ j {\displaystyle \langle k_{j}\rangle ={\widehat {k}}_{j}} are imposed on the ensemble by the method of Lagrange multipliers (see Maximum-entropy random graph model).
Derivation of the probability distribution The probability P SCM ( G ) {\displaystyle \mathbb {P} _{\text{SCM}}(G)} of the SCM producing a graph G {\displaystyle G} is determined by maximizing the Gibbs entropy S [ G ] {\displaystyle S[G]} subject to constraints ⟨ k j ⟩ = k ^ j , j = 1 , … , n {\displaystyle \langle k_{j}\rangle ={\widehat {k}}_{j},\ j=1,\ldots ,n} and normalization ∑ G ∈ G n P SCM ( G ) = 1 {\displaystyle \sum _{G\in {\mathcal {G}}_{n}}\mathbb {P} _{\text{SCM}}(G)=1} . This amounts to optimizing the multi-constraint Lagrange function below:
L ( α , { ψ j } j = 1 n ) =
… excerpt ends here. Continue reading the full article.
