Модель случайного графа с максимальной энтропией - Maximum-entropy random graph model

Сетевая наука
Теория
График Комплексная сеть Заражение Маленький мир Без накипи Структура сообщества Перколяция Эволюция Управляемость Рисование графика Социальный капитал Анализ ссылок Оптимизация Взаимность Закрытие Гомофилия Транзитивность Предпочтительная привязанность Теория баланса Сетевой эффект Влияние общества
Типы сетей
Информационная (вычислительная) Телекоммуникации Транспорт Социальное Научное сотрудничество Биологические Искусственный нейрон Взаимозависимый Семантический Пространственный Зависимость поток на чипе
Графики
особенности Клика Составная часть Резать Цикл Структура данных Край Петля окрестности Дорожка Вершина Список смежности  / матрица Список заболеваемости  / матрица Типы Двудольный Завершить Режиссер Гипер Мульти Случайный Взвешенный
Метрики Алгоритмы
Центральность Степень Близость Близость PageRank Мотив Кластеризация Распределение степеней Ассортативность Расстояние Модульность Эффективность
Модели
Топология Случайный график Эрдеш – Реньи Барабаши – Альберт Фитнес модель Уоттс-Строгац Экспоненциальный случайный (ERGM) Случайный геометрический (RGG) Гиперболический (HGN) Иерархический Стохастический блок Максимальная энтропия Мягкая конфигурация Тест LFR Динамика Логическая сеть агент на основе Эпидемия /СЭР
Списки Категории
Темы Программного обеспечения Сетевые ученые Категория: Теория сетей Категория: Теория графов

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

Обзор

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

Несколько обычно изучаемых моделей случайных сетей на самом деле являются максимальной энтропией, например ER графики ${ Displaystyle G (п, м)}$ и ${ Displaystyle G (п, р)}$ (каждый из которых имеет одно глобальное ограничение на количество ребер), а также модель конфигурации (СМ).^[3] и модель мягкой конфигурации (SCM) (каждый из которых ${ displaystyle n}$ локальные ограничения, по одному для каждого узлового значения степени). В двух парах моделей, упомянутых выше, важное различие^[4][5] заключается в том, является ли ограничение четким (т.е. удовлетворяется ли каждый элемент набора размера -${ displaystyle n}$ графики с ненулевой вероятностью в ансамбле) или мягкие (т.е. удовлетворяются в среднем по всему ансамблю). Первый (острый) случай соответствует микроканонический ансамбль,^[6] условие максимальной энтропии, дающее все графики ${ displaystyle G}$ удовлетворение ${ Displaystyle Q_ {j} (G) = q_ {j} forall j}$ как равновероятно; последний (мягкий) случай канонический,^[7] создание экспоненциальная модель случайного графа (ERGM).

Модель	Тип ограничения	Ограничительная переменная	Распределение вероятностей
ER, ${ Displaystyle G (п, м)}$	Резкий, глобальный	Общее количество ребер ${ displaystyle | E (G) |}$	${ Displaystyle 1 / { binom { binom {n} {2}} {m}}; m = | E (G) |}$
ER, ${ Displaystyle G (п, р)}$	Мягкий, глобальный	Ожидаемое общее количество ребер ${ displaystyle | E (G) |}$	${ Displaystyle p ^ {| E (G) |} (1-p) ^ {{ binom {n} {2}} - | E (G) |}}$
Модель конфигурации	Острый, местный	Степень каждой вершины, ${ 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 {{ 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 mathbb {P} (G)}$ на съемочной площадке ${ displaystyle { mathcal {G}} _ {n}}$ из простые графики с участием ${ displaystyle n}$ вершины. В Энтропия Гиббса ${ Displaystyle S [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 {Q_ {j} (G) } _ {j = 1} ^ {J}}$ (например, средний степень, средний кластеризация, или средняя длина кратчайшего пути ) для настройки, поэтому мы накладываем ${ displaystyle 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 mathbb {P} (G)}$ что максимизирует ${ Displaystyle S [G]}$ удовлетворяя ${ Displaystyle langle Q_ {j} rangle = q_ {j}}$, а условие нормировки ${ displaystyle sum _ {G in { mathcal {G}} _ {n}} mathbb {P} (G) = 1}$ приводит к следующему:^[1]

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

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

Модель Эрдеша – Реньи ${ Displaystyle G (п, м)}$

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

Резкое ограничение в ${ Displaystyle G (п, м)}$ это фиксированное количество края ${ displaystyle m}$,^[8] это ${ Displaystyle | OperatorName {E} (G) | = m}$, для всех графиков ${ displaystyle G}$ взяты из ансамбля (созданы с вероятностью, обозначенной ${ Displaystyle mathbb {P} _ {n, m} (G)}$). Это ограничивает пространство для сэмплов от ${ displaystyle { 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}}$, у нас нет внешних ограничений (кроме нормализации), которые необходимо удовлетворить, поэтому мы выберем ${ Displaystyle mathbb {P} _ {n, m} (G)}$ максимизировать ${ Displaystyle S [G]}$ без использования множителей Лагранжа. Хорошо известно, что максимизирующим энтропию распределением при отсутствии внешних ограничений является равномерное распределение над пространством выборки (см. распределение вероятностей максимальной энтропии ), откуда получаем:

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

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

Обобщения

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

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

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

использованная литература