Entropy of network ensembles

A set of networks that satisfies given structural characteristics can be treated as a network ensemble. The entropy of a network ensemble measures the level of the order or uncertainty of a network ensemble, which was first brought up by Ginestra Bianconi in 2007. Basically, the entropy is the logarithm of the number of graphs. To clarify, entropy can also be defined in one network. Basin entropy is the logarithm of the attractors in one Boolean network.

Employing statistical mechanics approaches, the complexity, uncertainty, and randomness of networks are able to be described by network ensembles with different types of constraints.

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

$\quad {Z}=\sum _{\mathbf {a} }\delta [{\vec {F}}(\mathbf {a} )-{\vec {C}}]{\textrm {exp}}{\Big (}\sum _{ij}h_{ij}\Theta (a_{ij})+r_{ij}a_{ij}{\Big )}$

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

$\quad {Z}=\sum _{\{a_{ij}\}}\prod _{k}\delta ({\textrm {constraint}}_{k}(\{a_{ij}\})){\textrm {exp}}{\Big (}\sum _{i<j}\sum _{\alpha }h_{ij}(\alpha )\delta _{a_{ij},\alpha }{\Big )}$

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

$\quad \Sigma ={\cfrac {1}{N}}\mathrm {log} {\mathcal {N}}$

$\qquad ={\cfrac {1}{N}}\mathrm {log} Z|_{h_{ij}(\alpha )=0\forall (i,j,\alpha )}$

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

$\quad \pi _{ij}(\alpha )={\cfrac {\partial {\mathrm {log} }Z}{\partial {h_{ij}}(\alpha )}}$

For a canonical ensemble, the entropy is presented in the form of a Shannon entropy

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

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

$\quad {N}\Sigma =\mathrm {log} {\Bigg (}{\begin{matrix}{\cfrac {N(N-1)}{2}}\\L\end{matrix}}{\Bigg )}$

For $G(N,p)$ ensemble,

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

Inserting $p_{ij}$ into the Shannon entropy,

$\quad \Sigma =S/N+{\cfrac {1}{2N}}{\Big [}\mathrm {log} {\Big (}{\cfrac {N(N-1)}{2L}}{\Big )}-\mathrm {log} {\Big (}{\cfrac {N(N-1)}{2}}-L{\Big )}{\Big ]}$

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\rightarrow \infty$.

Von Neumann entropy

Von Neumann entropy is the extension of the classical Gibbs entropy in the quantum context. This entropy is constructed from a density matrix $\rho$ with the expression of Laplacian matrix L associated with the network. The average von Neumann entropy of an ensemble is calculated as

$\quad {S}_{VN}=-\langle \mathrm {Tr} \rho \mathrm {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

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

Von Neumann entropy can also be calculated in multilayer networks with tensorial approach

See also

• Canonical ensemble
• Microcanonical ensemble
• Maximum-entropy random graph model
• Graph entropy