Модель мягкой конфигурации

В прикладной математике модель мягкой конфигурации (SCM) представляет собой модель случайных графов, подчиняющуюся принципу максимальной энтропии при ограничениях на математическое ожидание последовательности степеней выборочных графов . В то время как модель конфигурации (CM) равномерно выбирает случайные графы определенной последовательности степеней, SCM сохраняет только указанную последовательность степеней в среднем по всем реализациям сети; в этом смысле SCM имеет очень мягкие ограничения по сравнению с ограничениями CM («мягкие», а не «жесткие» ограничения). ). SCM для графиков размера $n$ имеет ненулевую вероятность выборки любого графа размера $n$, тогда как CM ограничен только графами, имеющими точно заданную структуру связности.

Формулировка модели

SCM представляет собой статистический ансамбль случайных графов. $G$ имея $n$ вершины ( $n=|V(G)|$) помечены $\{v_{j}\}_{j=1}^{n}=V(G)$, создавая распределение вероятностей на ${\mathcal {G}}_{n}$ (набор графиков размером $n$). На ансамбль наложены $n$ ограничения, а именно, что среднее ансамблю степени по $k_{j}$ вершины $v_{j}$ равно заданному значению ${\widehat {k}}_{j}$, для всех $v_{j}\in V(G)$. Модель полностью параметризована по размеру. $n$ и ожидаемая последовательность степеней $\{{\widehat {k}}_{j}\}_{j=1}^{n}$. Эти ограничения являются как локальными (одно ограничение, связанное с каждой вершиной), так и мягкими (ограничения на среднее по ансамблю определенных наблюдаемых величин) и, таким образом, образуют канонический ансамбль с большим количеством ограничений. Условия $\langle k_{j}\rangle ={\widehat {k}}_{j}$ накладываются на ансамбль методом множителей Лагранжа (см. Модель случайного графа с максимальной энтропией ).

распределения

Вероятность $\mathbb {P} _{\text{SCM}}(G)$ SCM, создающего график $G$ определяется путем максимизации энтропии Гиббса $S[G]$ с учетом ограничений $\langle k_{j}\rangle ={\widehat {k}}_{j},\ j=1,\ldots ,n$ и нормализация $\sum _{G\in {\mathcal {G}}_{n}}\mathbb {P} _{\text{SCM}}(G)=1$. Это равносильно оптимизации с несколькими ограничениями, функции Лагранжа приведенной ниже:

${\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}}$

где $\alpha$ и $\{\psi _{j}\}_{j=1}^{n}$ являются $n+1$ множители, устанавливаемые $n+1$ ограничения (нормализация и ожидаемая последовательность степеней). Приравнивая к нулю производную вышеизложенного по $\mathbb {P} _{\text{SCM}}(G)$ для произвольного $G\in {\mathcal {G}}_{n}$ урожайность

$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],$

константа $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)$ являющаяся статистической суммой, нормирующей распределение; приведенное выше экспоненциальное выражение применимо ко всем $G\in {\mathcal {G}}_{n}$, и, таким образом, является распределением вероятностей. Следовательно, мы имеем экспоненциальное семейство , параметризованное $\{\psi _{j}\}_{j=1}^{n}$, которые связаны с ожидаемой последовательностью степеней $\{{\widehat {k}}_{j}\}_{j=1}^{n}$ следующими эквивалентными выражениями:

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