Soft configuration model

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.^[1] 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^[2] ). The SCM for graphs of size ${\displaystyle n}${\displaystyle n} has a nonzero probability of sampling any graph of size ${\displaystyle n}${\displaystyle n}, whereas the CM is restricted to only graphs having precisely the prescribed connectivity structure.

The SCM is a statistical ensemble of random graphs ${\displaystyle G}${\displaystyle G} having ${\displaystyle n}${\displaystyle n} vertices (${\displaystyle n=|V(G)|}${\displaystyle n=|V(G)|}) labeled ${\displaystyle \{v_{j}\}_{j=1}^{n}=V(G)}${\displaystyle \{v_{j}\}_{j=1}^{n}=V(G)}, producing a probability distribution on ${\displaystyle {\mathcal {G}}_{n}}${\displaystyle {\mathcal {G}}_{n}} (the set of graphs of size ${\displaystyle n}${\displaystyle n}). Imposed on the ensemble are ${\displaystyle n}${\displaystyle n} constraints, namely that the ensemble average of the degree ${\displaystyle k_{j}}${\displaystyle k_{j}} of vertex ${\displaystyle v_{j}}${\displaystyle v_{j}} is equal to a designated value ${\displaystyle {\widehat {k}}_{j}}${\displaystyle {\widehat {k}}_{j}}, for all ${\displaystyle v_{j}\in V(G)}${\displaystyle v_{j}\in V(G)}. The model is fully parameterized by its size ${\displaystyle n}${\displaystyle n} and expected degree sequence ${\displaystyle \{{\widehat {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.^[2] The conditions ${\displaystyle \langle k_{j}\rangle ={\widehat {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).

The probability ${\displaystyle \mathbb {P} _{\text{SCM}}(G)}${\displaystyle \mathbb {P} _{\text{SCM}}(G)} of the SCM producing a graph ${\displaystyle G}${\displaystyle G} is determined by maximizing the Gibbs entropy ${\displaystyle S[G]}${\displaystyle S[G]} subject to constraints ${\displaystyle \langle k_{j}\rangle ={\widehat {k}}_{j},\ j=1,\ldots ,n}${\displaystyle \langle k_{j}\rangle ={\widehat {k}}_{j},\ j=1,\ldots ,n} and normalization ${\displaystyle \sum _{G\in {\mathcal {G}}_{n}}\mathbb {P} _{\text{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:

${\displaystyle {\begin{aligned}&{\mathcal {L}}\left(\alpha ,\{\psi _{j}\}_{j=1}^{n}\right)\\[6pt]={}&-\sum _{G\in {\mathcal {G}}_{n}}\mathbb {P} _{\text{SCM}}(G)\log \mathbb {P} _{\text{SCM}}(G)+\alpha \left(1-\sum _{G\in {\mathcal {G}}_{n}}\mathbb {P} _{\text{SCM}}(G)\right)+\sum _{j=1}^{n}\psi _{j}\left({\widehat {k}}_{j}-\sum _{G\in {\mathcal {G}}_{n}}\mathbb {P} _{\text{SCM}}(G)k_{j}(G)\right),\end{aligned}}}${\displaystyle {\begin{aligned}&{\mathcal {L}}\left(\alpha ,\{\psi _{j}\}_{j=1}^{n}\right)\\[6pt]={}&-\sum _{G\in {\mathcal {G}}_{n}}\mathbb {P} _{\text{SCM}}(G)\log \mathbb {P} _{\text{SCM}}(G)+\alpha \left(1-\sum _{G\in {\mathcal {G}}_{n}}\mathbb {P} _{\text{SCM}}(G)\right)+\sum _{j=1}^{n}\psi _{j}\left({\widehat {k}}_{j}-\sum _{G\in {\mathcal {G}}_{n}}\mathbb {P} _{\text{SCM}}(G)k_{j}(G)\right),\end{aligned}}}

where ${\displaystyle \alpha }${\displaystyle \alpha } and ${\displaystyle \{\psi _{j}\}_{j=1}^{n}}${\displaystyle \{\psi _{j}\}_{j=1}^{n}} are the ${\displaystyle n+1}${\displaystyle n+1} multipliers to be fixed by the ${\displaystyle n+1}${\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)}${\displaystyle \mathbb {P} _{\text{SCM}}(G)} for an arbitrary ${\displaystyle G\in {\mathcal {G}}_{n}}${\displaystyle G\in {\mathcal {G}}_{n}} yields

${\displaystyle 0={\frac {\partial {\mathcal {L}}\left(\alpha ,\{\psi _{j}\}_{j=1}^{n}\right)}{\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],}${\displaystyle 0={\frac {\partial {\mathcal {L}}\left(\alpha ,\{\psi _{j}\}_{j=1}^{n}\right)}{\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 ${\displaystyle Z:=e^{\alpha +1}=\sum _{G\in {\mathcal {G}}_{n}}\exp \left[-\sum _{j=1}^{n}\psi _{j}k_{j}(G)\right]=\prod _{1\leq i<j\leq n}\left(1+e^{-(\psi _{i}+\psi _{j})}\right)}${\displaystyle Z:=e^{\alpha +1}=\sum _{G\in {\mathcal {G}}_{n}}\exp \left[-\sum _{j=1}^{n}\psi _{j}k_{j}(G)\right]=\prod _{1\leq i<j\leq n}\left(1+e^{-(\psi _{i}+\psi _{j})}\right)}^[3] being the partition function normalizing the distribution; the above exponential expression applies to all ${\displaystyle G\in {\mathcal {G}}_{n}}${\displaystyle G\in {\mathcal {G}}_{n}}, and thus is the probability distribution. Hence we have an exponential family parameterized by ${\displaystyle \{\psi _{j}\}_{j=1}^{n}}${\displaystyle \{\psi _{j}\}_{j=1}^{n}}, which are related to the expected degree sequence ${\displaystyle \{{\widehat {k}}_{j}\}_{j=1}^{n}}${\displaystyle \{{\widehat {k}}_{j}\}_{j=1}^{n}} by the following equivalent expressions:

${\displaystyle \langle k_{q}\rangle =\sum _{G\in {\mathcal {G}}_{n}}k_{q}(G)\mathbb {P} _{\text{SCM}}(G)=-{\frac {\partial \log Z}{\partial \psi _{q}}}=\sum _{j\neq q}{\frac {1}{e^{\psi _{q}+\psi _{j}}+1}}={\widehat {k}}_{q},\ q=1,\ldots ,n.}${\displaystyle \langle k_{q}\rangle =\sum _{G\in {\mathcal {G}}_{n}}k_{q}(G)\mathbb {P} _{\text{SCM}}(G)=-{\frac {\partial \log Z}{\partial \psi _{q}}}=\sum _{j\neq q}{\frac {1}{e^{\psi _{q}+\psi _{j}}+1}}={\widehat {k}}_{q},\ q=1,\ldots ,n.}

• Random graphs
• Statistical ensembles

• Articles with short description
• Short description matches Wikidata