Сетевая энтропия

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

Составы

Согласно публикации Zenil et al. , 2018 г. существует несколько формулировок для расчета энтропии сети, и, как правило, все они требуют фокусировки на определенном свойстве графа, таком как матрица смежности, последовательность степеней, распределение степеней или количество бифуркаций, что может привести к значениям энтропии, которые не инвариантны выбранному описанию сети.

Распределение степеней Энтропия Шеннона

Энтропию Шеннона можно измерить для распределения вероятностей степени сети как среднее измерение неоднородность сети.

${\mathcal {H}}=-\sum _{k=1}^{N-1}P(k)\ln {P(k)}$

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

Случайный ходок Шеннон Энтропия

Из-за ограничений предыдущей формулировки можно использовать другой подход, сохраняя при этом использование исходного уравнения энтропии Шеннона.

Рассмотрим случайного блуждающего человека, который путешествует по графу, начиная с узла $i$ в любой узел $j$ рядом с $i$ с равной вероятностью. Распределение вероятностей $p_{ij}$ который описывает поведение этого случайного блуждающего, таким образом, будет

$p_{ij}={\begin{cases}{\frac {1}{k_{i}}},&{\text{if }}A_{ij}=1\\0,&{\text{if }}A_{ij}=0\\\end{cases}}$,

где $(A_{ij})$ – матрица смежности графов и $k_{i}$ это узел $i$ степень.

Отсюда энтропия Шеннона из каждого узла ${\mathcal {S}}_{i}$ может быть определен как

${\mathcal {S}}_{i}=-\sum _{j=1}^{N-1}p_{ij}\ln {p_{ij}}=\ln {k_{i}}$

и, поскольку $max(k_{i})=N-1$, нормализованная энтропия узла ${\mathcal {H}}_{i}$ рассчитывается

${\mathcal {H}}_{i}={\frac {{\mathcal {S}}_{i}}{max({\mathcal {S}}_{i})}}={\frac {\ln {k_{i}}}{\ln(max(k_{i}))}}={\frac {\ln {k_{i}}}{\ln(N-1)}}$

Это приводит к нормализованной сетевой энтропии. ${\mathcal {H}}$, рассчитывается путем усреднения нормализованной энтропии узла по всей сети:

${\mathcal {H}}={\frac {1}{N}}\sum _{i=1}^{N}{\mathcal {H}}_{i}={\frac {1}{N\ln(N-1)}}\sum _{i=1}^{N}\ln {k_{i}}$

Нормализованная энтропия сети максимальна ${\mathcal {H}}=1$ когда сеть полностью подключена и уменьшается, сеть становится более разреженной. ${\mathcal {H}}=0$. Обратите внимание, что изолированные узлы $k_{i}=0$ не имеют своей вероятности $p_{ij}$ определены и, следовательно, не учитываются при измерении энтропии сети. Эта формулировка сетевой энтропии имеет низкую чувствительность к концентраторам из-за логарифмического коэффициента и более значима для взвешенных сетей. что в конечном итоге затрудняет дифференциацию безмасштабных сетей, используя только эту меру.

Случайный ходок Энтропия Колмогорова – Синая

Ограничения энтропии Шеннона случайного блуждающего человека можно преодолеть, адаптировав его для использования энтропии Колмогорова-Синая . В этом контексте энтропия сети — это энтропия стохастической матрицы, связанной с матрицей смежности графов. $(A_{ij})$ а энтропия случайного блуждающего Шеннона называется динамической энтропией сети. Исходя из этого, пусть $\lambda$ быть доминирующим собственным значением $(A_{ij})$. Доказано, что $\ln \lambda$ удовлетворяет вариационному принципу это эквивалентно динамической энтропии для невзвешенных сетей, т. е. матрица смежности состоит исключительно из логических значений. Следовательно, топологическая энтропия определяется как

${\mathcal {H}}=\ln \lambda$

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

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

Энтропия фон Неймана

Энтропия фон Неймана — это расширение классической энтропии Гиббса в квантовом контексте. Эта энтропия строится из матрицы плотности $\rho$: исторически первым предложенным кандидатом на такую ​​матрицу плотности было выражение матрицы Лапласа L, связанной с сетью. Средняя энтропия фон Неймана ансамбля рассчитывается как:

$${S}_{VN}=-\langle \mathrm {Tr} \rho \log(\rho )\rangle$$

Для случайного сетевого ансамбля $G(N,p)$, отношение между $S_{VN}$ и $S$ немонотонна, когда средняя связность $p(N-1)$ разнообразен.

Для ансамблей канонических степенных сетей две энтропии связаны линейно.

$${S}_{VN}=\eta {S/N}+\beta$$

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

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

Однако было показано, что это определение энтропии не удовлетворяет свойству субаддитивности (см. Субаддитивность энтропии Фон Неймана ), которое, как ожидается, будет соблюдаться теоретически. Более обоснованное определение, удовлетворяющее этому фундаментальному свойству, было предложено Манлио Де Доменико и Биамонте. как квантовоподобное состояние Гиббса

$$\rho (\beta )={\frac {e^{-\beta L}}{Z(\beta )}}$$

где $$Z(\beta )=Tr[e^{-\beta L}]$$ – нормирующий множитель, играющий роль статистической суммы, а $\beta$ — настраиваемый параметр, позволяющий проводить анализ с несколькими разрешениями. Если $\beta$ интерпретируется как временной параметр, эта матрица плотности формально пропорциональна распространителю диффузионного процесса на вершине сети.

