Модель случайного графа с максимальной энтропией

Модели случайных графов с максимальной энтропией — это модели случайных графов , используемые для изучения сложных сетей, подчиняющихся принципу максимальной энтропии при наборе структурных ограничений. который может быть глобальным, распределительным или локальным.

Обзор

Любая модель случайного графа (при фиксированном наборе значений параметров) приводит к распределению вероятностей на графах , а модели с максимальной энтропией в рассматриваемом классе распределений обладают особым свойством быть максимально несмещенными нулевыми моделями для сетевого вывода. (например, вывод биологической сети ). Каждая модель определяет семейство вероятностных распределений на множестве графиков размера $n$ (за каждого $n>n_{0}$ для некоторого конечного $n_{0}$), параметризованный набором ограничений на $J$ наблюдаемые $\{Q_{j}(G)\}_{j=1}^{J}$ определено для каждого графа $G$ (например, фиксированная ожидаемая средняя степень , распределение степеней определенной формы или определенная последовательность степеней ), применяемая в распределении графа наряду с максимизацией энтропии с помощью метода множителей Лагранжа . Обратите внимание, что в этом контексте «максимальная энтропия» относится не к энтропии отдельного графа , а скорее к энтропии всего вероятностного ансамбля случайных графов.

Некоторые широко изучаемые модели случайных сетей на самом деле представляют собой максимальную энтропию, например ER . графы $G(n,m)$ и $G(n,p)$ (каждый из которых имеет одно глобальное ограничение на количество ребер), а также модель конфигурации (CM). и модель мягкой конфигурации (SCM) (каждая из которых имеет $n$ локальные ограничения, по одному для каждого значения степени узла). В двух парах моделей, упомянутых выше, важное различие заключается в том, является ли ограничение резким (т.е. удовлетворяется ли каждый элемент набора размера- $n$ графы с ненулевой вероятностью в ансамбле), или мягкие (т.е. удовлетворяющиеся в среднем по всему ансамблю). Первый (точный) случай соответствует микроканоническому ансамблю условие максимальной энтропии, дающее все графы $G$ удовлетворяющий $Q_{j}(G)=q_{j}\forall j$ как равновероятный; последний (мягкий) случай является каноническим , создание экспоненциальной модели случайного графа (ERGM).

Модель	Тип ограничения	Ограничивающая переменная	Распределение вероятностей
ЯВЛЯЕТСЯ , $G(n,m)$	Острый, глобальный	Общее количество ребер $|E(G)|$	$1/{\binom {\binom {n}{2}}{m}};\ m=|E(G)|$
ЯВЛЯЕТСЯ , $G(n,p)$	Мягкий, глобальный	Ожидаемое общее количество ребер $|E(G)|$	$p^{|E(G)|}(1-p)^{{\binom {n}{2}}-|E(G)|}$
Модель конфигурации	Острый, местный	Степень каждой вершины, $\{{\hat {k}}_{j}\}_{j=1}^{n}$	$1/\left\vert \Omega (\{{\hat {k}}_{j}\}_{j=1}^{n})\right\vert ;\Omega (\{k_{j}\}_{j=1}^{n})=\{g\in {\mathcal {G}}_{n}:k_{j}(g)={\hat {k}}_{j}\forall j\}\subset {\mathcal {G}}_{n}$
Модель мягкой конфигурации	Мягкий, местный	Ожидаемая степень каждой вершины, $\{{\hat {k}}_{j}\}_{j=1}^{n}$	$Z^{-1}\exp \left[-\sum _{j=1}^{n}\psi _{j}k_{j}(G)\right];\ -{\frac {\partial \ln Z}{\partial \psi _{j}}}={\hat {k}}_{j}$

Канонический ансамбль графов (общая структура)

Предположим, мы строим модель случайного графа, состоящую из распределения вероятностей $\mathbb {P} (G)$ на съемочной площадке ${\mathcal {G}}_{n}$ графиков простых с $n$ вершины. Гиббса Энтропия $S[G]$ этого ансамбля будет предоставлен

$S[G]=-\sum _{G\in {\mathcal {G}}_{n}}\mathbb {P} (G)\log \mathbb {P} (G).$

