Random graph model in applied mathematics
Part of a series on |
Network science |
---|
|
|
---|
- Graph
- Complex network
- Contagion
- Small-world
- Scale-free
- Community structure
- Percolation
- Evolution
- Controllability
- Graph drawing
- Social capital
- Link analysis
- Optimization
- Reciprocity
- Closure
- Homophily
- Transitivity
- Preferential attachment
- Balance theory
- Network effect
- Social influence
|
Network types |
---|
|
Graphs |
---|
|
|
---|
|
Models |
---|
|
|
---|
- Category:Network theory
- Category:Graph theory
|
|
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
has a nonzero probability of sampling any graph of size
, 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
having
vertices (
) labeled
, producing a probability distribution on
(the set of graphs of size
). Imposed on the ensemble are
constraints, namely that the ensemble average of the degree
of vertex
is equal to a designated value
, for all
. The model is fully parameterized by its size
and expected degree sequence
. 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
are imposed on the ensemble by the method of Lagrange multipliers (see Maximum-entropy random graph model).
Derivation of the probability distribution
The probability
of the SCM producing a graph
is determined by maximizing the Gibbs entropy
subject to constraints
and normalization
. 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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/426a3cc31489b0b0465255e44a37e34e91a0330f)
where
and
are the
multipliers to be fixed by the
constraints (normalization and the expected degree sequence). Setting to zero the derivative of the above with respect to
for an arbitrary
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],}](https://wikimedia.org/api/rest_v1/media/math/render/svg/54cf3d859575acc9547b31a499f5c0e6a8fd5bb7)
the constant
[3] being the partition function normalizing the distribution; the above exponential expression applies to all
, and thus is the probability distribution. Hence we have an exponential family parameterized by
, which are related to the expected degree sequence
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.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d946c17bb4c5d29f1e5d613b787aeab589f07c56)
References
- ^ 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 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.
- ^ Park, Juyong; M.E.J. Newman (2004-05-25). "The statistical mechanics of networks". arXiv:cond-mat/0405566.