Эта особенность была использована для построения статистической теории поля сложной информационной динамики, где матрицу плотности можно интерпретировать как суперпозицию операторов потоков, действие которых заключается в активации информационных потоков между узлами. Эта структура была успешно применена для анализа сетей белок-белковых взаимодействий интерактомов вируса и человека, включая SARS-CoV-2 , для выяснения системных особенностей заражения последнего на микроскопическом, мезоскопическом и макроскопическом масштабах. а также оценить важность узлов для интеграции информационных потоков внутри сети и роль, которую они играют в надежности сети.

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

Принцип максимальной энтропии

Основная статья: Принцип максимальной энтропии

Принцип максимальной энтропии — это вариационный принцип, утверждающий, что распределение вероятностей, лучше всего представляющее текущее состояние системы, — это то, которое максимизирует энтропию Шеннона. Эту концепцию можно использовать для генерации ансамбля случайных графов с заданными структурными свойствами, полученных на основе подхода максимальной энтропии, который, в свою очередь, описывает наиболее вероятную конфигурацию сети: принцип максимальной энтропии позволяет получить максимально объективную информацию при отсутствии полных знаний (микроскопические конфигурация недоступна, например: мы не знаем матрицу смежности). С другой стороны, этот ансамбль служит нулевой моделью, когда известна фактическая микроскопическая конфигурация сети, что позволяет оценить значимость эмпирических закономерностей, обнаруженных в сети.

Сетевые ансамбли

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

Энтропия — это логарифм количества графов. Энтропию также можно определить в одной сети. Энтропия бассейна — это логарифм аттракторов в одной булевой сети .

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

Энтропия Гиббса и Шеннона

По аналогии со статистической механикой микроканонические ансамбли и канонические ансамбли для реализации вводятся сетей. Статистическая сумма Z ансамбля может быть определена как: $$Z=\sum _{\mathbf {a} }\delta \left[{\vec {F}}(\mathbf {a} )-{\vec {C}}\right]\exp \left(\sum _{ij}h_{ij}\Theta (a_{ij})+r_{ij}a_{ij}\right)$$

где ${\vec {F}}(\mathbf {a} )={\vec {C}}$ является ограничением, и $a_{ij}$ ( $a_{ij}\geq {0}$) — элементы матрицы смежности , $a_{ij}>0$ тогда и только тогда, когда существует связь между узлом i и узлом j. $\Theta (a_{ij})$ представляет собой ступенчатую функцию с $\Theta (a_{ij})=1$ если $x>0$, и $\Theta (a_{ij})=0$ если $x=0$. Вспомогательные поля $h_{ij}$ и $r_{ij}$ были введены как аналогия ванне в классической механике.

Для простых ненаправленных сетей функцию разделения можно упростить как

$$Z=\sum _{\{a_{ij}\}}\prod _{k}\delta ({\textrm {constraint}}_{k}(\{a_{ij}\}))\exp \left(\sum _{i<j}\sum _{\alpha }h_{ij}(\alpha )\delta _{a_{ij},\alpha }\right)$$

где $a_{ij}\in \alpha$, $\alpha$ — индекс веса, а для простой сети $\alpha =\{0,1\}$.

Микроканонические ансамбли и канонические ансамбли демонстрируются на простых неориентированных сетях.

Для микроканонического ансамбля Гиббса энтропия $\Sigma$ определяется:

$${\begin{aligned}\Sigma &={\frac {1}{N}}\log {\mathcal {N}}\\&={\frac {1}{N}}\log Z|_{h_{ij}(\alpha )=0\forall (i,j,\alpha )}\end{aligned}}$$

где ${\mathcal {N}}$ указывает мощность ансамбля, т. е. общее количество сетей в ансамбле.

Вероятность наличия связи между узлами i и j с весом $\alpha$ дается:

$$\pi _{ij}(\alpha )={\frac {\partial \log Z}{\partial {h_{ij}}(\alpha )}}$$

Для канонического ансамбля энтропия представляется в виде энтропии Шеннона :

$${S}=-\sum _{i<j}\sum _{\alpha }\pi _{ij}(\alpha )\log \pi _{ij}(\alpha )$$

Связь между энтропией Гиббса и Шеннона

Сетевой ансамбль $G(N,L)$ с заданным количеством узлов $N$ и ссылки $L$, и его сопряженно-канонический ансамбль $G(N,p)$ характеризуются как микроканонические и канонические ансамбли и обладают энтропией Гиббса. $\Sigma$ и энтропия Шеннона S соответственно. Энтропия Гиббса в $G(N,p)$ ансамбль представлен:

$${N}\Sigma =\log \left({\begin{matrix}{\cfrac {N(N-1)}{2}}\\L\end{matrix}}\right)$$

Для $G(N,p)$ ансамбль,

$${p}_{ij}=p={\cfrac {2L}{N(N-1)}}$$

Вставка $p_{ij}$ в энтропию Шеннона:

$$\Sigma =S/N+{\cfrac {1}{2N}}\left[\log \left({\cfrac {N(N-1)}{2L}}\right)-\log \left({\cfrac {N(N-1)}{2}}-L\right)\right]$$

Соотношение указывает на то, что энтропия Гиббса $\Sigma$ и энтропия Шеннона на узел S/N случайных графов равны в термодинамическом пределе $N\to \infty$.

См. также

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