entropía de red

La entropía de Shannon se puede medir para la distribución de probabilidad del grado de la red como una medida promedio de la heterogeneidad de la red.

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

Esta formulación tiene un uso limitado en lo que respecta a la complejidad, el contenido informativo, la causalidad y la información temporal. Sea como fuere, la complejidad algorítmica tiene la capacidad de caracterizar cualquier propiedad general o universal de un grafo o red, y está demostrado que los grafos con baja entropía tienen baja complejidad algorítmica porque las regularidades estadísticas que se encuentran en un grafo son útiles para que los programas informáticos lo recreen. Sin embargo, no se puede decir lo mismo de las redes de alta entropía, ya que estas podrían no tener ningún valor para la complejidad algorítmica. ^{[ 3 ]}

Debido a las limitaciones de la formulación anterior, es posible adoptar un enfoque diferente manteniendo el uso de la ecuación original de la entropía de Shannon.

Consideremos un caminante aleatorio que viaja por el grafo, yendo desde un nodo${\displaystyle i}$a cualquier nodo${\displaystyle j}$adyacente a${\displaystyle i}$con igual probabilidad. La distribución de probabilidad${\displaystyle p_{ij}}$que describe el comportamiento de este caminante aleatorio sería, por lo tanto,

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

dónde${\displaystyle (A_{ij})}$es la matriz de adyacencia del grafo y${\displaystyle k_{i}}$es el nodo${\displaystyle i}$grado.

A partir de eso, la entropía de Shannon de cada nodo${\displaystyle {\mathcal {S}}_{i}}$puede definirse como

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

y, dado que${\displaystyle max(k_{i})=N-1}$, la entropía normalizada del nodo${\displaystyle {\mathcal {H}}_{i}}$se calcula

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

Esto conduce a una entropía de red normalizada.${\displaystyle {\mathcal {H}}}$, calculado promediando la entropía normalizada del nodo en toda la red: ^{[ 4 ]}

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

La entropía de red normalizada es máxima.${\displaystyle {\mathcal {H}}=1}$cuando la red está completamente conectada y disminuye a medida que la red se vuelve más dispersa${\displaystyle {\mathcal {H}}=0}$. Observe que los nodos aislados${\displaystyle k_{i}=0}$no tienen su probabilidad${\displaystyle p_{ij}}$definidos y, por lo tanto, no se consideran al medir la entropía de la red. Esta formulación de la entropía de la red tiene baja sensibilidad a los hubs debido al factor logarítmico y es más significativa para redes ponderadas, ^{[ 4 ]} lo que en última instancia dificulta diferenciar redes libres de escala utilizando solo esta medida. ^{[ 2 ]}

Las limitaciones de la entropía de Shannon del caminante aleatorio pueden superarse adaptándola para usar una entropía de Kolmogorov-Sinai . En este contexto, la entropía de red es la entropía de una matriz estocástica asociada con la matriz de adyacencia del grafo.${\displaystyle (A_{ij})}$y la entropía de Shannon del caminante aleatorio se llama entropía dinámica de la red. A partir de eso, dejemos${\displaystyle \lambda }$sea ​​el valor propio dominante de${\displaystyle (A_{ij})}$Está demostrado que${\displaystyle \ln \lambda }$satisface un principio variacional ^{[ 5 ]} que es equivalente a la entropía dinámica para redes no ponderadas, es decir, la matriz de adyacencia consta exclusivamente de valores booleanos. Por lo tanto, la entropía topológica se define como

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

Esta formulación es importante para el estudio de la robustez de la red , es decir, la capacidad de la red para resistir cambios estructurales aleatorios. La robustez es difícil de medir numéricamente, mientras que la entropía se puede calcular fácilmente para cualquier red, lo cual es especialmente importante en el contexto de redes no estacionarias. El teorema de fluctuación entrópica muestra que esta entropía está correlacionada positivamente con la robustez y, por lo tanto, con una mayor insensibilidad de una observable a las perturbaciones dinámicas o estructurales de la red. Además, los valores propios están intrínsecamente relacionados con la multiplicidad de caminos internos, lo que lleva a una correlación negativa entre la entropía topológica y la longitud del camino promedio más corto . ^{[ 6 ]}

Aparte de eso, la entropía de Kolmogorov está relacionada con la curvatura de Ricci de la red, ^{[ 7 ]} una métrica que se ha utilizado para diferenciar etapas del cáncer a partir de redes de coexpresión genética, ^{[ 8 ]} así como para dar características distintivas de colapsos financieros a partir de redes de correlación de acciones ^{[ 9 ]}

La entropía de Von Neumann es la extensión de la entropía clásica de Gibbs en un contexto cuántico. Esta entropía se construye a partir de una matriz de densidad.${\displaystyle \rho }$Históricamente, el primer candidato propuesto para dicha matriz de densidad ha sido una expresión de la matriz laplaciana L asociada a la red. La entropía de von Neumann promedio de un conjunto se calcula como: ^{[ 10 ]}

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

Para un conjunto de redes aleatorias${\displaystyle G(N,p)}$, la relación entre${\displaystyle S_{VN}}$y${\displaystyle S}$no es monótono cuando la conectividad promedio${\displaystyle p(N-1)}$es variado.

Para conjuntos de redes canónicas de ley de potencias , las dos entropías están relacionadas linealmente. ^{[ 11 ]}

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

