{{Short description|Random graph model in applied mathematics}} {{Network science}}
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.<ref name="van der Hoorn">{{cite news |title=Sparse Maximum-Entropy Random Graphs with a Given Power-Law Degree Distribution |last=van der Hoorn |first=Pim |author2=Gabor Lippner |author3=Dmitri Krioukov |date=2017-10-10 |arxiv = 1705.10261}}</ref> 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<ref name="Diego">{{cite news |last=Garlaschelli |first=Diego |author2=Frank den Hollander |author3=Andrea Roccaverde |date=January 30, 2018 |title=Coviariance structure behind breaking of ensemble equivalence in random graphs |url=http://eprints.imtlucca.it/4040/1/1711.04273.pdf |access-date=September 14, 2018 |archive-date=February 4, 2023 |archive-url=https://web.archive.org/web/20230204161609/http://eprints.imtlucca.it/4040/1/1711.04273.pdf |url-status=live }}</ref>). The SCM for graphs of size <math>n</math> has a nonzero probability of sampling any graph of size <math>n</math>, 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 <math>G</math> having <math>n</math> vertices (<math>n=|V(G)|</math>) labeled <math>\{v_j\}_{j=1}^n=V(G)</math>, producing a probability distribution on <math>\mathcal{G}_n</math> (the set of graphs of size <math>n</math>). Imposed on the ensemble are <math>n</math> constraints, namely that the ensemble average of the degree <math>k_j</math> of vertex <math>v_j</math> is equal to a designated value <math>\widehat{k}_j</math>, for all <math>v_j\in V(G)</math>. The model is fully parameterized by its size <math>n</math> and expected degree sequence <math>\{\widehat{k}_j\}_{j=1}^n</math>. 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.<ref name="Diego" /> The conditions <math>\langle k_j \rangle = \widehat{k}_j</math> are imposed on the ensemble by the method of Lagrange multipliers (see Maximum-entropy random graph model).
==Derivation of the probability distribution== The probability <math>\mathbb{P}_\text{SCM}(G)</math> of the SCM producing a graph <math>G</math> is determined by maximizing the Gibbs entropy <math>S[G]</math> subject to constraints <math>\langle k_j \rangle = \widehat{k}_j, \ j=1,\ldots,n</math> and normalization <math>\sum_{G\in \mathcal{G}_n}\mathbb{P}_\text{SCM}(G)=1</math>. This amounts to optimizing the multi-constraint Lagrange function below:
: <math> \begin{align} & \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{align} </math>
where <math>\alpha</math> and <math>\{\psi_j\}_{j=1}^n</math> are the <math>n+1</math> multipliers to be fixed by the <math>n+1</math> constraints (normalization and the expected degree sequence). Setting to zero the derivative of the above with respect to <math>\mathbb{P}_\text{SCM}(G)</math> for an arbitrary <math>G\in \mathcal{G}_n</math> yields
: <math> 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_jk_j(G)\right],</math>
the constant <math>Z:=e^{\alpha+1}=\sum_{G\in\mathcal{G}_n}\exp\left[-\sum_{j=1}^n\psi_jk_j(G)\right]=\prod_{1\le i < j \le n}\left(1+e^{-(\psi_i+\psi_j)}\right)</math><ref name="Park">{{cite news |title=The statistical mechanics of networks |last=Park |first=Juyong |author2=M.E.J. Newman |date=2004-05-25 |arxiv = cond-mat/0405566}}</ref> being the partition function normalizing the distribution; the above exponential expression applies to all <math>G\in\mathcal{G}_n</math>, and thus is the probability distribution. Hence we have an exponential family parameterized by <math>\{\psi_j\}_{j=1}^n</math>, which are related to the expected degree sequence <math>\{\widehat{k}_j\}_{j=1}^n</math> by the following equivalent expressions:
: <math> \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\ne q}\frac{1}{e^{\psi_q+\psi_j}+1} = \widehat{k}_q, \ q=1,\ldots,n.</math>
==References== {{Reflist}}
Category:Random graphs Category:Statistical ensembles