In applied mathematics, thesoft configuration model (SCM) is arandom graph model subject to theprinciple of maximum entropy under constraints on theexpectation of thedegree sequence of sampledgraphs.^[1] Whereas theconfiguration 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^[2]). The SCM for graphs of size${\displaystyle n}$ has a nonzero probability of sampling any graph of size${\displaystyle n}$, whereas the CM is restricted to only graphs having precisely the prescribed connectivity structure.

The SCM is astatistical ensemble of random graphs${\displaystyle G}$ having${\displaystyle n}$ vertices (${\displaystyle n=|V(G)|}$) labeled${\displaystyle \{v_j{\}}_{j=1}^n=V(G)}$, producing aprobability distribution on${\displaystyle {\mathcal{G}}_n}$ (the set of graphs of size${\displaystyle n}$). Imposed on the ensemble are${\displaystyle n}$ constraints, namely that theensemble average of thedegree${\displaystyle k_j}$ of vertex${\displaystyle v_j}$ is equal to a designated value${\displaystyle {\hat{k}}_j}$, for all${\displaystyle v_j\in V(G)}$. The model is fullyparameterized by its size${\displaystyle n}$ and expected degree sequence${\displaystyle \{{\hat{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 acanonical ensemble with anextensive number of constraints.^[2] The conditions${\displaystyle ⟨k_j⟩={\hat{k}}_j}$ are imposed on the ensemble by themethod of Lagrange multipliers (seeMaximum-entropy random graph model).

The probability${\displaystyle {\mathbb{P}}_{\text{SCM}}(G)}$ of the SCM producing a graph${\displaystyle G}$ is determined by maximizing theGibbs entropy${\displaystyle S[G]}$ subject to constraints${\displaystyle ⟨k_j⟩={\hat{k}}_j,j=1,\dots ,n}$ and normalization${\displaystyle \sum _{G\in {\mathcal{G}}_n}{\mathbb{P}}_{\text{SCM}}(G)=1}$. This amounts tooptimizing the multi-constraintLagrange function below:

where${\displaystyle \alpha }$ and${\displaystyle \{{\psi }_j{\}}_{j=1}^n}$ are the${\displaystyle n+1}$ multipliers to be fixed by the${\displaystyle n+1}$ constraints (normalization and the expected degree sequence). Setting to zero the derivative of the above with respect to${\displaystyle {\mathbb{P}}_{\text{SCM}}(G)}$ for an arbitrary${\displaystyle G\in {\mathcal{G}}_n}$ yields

${\displaystyle 0=\frac{\mathrm{\partial }\mathcal{L}\left(\alpha ,\{{\psi }_j{\}}_{j=1}^n\right)}{\mathrm{\partial }{\mathbb{P}}_{\text{SCM}}(G)}=-\log {\mathbb{P}}_{\text{SCM}}(G)-1-\alpha -\sum _{j=1}^n{\psi }_j{k}_j(G)\Rightarrow {\mathbb{P}}_{\text{SCM}}(G)=\frac{1}{Z}\exp \left[-\sum _{j=1}^n{\psi }_j{k}_j(G)\right],}$

the constant^[3] being thepartition function normalizing the distribution; the above exponential expression applies to all${\displaystyle G\in {\mathcal{G}}_n}$, and thus is the probability distribution. Hence we have anexponential family parameterized by${\displaystyle \{{\psi }_j{\}}_{j=1}^n}$, which are related to the expected degree sequence${\displaystyle \{{\hat{k}}_j{\}}_{j=1}^n}$ by the following equivalent expressions:

${\displaystyle ⟨k_q⟩=\sum _{G\in {\mathcal{G}}_n}{k}_q(G){\mathbb{P}}_{\text{SCM}}(G)=-\frac{\mathrm{\partial }\log Z}{\mathrm{\partial }{\psi }_q}=\sum _{j\ne q}\frac{1}{e^{{\psi }_q+{\psi }_j}+1}={\hat{k}}_q,q=1,\dots ,n.}$

• Random graphs
• Statistical ensembles

• Articles with short description
• Short description matches Wikidata