Soft configuration model

In applied mathematics, the soft configuration model (SCM) is a

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}\}_{j=1}^{n}=V(G)

, producing a probability distribution on

{\mathcal {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}\}_{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

\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 $\mathbb {P} _{\text{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 {\mathcal {G}}_{n}}\mathbb {P} _{\text{SCM}}(G)=1

. This amounts to

optimizing the multi-constraint Lagrange function

below:

{\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 $\alpha$ and $\{\psi _{j}\}_{j=1}^{n}$ 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 $\mathbb {P} _{\text{SCM}}(G)$ for an arbitrary $G\in {\mathcal {G}}_{n}$ yields

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 $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 $G\in {\mathcal {G}}_{n}$ , and thus is the probability distribution. Hence we have an exponential family parameterized by $\{\psi _{j}\}_{j=1}^{n}$ , which are related to the expected degree sequence $\{{\widehat {k}}_{j}\}_{j=1}^{n}$ by the following equivalent expressions:

\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

arXiv:1705.10261
.

^ ^a ^b Garlaschelli, Diego; Frank den Hollander; Andrea Roccaverde (January 30, 2018). "Coviariance structure behind breaking of ensemble equivalence in random graphs" (PDF). Archived (PDF) from the original on February 4, 2023. Retrieved September 14, 2018.

arXiv:cond-mat/0405566
.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Soft_configuration_model&oldid=1195898888"

[van_der_Hoorn-1] arXiv:1705.10261
.

[Diego-2] Garlaschelli, Diego; Frank den Hollander; Andrea Roccaverde (January 30, 2018). "Coviariance structure behind breaking of ensemble equivalence in random graphs" (PDF). Archived (PDF) from the original on February 4, 2023. Retrieved September 14, 2018.

[Park-3] arXiv:cond-mat/0405566
.

[1]

[2]