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

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

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

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

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

Вывод вероятностного распределения

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

${ displaystyle { begin {align} & { 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 {align}}}$

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

${ displaystyle 0 = { frac { partial { mathcal {L}} left ( alpha, { psi _ {j} } _ {j = 1} ^ {n} right)} { частичный 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],}$

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

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

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