Network entropy
It has been suggested that Entropy of network ensembles be merged into this article. (Discuss) Proposed since October 2023. |
In
Formulations
According to a publication from Entropy, a journal published by MDPI, there are several formulations in which to measure the 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.[3]
Degree Distribution Shannon Entropy
The
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.[3]
Random Walker Shannon Entropy
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 to any node adjacent to with equal probability. The probability distribution that describes the behavior of this random walker would thus be
,
where is the graph adjacency matrix and is the node degree.
From that, the
and, since , the normalized node entropy is calculated
This leads to a normalized network entropy , calculated by averaging the normalized node entropy over the whole network[4]
The normalized network entropy is maximal when the network is fully connected and decreases the sparser the network becomes . Notice that isolated nodes do not have its probability 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.,[4] what ultimately makes it hard to differentiate scale-free networks using this measure alone.[2]
Random Walker Kolmogorov–Sinai Entropy
The limitations of the random walker Shannon entropy can be overcome by adapting it to use a
This formulation is important to the study of
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
Von Neumann entropy is the extension of the classical Gibbs entropy in a quantum context. This entropy is constructed from a density matrix : 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:[10]
For random network ensemble , the relation between and is nonmonotonic when the average connectivity is varied.
For canonical power-law network ensembles, the two entropies are linearly related.[11]
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.[14]
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[15] as a quantum-like Gibbs state
where
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]
Maximum Entropy Principle
The
Complex Network Ensembles
It is possible to extend the network entropy formulations to instead measure the ensemble entropy. Let be an ensemble of all graphs with the same number of nodes and type of links, is defined as the occurrence probability of a graph . From the maximum entropy principle, it is desired to achieve such that it maximizes the Shannon entropy
Moreover, constraints shall be imposed in order to extract conclusions. Soft constraints (constraints set over the whole ensemble ) will lead to the canonical ensemble whereas hard constraints (constraints set over each graph ) are going to define the microcanonical ensemble. In the end, these ensembles lead to models that can validate a range of network patterns and even reconstruct graphs from limited knowledge, showing that maximum entropy models based on local constraints can quantify the relevance of a set of observed features and extracting meaningful information from huge big data streams in real-time and high-dimensional noisy data.[22]
See also Entropy of network ensembles.
References
- ^ S2CID 761765.
- ^ S2CID 207987035.
- ^ PMID 33265640.
- ^ S2CID 9275909.
- JSTOR 2245067.
- .
- S2CID 15556613.
- PMID 26169480.
- PMID 27386522.
- ISSN 0024-3795.
- S2CID 27419558.
- S2CID 1482301.
- S2CID 16611157.
- S2CID 16776349.
- S2CID 51786781.
- S2CID 222208856.
- .
- S2CID 221104066.
- S2CID 210165034.
- PMID 34746629.
- S2CID 17870175.
- ^ S2CID 52963395.