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

редактировать

Теория

Типы сетей

Особенности
Клика Составная часть Порез Цикл Структура данных Край Петля окрестности Путь Вершина Список / матрица смежности Список / матрица заболеваемости
Типы
Двудольный Завершить Режиссер Гипер Мульти Случайный Взвешенный

Модели

Топология
Случайный график Эрдеш – Реньи Барабаши – Альберт Фитнес модель Уоттс-Строгац Экспоненциальный случайный (ERGM) Случайный геометрический (RGG) Гиперболический (HGN) Иерархический Стохастический блок Максимальная энтропия Мягкая конфигурация Тест LFR
Динамика
Логическая сеть агент на основе Эпидемия / SIR

Списки
Категории

Категория: Теория сетей
Категория: Теория графов

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

Содержание

1 Обзор
2 Канонический ансамбль графов (общие рамки)
3 Модель Эрдеша – Реньи ${\ Displaystyle G (п, м)}$ $G (п, м)$
4 Обобщения
5 См. Также
6 Ссылки

Обзор

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

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

Модель	Тип ограничения	Ограничительная переменная	Распределение вероятностей
ER, ${\ Displaystyle G (п, м)}$ $G (п, м)$	Резкий, глобальный	Общее количество ребер ${\ displaystyle \| E (G) \|}$ $\| E (G) \|$	${\ Displaystyle 1 / {\ binom {\ binom {n} {2}} {m}}; \ m = \| E (G) \|}$ ${\ Displaystyle 1 / {\ binom {\ binom {n} {2}} {m}}; \ m = \| E (G) \|}$
ER, ${\ Displaystyle G (п, р)}$ $G (п, р)$	Мягкий, глобальный	Ожидаемое общее количество ребер ${\ displaystyle \| E (G) \|}$ $\| E (G) \|$	${\ Displaystyle p ^ {\| E (G) \|} (1-p) ^ {{\ binom {n} {2}} - \| E (G) \|}}$ ${\ Displaystyle p ^ {\| E (G) \|} (1-p) ^ {{\ binom {n} {2}} - \| E (G) \|}}$
Модель конфигурации	Острый, местный	Степень каждой вершины, ${\ displaystyle \ {{\ hat {k}} _ {j} \} _ {j = 1} ^ {n}}$ ${\ displaystyle \ {{\ hat {k}} _ {j} \} _ {j = 1} ^ {n}}$	${\ displaystyle 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}}$ ${\ displaystyle 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}}$
Модель мягкой конфигурации	Мягкий, местный	Ожидаемая степень каждой вершины, ${\ displaystyle \ {{\ hat {k}} _ {j} \} _ {j = 1} ^ {n}}$ ${\ displaystyle \ {{\ hat {k}} _ {j} \} _ {j = 1} ^ {n}}$	${\ Displaystyle Z ^ {- 1} \ exp \ left [- \ sum _ {j = 1} ^ {n} \ psi _ {j} k_ {j} (G) \ right]; \ - {\ frac { \ partial \ ln Z} {\ partial \ psi _ {j}}} = {\ hat {k}} _ {j}}$ ${\ Displaystyle Z ^ {- 1} \ exp \ left [- \ sum _ {j = 1} ^ {n} \ psi _ {j} k_ {j} (G) \ right]; \ - {\ frac { \ partial \ ln Z} {\ partial \ psi _ {j}}} = {\ hat {k}} _ {j}}$

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

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

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

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

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

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

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

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

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

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

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

Модель Эрдеша – Реньи

{\ Displaystyle G (п, м)}

G (п, м)

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

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

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

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

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

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

Обобщения

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

Смотрите также

Рекомендации