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.
[1] It is a relevant metric to quantitatively characterize real complex networks and can also be used to quantify network complexity[1][2] According to a 2018 publication by Zenil et al. there are several formulations by which to calculate network entropy and, as a rule, they all require a particular property of the graph to be focused, such as the adjacency matrix, degree sequence, degree distribution or number of bifurcations, what might lead to values of entropy that aren't invariant to the chosen network description.
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.
[3] Due to the limits of the previous formulation, it is possible to take a different approach while keeping the usage of the original Shannon Entropy equation.
Consider a random walker that travels around the graph, going from a node
, calculated by averaging the normalized node entropy over the whole network:[4]
This formulation of network entropy has low sensitivity to hubs due to the logarithmic factor and is more meaningful for weighted networks.,[4] what ultimately makes it hard to differentiate scale-free networks using this measure alone.
satisfies a variational principal[5] that is equivalent to the dynamic entropy for unweighted networks, i.e., the adjacency matrix consists exclusively of boolean values.
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.
[6] Other than that, the Kolmogorov entropy is related to the Ricci curvature of the network,[7] a metric that has been used to differentiate stages of cancer from gene co-expression networks,[8] as well as to give hallmarks of financial crashes from stock correlation networks[9] Von Neumann entropy is the extension of the classical Gibbs entropy in a quantum context.
The average von Neumann entropy of an ensemble is calculated as:[10]
For canonical power-law network ensembles, the two entropies are linearly related.
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.
[12] This definition of the Von Neumann entropy can also be extended to multilayer networks with tensorial approach[13] and has been used successfully to reduce their dimensionality from a structural point of perspective.
A more grounded definition, satisfying this fundamental property, has been introduced by Manlio De Domenico and Biamonte[15] as a quantum-like Gibbs state
is a normalizing factor which plays the role of the partition function, and
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.
[16] 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,[17] as well as to assess the importance of nodes for integrating information flows within the network and the role they play in network robustness.
[18] 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.
[19] 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.
[20] The maximum entropy principle is a variational principal stating that the probability distribution best representing the current state of a system is the one which maximizes the Shannon entropy.
[21] This concept can be used to generate an ensemble of random graphs with given structural properties derived from the maximum entropy approach which, in its turn, describes the most probable network configuration: the maximum entropy principle allows for maximally unbiased information when lacking complete knowledge (microscopic configuration is not accessible, e.g.: we don't know the adjacency matrix).
On the other hand, this ensemble serves as a null model when the actual microscopic configuration of the network is known, allowing to assess the significance of empirical patterns found in the network[22] It is possible to extend the network entropy formulations to instead measure the ensemble entropy.
Basin entropy is the logarithm of the attractors in one Boolean network.
For simple undirected networks, the partition function can be simplified as[11]
are characterized as microcanonical and canonical ensembles and they have Gibbs entropy
and the Shannon entropy per node S/N of random graphs are equal in the thermodynamic limit