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

Энтропия Шеннона может быть измерена для распределения вероятностей степеней в сети и служит усреднённой характеристикой гетерогенности структуры:

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

Эта формулировка имеет ограниченное применение в вопросах сложности, содержательной информации, причинности и временных характеристик. Тем не менее, алгоритмическая сложность способна характеризовать любые общие или универсальные свойства графов или сетей: доказано, что графы с низкой энтропией обладают и малой алгоритмической сложностью, поскольку статистические закономерности в таких графах могут быть эффективно использованы при их реконструкции программами. Однако для сетей с высокой энтропией такого прямого соответствия уже нет^[2].

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

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

${\displaystyle p_{ij}={\begin{cases}{\frac {1}{k_{i}}},&{\text{если }}A_{ij}=1\\0,&{\text{если }}A_{ij}=0\\\end{cases}}}$,

где ${\displaystyle (A_{ij})}$ — матрица смежности графа, ${\displaystyle k_{i}}$ — степень вершины ${\displaystyle i}$.

Тогда энтропия Шеннона, вычисляемая для каждой вершины ${\displaystyle {\mathcal {S}}_{i}}$:

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

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

${\displaystyle {\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)}}}$

Нормализованная энтропия сети ${\displaystyle {\mathcal {H}}}$ задаётся как среднее по всем вершинам:^[3]

${\displaystyle {\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}}}$

Максимальное значение ${\displaystyle {\mathcal {H}}=1}$ достигается при полной связности сети, а при разрежении энтропия стремится к нулю. Заметим, что изолированные вершины (${\displaystyle k_{i}=0}$) не учитываются, так как для них ${\displaystyle p_{ij}}$ не определено. Эта формула обладает слабой чувствительностью к хабам из-за логарифмического характера и актуальна в большей степени для взвешенных сетей^[3], что затрудняет различение масштабно-инвариантных сетей по этой метрике^[1].

Ограничения энтропии Шеннона случайного блуждальщика устраняются с помощью энтропии Колмогорова — Синая. В данном контексте сетевая энтропия — это энтропия стохастической матрицы, ассоциированной с матрицей смежности ${\displaystyle (A_{ij})}$; «динамической энтропией» сети называется энтропия случайного блуждальщика. Пусть ${\displaystyle \lambda }$ — доминирующее собственное значение ${\displaystyle (A_{ij})}$; доказано, что ${\displaystyle \ln \lambda }$ удовлетворяет вариационному принципу^[4], эквивалентному «динамической энтропии» для невзвешенных сетей (булева матрица смежности). Соответственно, топологическая энтропия определяется как

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

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

Кроме того, энтропия Колмогорова связана с кривизной Риччи на графе^[6], метрикой, которую применяют для различения стадий развития рака по коэкспрессии генов, а также для выявления признаков финансовых кризисов по корреляционным сетям акций.

Энтропия фон Неймана — расширение классической энтропии Гиббса на квантовый случай. Эта энтропия строится на основе плотностной матрицы ${\displaystyle \rho }$; исторически первым кандидатом на такую матрицу была функция матричного лапласиана L, связанного с сетью. Усреднённая энтропия фон Неймана по ансамблю определяется как:^[7]

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

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

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

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

Эта трактовка легко распространяется на многослойные сети через тензорный подход и применяется для снижения их размерности с точки зрения структуры.

Однако показано, что эта энтропия не всегда удовлетворяет свойству субаддитивности. Более строгую определённость с этим свойством дал подход Манлио Де Доменико и Бьямонте, применяя квантово-подобное обобщение Гиббсовского состояния:

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

где

$${\displaystyle Z(\beta )=Tr[e^{-\beta L}]}$$

${\displaystyle \beta }$

${\displaystyle \beta }$

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

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

По аналогии со статистической механикой вводятся микроканонические и канонические ансамбли сетей. Для ансамбля можно определить функцию распределения Z:

$${\displaystyle 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)}$$

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

Для простых неориентированных сетей функция распределения упрощается:

$${\displaystyle 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)}$$

где ${\displaystyle a_{ij}\in \alpha }$, индекс ${\displaystyle \alpha }$ принимает значения ${\displaystyle \{0,1\}}$ (в простых сетях).

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

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

где ${\displaystyle {\mathcal {N}}}$ — мощность ансамбля, то есть общее число сетей.

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

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

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

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

Ансамбль ${\displaystyle G(N,L)}$ с заданным числом вершин ${\displaystyle N}$ и рёбер ${\displaystyle L}$ (и сопряжённый ему канонический ансамбль ${\displaystyle G(N,p)}$) характеризуются соответственно как микроканонический и канонический, с энтропиями Гиббса ${\displaystyle \Sigma }$ и Шеннона S. Энтропия Гиббса для ${\displaystyle G(N,p)}$ выражается так:^[16]

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

Для ${\displaystyle G(N,p)}$:

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

Подставляя ${\displaystyle p_{ij}}$ в энтропию Шеннона:

$${\displaystyle \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]}$$

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