Network entropy
≈ 8 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In network science, the network entropy is a disorder measure derived from information theory to describe the level of randomness and the amount of information encoded in a graph. It is a relevant metric to quantitatively characterize real complex networks and can also be used to quantify network complexity
In network science, the network entropy is a disorder measure derived from information theory to describe the level of randomness and the amount of information encoded in a graph. It is a relevant metric to quantitatively characterize real complex networks and can also be used to quantify network complexity \mathcal{H} = - \sum_{k=1}^{N - 1} P(k) \ln{P(k)} This formulation has limited use with regards to complexity, information content, causation and temporal information. Be that as it may, algorithmic complexity has the ability to characterize any general or universal property of a graph or network and it is proven that graphs with low entropy have low algorithmic complexity because the statistical regularities found in a graph are useful for computer programs to recreate it. The same cannot be said for high entropy networks though, as these might have any value for algorithmic complexity. p_{ij} = \begin{cases} \frac{1}{k_i}, & \text{if } A_{ij} = 1 \\ 0, & \text{if } A_{ij} = 0 \\ \end{cases} , where (A_{ij}) is the graph adjacency matrix and k_i is the node i degree. From that, the Shannon entropy from each node \mathcal{S}_i can be defined as \mathcal{S}_i = - \sum_{j = 1}^{N - 1} p_{ij} \ln{p_{ij}} = \ln{k_i} and, since max(k_i) = N - 1 , the normalized node entropy \mathcal{H}_i is calculated \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)} This leads to a normalized network entropy \mathcal{H} , calculated by averaging the normalized node entropy over the whole network: \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} The normalized network entropy is maximal \mathcal{H} = 1 when the network is fully connected and decreases the sparser the network becomes \mathcal{H} = 0 . Notice that isolated nodes k_i = 0 do not have its probability p_{ij} defined and, therefore, are not considered when measuring the network entropy. This formulation of network entropy has low sensitivity to hubs due to the logarithmic factor and is more meaningful for weighted networks., what ultimately makes it hard to differentiate scale-free networks using this measure alone. \mathcal{H} = \ln \lambda This formulation is important to the study of network robustness, i.e., the capacity of the network to withstand random structural changes. Robustness is actually difficult to be measured numerically whereas the entropy can be easily calculated for any network, which is especially important in the context of non-stationary networks. The entropic fluctuation theorem shows that this entropy is positively correlated to robustness and hence a greater insensitivity of an observable to dynamic or structural perturbations of the network. Moreover, the eigenvalues are inherently related to the multiplicity of internal pathways, leading to a negative correlation between the topological entropy and the shortest average path length. Other than that, the Kolmogorov entropy is related to the Ricci curvature of the network, a metric that has been used to differentiate stages of cancer from gene co-expression networks, as well as to give hallmarks of financial crashes from stock correlation networks
Von Neumann entropy
Von Neumann entropy is the extension of the classical Gibbs entropy in a quantum context. This entropy is constructed from a density matrix \rho : historically, the first proposed candidate for such a density matrix has been an expression of the Laplacian matrix L associated with the network. The average von Neumann entropy of an ensemble is calculated as: {S}_{VN} = -\langle\mathrm{Tr}\rho\log(\rho)\rangle For random network ensemble G(N,p) , the relation between S_{VN} and S is nonmonotonic when the average connectivity p(N-1) is varied. For canonical power-law network ensembles, the two entropies are linearly related. {S}_{VN} = \eta {S/N} + \beta Networks with given expected degree sequences suggest that, heterogeneity in the expected degree distribution implies an equivalence between a quantum and a classical description of networks, which respectively corresponds to the von Neumann and the Shannon entropy. This definition of the Von Neumann entropy can also be extended to multilayer networks with tensorial approach and has been used successfully to reduce their dimensionality from a structural point of perspective. However, it has been shown that this definition of entropy does not satisfy the property of sub-additivity (see Von Neumann entropy's subadditivity), expected to hold theoretically. A more grounded definition, satisfying this fundamental property, has been introduced by Manlio De Domenico and Biamonte as a quantum-like Gibbs state \rho(\beta)=\frac{e^{-\beta L}}{Z(\beta)} where Z(\beta)=Tr[e^{-\beta L}] is a normalizing factor which plays the role of the partition function, and \beta is a tunable parameter which allows multi-resolution analysis. If \beta is interpreted as a temporal parameter, this density matrix is formally proportional to the propagator of a diffusive process on the top of the network. This feature has been used to build a statistical field theory of complex information dynamics, where the density matrix can be interpreted in terms of the super-position of streams operators whose action is to activate information flows among nodes. The framework has been successfully applied to analyze the protein-protein interaction networks of virus-human interactomes, including the SARS-CoV-2, to unravel the systemic features of infection of the latter at microscopic, mesoscopic and macroscopic scales, as well as to assess the importance of nodes for integrating information flows within the network and the role they play in network robustness. This approach has been generalized to deal with other types of dynamics, such as random walks, on the top of multilayer networks, providing an effective way to reduce the dimensionality of such systems without altering their structure. Using both classical and maximum-entropy random walks, the corresponding density matrices have been used to encode the network states of the human brain and to assess, at multiple scales, connectome's information capacity at different stages of dementia.
Gibbs and Shannon entropy
By analogy to statistical mechanics, microcanonical ensembles and canonical ensembles of networks are introduced for the implementation. A partition function Z of an ensemble can be defined as: 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) where \vec{F}(\mathbf{a})=\vec{C} is the constraint, and a_{ij} ( a_{ij} \geq {0} ) are the elements in the adjacency matrix, a_{ij} > 0 if and only if there is a link between node i and node j. \Theta(a_{ij}) is a step function with \Theta(a_{ij}) = 1 if x > 0 , and \Theta(a_{ij}) = 0 if x = 0 . The auxiliary fields h_{ij} and r_{ij} have been introduced as analogy to the bath in classical mechanics. For simple undirected networks, the partition function can be simplified as Z = \sum_{\{a_{ij}\}} \prod_{k}\delta(\textrm{constraint}_{k}(\{a_{ij}\})) \exp\left(\sum_{i where a_{ij}\in\alpha , \alpha is the index of the weight, and for a simple network \alpha=\{0,1\} . Microcanonical ensembles and canonical ensembles are demonstrated with simple undirected networks. For a microcanonical ensemble, the Gibbs entropy \Sigma is defined by: \begin{align} \Sigma &= \frac{1}{N} \log\mathcal{N} \\ &= \frac{1}{N} \log Z|_{h_{ij}(\alpha)=0\forall(i,j,\alpha)} \end{align} where \mathcal{N} indicates the cardinality of the ensemble, i.e., the total number of networks in the ensemble. The probability of having a link between nodes i and j, with weight \alpha is given by: \pi_{ij}(\alpha) = \frac{\partial \log Z}{\partial{h_{ij}}(\alpha)} For a canonical ensemble, the entropy is presented in the form of a Shannon entropy: {S}=-\sum_{i
Relation between Gibbs and Shannon entropy
Network ensemble G(N,L) with given number of nodes N and links L , and its conjugate-canonical ensemble G(N,p) are characterized as microcanonical and canonical ensembles and they have Gibbs entropy \Sigma and the Shannon entropy S, respectively. The Gibbs entropy in the G(N,p) ensemble is given by: {N}\Sigma = \log\left(\begin{matrix}\cfrac{N(N-1)}{2}\\L\end{matrix}\right) For G(N,p) ensemble, {p}_{ij} = p = \cfrac{2L}{N(N-1)} Inserting p_{ij} into the Shannon entropy: \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] The relation indicates that the Gibbs entropy \Sigma and the Shannon entropy per node S/N of random graphs are equal in the thermodynamic limit N\to\infty .
See also
Canonical ensemble Microcanonical ensemble Maximum-entropy random graph model Graph entropy
Text derived from https://en.wikipedia.org/w/index.php?oldid=1369642035 under CC BY-SA 4.0; modifications have been made.