Las redes con secuencias de grados esperados dadas sugieren que la heterogeneidad en la distribución de grados esperados implica una equivalencia entre una descripción cuántica y una clásica de las redes, que corresponden respectivamente a la entropía de von Neumann y la entropía de Shannon. ^{[ 12 ]}

Esta definición de la entropía de Von Neumann también puede extenderse a redes multicapa con un enfoque tensorial ^{[ 13 ]} y se ha utilizado con éxito para reducir su dimensionalidad desde un punto de vista estructural. ^{[ 14 ]}

Sin embargo, se ha demostrado que esta definición de entropía no satisface la propiedad de subaditividad (véase la subaditividad de la entropía de Von Neumann ), que se espera que se cumpla teóricamente. Una definición más fundamentada, que satisface esta propiedad fundamental, ha sido introducida por Manlio De Domenico y Biamonte ^{[ 15 ]} como un estado de Gibbs de tipo cuántico.

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

dónde$${\displaystyle Z(\beta )=Tr[e^{-\beta L}]}$$es un factor de normalización que desempeña el papel de la función de partición, y${\displaystyle \beta }$es un parámetro ajustable que permite el análisis multirresolución. Si${\displaystyle \beta }$Se interpreta como un parámetro temporal, esta matriz de densidad es formalmente proporcional al propagador de un proceso difusivo en la parte superior de la red.

Esta característica se ha utilizado para construir una teoría de campo estadística de la dinámica de información compleja, donde la matriz de densidad puede interpretarse en términos de la superposición de operadores de flujos cuya acción es activar flujos de información entre nodos. ^{[ 16 ]} El marco se ha aplicado con éxito para analizar las redes de interacción proteína-proteína de los interactomas virus-humanos, incluido el SARS-CoV-2 , para desentrañar las características sistémicas de la infección de este último a escalas microscópicas, mesoscópicas y macroscópicas, ^{[ 17 ]} así como para evaluar la importancia de los nodos para integrar flujos de información dentro de la red y el papel que desempeñan en la robustez de la red. ^{[ 18 ]}

Este enfoque se ha generalizado para abordar otros tipos de dinámicas, como los paseos aleatorios, sobre redes multicapa, proporcionando una forma eficaz de reducir la dimensionalidad de dichos sistemas sin alterar su estructura. ^{[ 19 ]} Utilizando paseos aleatorios clásicos y de máxima entropía , las matrices de densidad correspondientes se han utilizado para codificar los estados de red del cerebro humano y para evaluar, a múltiples escalas, la capacidad de información del conectoma en diferentes etapas de la demencia. ^{[ 20 ]}

Por analogía con la mecánica estadística, se introducen conjuntos microcanónicos y conjuntos canónicos de redes para la implementación. Una función de partición Z de un conjunto se puede definir como: $${\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)}$$

dónde${\displaystyle {\vec {F}}(\mathbf {a} )={\vec {C}}}$es la restricción, y${\displaystyle a_{ij}}$(${\displaystyle a_{ij}\geq {0}}$) son los elementos de la matriz de adyacencia ,${\displaystyle a_{ij}>0}$si y solo si existe un vínculo entre el nodo i y el nodo j.${\displaystyle \Theta (a_{ij})}$es una función escalón con${\displaystyle \Theta (a_{ij})=1}$si${\displaystyle x>0}$, y${\displaystyle \Theta (a_{ij})=0}$si${\displaystyle x=0}$Los campos auxiliares${\displaystyle h_{ij}}$y${\displaystyle r_{ij}}$Se han introducido como analogía del baño en la mecánica clásica.

Para redes simples no dirigidas, la función de partición se puede simplificar como ^{[ 11 ].}

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

dónde${\displaystyle a_{ij}\in \alpha }$,${\displaystyle \alpha }$es el índice del peso, y para una red simple${\displaystyle \alpha =\{0,1\}}$.

Los conjuntos microcanónicos y los conjuntos canónicos se demuestran con redes no dirigidas simples.

Para un conjunto microcanónico , la entropía de Gibbs${\displaystyle \Sigma }$se define por:

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

dónde${\displaystyle {\mathcal {N}}}$indica la cardinalidad del conjunto, es decir, el número total de redes en el conjunto.

La probabilidad de tener un enlace entre los nodos i y j, con peso${\displaystyle \alpha }$está dado por:

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

Para un conjunto canónico , la entropía se presenta en forma de entropía de Shannon :

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

Conjunto de red${\displaystyle G(N,L)}$con un número determinado de nodos${\displaystyle N}$y enlaces${\displaystyle L}$y su conjunto canónico conjugado${\displaystyle G(N,p)}$se caracterizan como conjuntos microcanónicos y canónicos y tienen entropía de Gibbs.${\displaystyle \Sigma }$y la entropía de Shannon S, respectivamente. La entropía de Gibbs en el${\displaystyle G(N,p)}$El conjunto viene dado por: ^{[ 28 ]}

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

Para${\displaystyle G(N,p)}$conjunto,

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

Insertar${\displaystyle p_{ij}}$en la entropía de Shannon: ^{[ 11 ]}

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

La relación indica que la entropía de Gibbs${\displaystyle \Sigma }$y la entropía de Shannon por nodo S/N de los grafos aleatorios son iguales en el límite termodinámico.${\displaystyle N\to \infty }$.