Network entropy

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. 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.

Formulations

Degree Distribution Shannon Entropy

The Shannon entropy can be measured for the network degree probability distribution as an average measurement of the heterogeneity of the network.

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

Random Walker Shannon Entropy

Suppose a random walker goes from node $i$ to any other node $j$ in a network. This results in a probability distribution $p_{ij}={\frac {1}{k_{i}}}$ if $A_{ij}=1$ else $0$, where $(A_{ij})$ is the graph adjacency matrix and $k_{i}$ is the node $i$ degree. From that, the Shannon entropy can be measured for each node, what results in 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}{\frac {1}{\ln(N-1)}}{\bigg (}-\sum _{j=1}^{N-1}p_{ij}\ln {p_{ij}}{\bigg )}={\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. .

Random Walker Kolmogorov–Sinai Entropy

The limitations of the random walker Shannon entropy can be overcome by adapting it to use a Kolmogorov–Sinai entropy. In this context, network entropy is the entropy of a stochastic matrix associated with the graph adjacency matrix $(A_{ij})$ and the random walker Shannon entropy is called the dynamic entropy of the network. From that, let $\lambda$ be the dominant eigenvalue of $(A_{ij})$. It is proven that $\ln \lambda$ satisfies a variational principal that is equivalent to the dynamic entropy for unweighted networks, i.e., the adjacency matrix consists exclusively of boolean values. Therefore, the topological entropy is defined as

${\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, what is specially import 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 .

Maximum Entropy Principle

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 . 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

Complex Network Ensembles

It is possible to extend the network entropy formulations to instead measure the ensemble entropy. Let $\Omega$ be an ensemble of all graphs $G$ with the same number $N$ of nodes and type of links, $P(G)$ is defined as the occurrence probability of a graph $G\in \Omega$. From the maximum entropy principle, it is desired to achieve $P(G)$ such that it maximizes the Shannon entropy

${\mathcal {H}}=-\sum _{G\in \Omega }P(G)\ln P(G)$

Moreover, constraints shall be imposed in order to extract conclusions. Soft constraints (constraints set over the whole ensemble $\Omega$) will lead to the canonical ensemble whereas hard constraints (constraints set over each graph $G$) 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.