Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Soft configuration model
open-in-new
<h2 id="model-formulation">Model formulation</h2> <p>The SCM is a <a href="/facts/Statistical_ensemble/Nsxv4FAI">statistical ensemble</a> of random graphs G {\displaystyle G} having n {\displaystyle n} vertices ( n = | V ( G ) | {\displaystyle n=|V(G)|} ) labeled { v j } j = 1 n = V ( G ) {\displaystyle \{v_{j}\}_{j=1}^{n}=V(G)} , producing a <a href="/facts/Probability_distribution/EpsKKVRu">probability distribution</a> on G n {\displaystyle {\mathcal {G}}_{n}} (the set of graphs of size n {\displaystyle n} ). Imposed on the ensemble are n {\displaystyle n} constraints, namely that the <a href="/facts/Ensemble_average/oCtaySGB">ensemble average</a> of the <a href="/facts/Degree_(graph_theory)/LnFFpI8v">degree</a> k j {\displaystyle k_{j}} of vertex v j {\displaystyle v_{j}} is equal to a designated value k ^ j {\displaystyle {\widehat {k}}_{j}} , for all v j ∈ V ( G ) {\displaystyle v_{j}\in V(G)} . The model is fully <a href="/facts/Parameterization/SQK3P4sc">parameterized</a> by its size n {\displaystyle n} and expected degree sequence { 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 <a href="/facts/Canonical_ensemble/GIhyzkb8">canonical ensemble</a> with an <a href="/facts/Intensive_and_extensive_properties/UcgSh8EG">extensive</a> number of constraints.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> The conditions ⟨ k j ⟩ = k ^ j {\displaystyle \langle k_{j}\rangle ={\widehat {k}}_{j}} are imposed on the ensemble by the <a href="/facts/Method_of_Lagrange_multipliers/U5mSI5YP">method of Lagrange multipliers</a> (see <a href="/facts/Maximum-entropy_random_graph_model/4fV7BVYH">Maximum-entropy random graph model</a>). </p> <h2 id="derivation-of-the-probability-distribution">Derivation of the probability distribution</h2> <p>The probability P SCM ( G ) {\displaystyle \mathbb {P} _{\text{SCM}}(G)} of the SCM producing a graph G {\displaystyle G} is determined by maximizing the <a href="/facts/Gibbs_entropy/gMFXXIck">Gibbs entropy</a> S [ G ] {\displaystyle S[G]} subject to constraints ⟨ k j ⟩ = k ^ j , j = 1 , … , n {\displaystyle \langle k_{j}\rangle ={\widehat {k}}_{j},\ j=1,\ldots ,n} and normalization ∑ G ∈ G n P SCM ( G ) = 1 {\displaystyle \sum _{G\in {\mathcal {G}}_{n}}\mathbb {P} _{\text{SCM}}(G)=1} . This amounts to <a href="/facts/Optimizing/oRn8Iv5I">optimizing</a> the multi-constraint <a href="/facts/Lagrange_multiplier/U5mSI5YP">Lagrange function</a> below: </p> L ( α , { ψ j } j = 1 n ) = − ∑ G ∈ G n P SCM ( G ) log P SCM ( G ) + α ( 1 − ∑ G ∈ G n P SCM ( G ) ) + ∑ j = 1 n ψ j ( k ^ j − ∑ G ∈ G n P SCM ( G ) k j ( G ) ) , {\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}}} <p>where α {\displaystyle \alpha } and { ψ j } j = 1 n {\displaystyle \{\psi _{j}\}_{j=1}^{n}} are the n + 1 {\displaystyle n+1} multipliers to be fixed by the n + 1 {\displaystyle n+1} constraints (normalization and the expected degree sequence). Setting to zero the derivative of the above with respect to P SCM ( G ) {\displaystyle \mathbb {P} _{\text{SCM}}(G)} for an arbitrary G ∈ G n {\displaystyle G\in {\mathcal {G}}_{n}} yields </p> 0 = ∂ L ( α , { ψ j } j = 1 n ) ∂ P SCM ( G ) = − log P SCM ( G ) − 1 − α − ∑ j = 1 n ψ j k j ( G ) ⇒ P SCM ( G ) = 1 Z exp [ − ∑ j = 1 n ψ j k j ( G ) ] , {\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],} <p>the constant Z := e α + 1 = ∑ G ∈ G n exp [ − ∑ j = 1 n ψ j k j ( G ) ] = ∏ 1 ≤ i < j ≤ n ( 1 + e − ( ψ i + ψ j ) ) {\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)} <a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> being the <a href="/facts/Partition_function_(mathematics)/dp53Le9y">partition function</a> normalizing the distribution; the above exponential expression applies to all G ∈ G n {\displaystyle G\in {\mathcal {G}}_{n}} , and thus is the probability distribution. Hence we have an <a href="/facts/Exponential_family/1LkkqEIf">exponential family</a> parameterized by { ψ j } j = 1 n {\displaystyle \{\psi _{j}\}_{j=1}^{n}} , which are related to the expected degree sequence { k ^ j } j = 1 n {\displaystyle \{{\widehat {k}}_{j}\}_{j=1}^{n}} by the following equivalent expressions: </p> ⟨ k q ⟩ = ∑ G ∈ G n k q ( G ) P SCM ( G ) = − ∂ log Z ∂ ψ q = ∑ j ≠ q 1 e ψ q + ψ j + 1 = k ^ q , q = 1 , … , 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.} <h2 id="references">References</h2> <ol> <li id="fn:1"><p>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. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>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. <a href="http://eprints.imtlucca.it/4040/1/1711.04273.pdf" target="_blank">http://eprints.imtlucca.it/4040/1/1711.04273.pdf</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>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. <a href="http://eprints.imtlucca.it/4040/1/1711.04273.pdf" target="_blank">http://eprints.imtlucca.it/4040/1/1711.04273.pdf</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Park, Juyong; M.E.J. Newman (2004-05-25). "The statistical mechanics of networks". arXiv:cond-mat/0405566. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> </ol>