Нам нужны усредненные по ансамблю значения $\{\langle Q_{j}\rangle \}_{j=1}^{J}$ наблюдаемых $\{Q_{j}(G)\}_{j=1}^{J}$ (например, средняя степень , средняя кластеризация или средняя длина кратчайшего пути ) настраиваемыми, поэтому мы налагаем $J$ «мягкие» ограничения на распределение графов:

$\langle Q_{j}\rangle =\sum _{G\in {\mathcal {G}}_{n}}\mathbb {P} (G)Q_{j}(G)=q_{j},$

где $j=1,...,J$ обозначьте ограничения. Применение метода множителей Лагранжа для определения распределения $\mathbb {P} (G)$ это максимизирует $S[G]$ удовлетворяя $\langle Q_{j}\rangle =q_{j}$, и условие нормировки $\sum _{G\in {\mathcal {G}}_{n}}\mathbb {P} (G)=1$ приводит к следующему:

$\mathbb {P} (G)={\frac {1}{Z}}\exp \left[-\sum _{j=1}^{J}\psi _{j}Q_{j}(G)\right],$

где $Z$ — нормировочная константа ( статистическая сумма ) и $\{\psi _{j}\}_{j=1}^{J}$ являются параметрами (множителями Лагранжа), связанными с соответственно индексированными наблюдаемыми графа, которые можно настроить для получения образцов графа с желаемыми значениями этих свойств в среднем; в результате получается экспоненциальное семейство и канонический ансамбль ; в частности, давая ERGM .

Модель Эрдеша – Реньи $G(n,m)$

В приведенной выше канонической структуре ограничения налагались на усредненные по ансамблю величины $\langle Q_{j}\rangle$. Хотя эти свойства в среднем принимают значения, определяемые соответствующей настройкой $\{\psi _{j}\}_{j=1}^{J}$, каждый конкретный экземпляр $G$ может иметь $Q_{j}(G)\neq q_{j}$, что может быть нежелательно. Вместо этого мы можем наложить гораздо более строгое условие: каждый граф с ненулевой вероятностью должен удовлетворять $Q_{j}(G)=q_{j}$ точно. При этих «жестких» ограничениях определяется распределение максимальной энтропии. Мы проиллюстрируем это на модели Эрдеша – Реньи. $G(n,m)$.

Резкое ограничение в $G(n,m)$ это фиксированное количество ребер $m$, то есть $|\operatorname {E} (G)|=m$, для всех графиков $G$ взятый из ансамбля (созданный с вероятностью, обозначенной $\mathbb {P} _{n,m}(G)$). Это ограничивает пространство выборки от ${\mathcal {G}}_{n}$ (все графики на $n$ вершины) в подмножество ${\mathcal {G}}_{n,m}=\{g\in {\mathcal {G}}_{n};|\operatorname {E} (g)|=m\}\subset {\mathcal {G}}_{n}$. Это прямая аналогия с микроканоническим ансамблем в классической статистической механике , где система ограничена тонким многообразием в фазовом пространстве всех состояний с определенным значением энергии .

Ограничив наше пространство выборки до ${\mathcal {G}}_{n,m}$, у нас нет внешних ограничений (кроме нормализации), которые необходимо удовлетворить, и поэтому мы выберем $\mathbb {P} _{n,m}(G)$ максимизировать $S[G]$ без использования множителей Лагранжа. Хорошо известно, что максимизирующее энтропию распределение при отсутствии внешних ограничений представляет собой равномерное распределение по выборочному пространству (см. Распределение вероятностей максимальной энтропии ), из которого получаем:

$\mathbb {P} _{n,m}(G)={\frac {1}{|{\mathcal {G}}_{n,m}|}}={\binom {\binom {n}{2}}{m}}^{-1},$

где последнее выражение через биномиальные коэффициенты — это количество способов разместить $m$ края среди ${\binom {n}{2}}$ возможные ребра и, следовательно мощность , ${\mathcal {G}}_{n,m}$.

Обобщения

На основе обобщений простых графов изучались различные ансамбли с максимальной энтропией. К ним относятся, например, ансамбли симплициальных комплексов, и взвешенные случайные графы с заданной ожидаемой последовательностью степеней

См. также

• Принцип максимальной энтропии
• Распределение вероятностей максимальной энтропии
• Метод множителей Лагранжа
• Нулевая модель
• Случайный график
• Модель экспоненциального случайного графа
• Канонический ансамбль
• Микроканонический ансамбль