View source for Soft configuration model

{{Short description|Random graph model in applied mathematics}}
{{Network science}}

In applied mathematics, the '''soft configuration model (SCM)''' is a [[Random graph|random graph]] model subject to the [[Principle of maximum entropy|principle of maximum entropy]] under constraints on the expectation of the [[Degree sequence|degree sequence]] of sampled [[Graph (discrete mathematics)|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|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 [[Physics:Statistical ensemble|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|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 [[Physics:Ensemble average|ensemble average]] of the [[Degree (graph theory)|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 [[Physics:Canonical ensemble|canonical ensemble]] with an [[Physics:Intensive and extensive properties|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 multiplier#Multiple constraints|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 (mathematics)|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|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| ]]

{{Sourceattribution|Soft configuration model}}