Soft configuration model explained

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

n has a nonzero probability of sampling any graph of size 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 having n vertices (n = |V(G)| ) labeled \{v _{j\}} ^{n = V(G)} ^{j =1} , producing a probability distribution on l{G} _{n} (the set of graphs of size n ). Imposed on the ensemble are n constraints, namely that the ensemble average of the degree k _{j} of vertex v _{j} is equal to a designated value \widehat{k} _{j} , for all v _{j\in} V(G) . The model is fully parameterized by its size n and expected degree sequence \{\widehat{k} _{j\}} ^{n} ^{j =1} . 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 \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)} of the SCM producing a graph G is determined by maximizing the Gibbs entropy S[G] subject to constraints \langle k _{j} \rangle = \widehat{k} _{j,} j =1 ,\ldots,n and normalization \sum _{G\in} _{n}P} _{SCM(G)=1} . This amounts to optimizing the multi-constraint Lagrange function below:\begin{align} & l{L}\left(\alpha,\{\psi _{j\}} ^{n\right)} ^{j =1} \\[ 6 pt] = {} & - \sum _{G\inl{G} _{n}P} _{SCM(G)logP} _{SCM(G)} + \alpha\left( 1- \sum _{G\in} _{n}P} _{SCM(G)} \right) + \sum ^{n\psi} _{j\left(\widehat{k}} _{j-\sum} _{G\inl{G} _{n}P} _{SCM(G)k} _{j(G)\right), \end{align}}

where

\alpha and \{\psi _{j\}} ^{n} ^{j =1} are the n +1 multipliers to be fixed by the n +1 constraints (normalization and the expected degree sequence). Setting to zero the derivative of the above with respect to P _{SCM(G)} for an arbitrary G\in l{G} _{n} yields0 = (\partial l{L)/(\left(\alpha,\{\psi) _{j\}} ^{n\right)}{\partial} ^{j =1} P _{SCM(G)}=} -log P _{SCM(G)} -1- \alpha - \sum ^{n\psi} _{j} k _{j(G)} ⇒ P _{SCM (G) = (1)/(Z)} \exp\left[ - \sum ^{n\psi} _{jk} _{j(G)\right],}

the constant

Z: = e ^{\alpha+1} = \sum _{G\inl{G} _{n}\exp\left[-\sum} ^{n\psi} ^{jk} _{j(G)\right]=\prod} _{1\le} \left( 1+ e ^{- (\psi _{i+\psi} _{j)}} \right) ^[3] being the partition function normalizing the distribution; the above exponential expression applies to all G\in l{G} _{n} , and thus is the probability distribution. Hence we have an exponential family parameterized by \{\psi _{j\}} ^{n} ^{j =1} , which are related to the expected degree sequence \{\widehat{k} _{j\}} ^{n} ^{j =1} by the following equivalent expressions:\langle k _{q} \rangle = \sum _{G\in} _{n}k} _{q(G)P} _{SCM(G)} =- (\partial log Z)/(\partial \psi _{q}) = \sum _{j\ne} (1)/(e ^{\psi _{q+\psi} _{j}} +1) = \widehat{k} _{q,} q =1 ,\ldots,n.

Notes and References

1. News: Sparse Maximum-Entropy Random Graphs with a Given Power-Law Degree Distribution. van der Hoorn. Pim. Gabor Lippner. Dmitri Krioukov. 2017-10-10. 1705.10261.
2. News: Garlaschelli. Diego. Frank den Hollander. Andrea Roccaverde. January 30, 2018. Coviariance structure behind breaking of ensemble equivalence in random graphs. September 14, 2018. February 4, 2023. https://web.archive.org/web/20230204161609/http://eprints.imtlucca.it/4040/1/1711.04273.pdf. live.
3. News: The statistical mechanics of networks. Park. Juyong. M.E.J. Newman. 2004-05-25. cond-mat/0405566.