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}$ 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.

Model formulation

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

Derivation of the probability distribution

The probability ${\displaystyle \mathbb {P} _{\text{SCM}}(G)}$ of the SCM producing a graph ${\displaystyle G}$ is determined by maximizing the Gibbs entropy ${\displaystyle S[G]}$ subject to constraints ${\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}$. 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}}}$

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 {\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)}$[3] being the partition 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 an exponential family parameterized by ${\displaystyle \{\psi _{j}\}_{j=1}^{n}}$, which are related to the expected degree sequence ${\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.}$

References

1. van der Hoorn, Pim; Gabor Lippner; Dmitri Krioukov (2017-10-10). "Sparse Maximum-Entropy Random Graphs with a Given Power-Law Degree Distribution". arXiv:1705.10261.
2. Garlaschelli, Diego; Frank den Hollander; Andrea Roccaverde (January 30, 2018). "Coviariance structure behind breaking of ensemble equivalence in random graphs" (PDF).
3. Park, Juyong; M.E.J. Newman (2004-05-25). "The statistical mechanics of networks". arXiv:cond-mat/0405566.