It has been suggested that this article be merged into Network entropy. ( Discuss) Proposed since October 2023.

This article may require cleanup to meet Wikipedia's quality standards. The specific problem is: Difficult to understand for laymen, an expert with an ability to explain the subject in simpler terms is required. Please help improve this article if you can. (September 2020) ( Learn how and when to remove this message)

A set of networks that satisfies given structural characteristics can be treated as a network ensemble. ^[1] Brought up by Ginestra Bianconi in 2007, the entropy of a network ensemble measures the level of the order or uncertainty of a network ensemble. ^[2]

The entropy is the logarithm of the number of graphs. ^[3] Entropy can also be defined in one network. Basin entropy is the logarithm of the attractors in one Boolean network. ^[4]

Employing approaches from statistical mechanics, the complexity, uncertainty, and randomness of networks can be described by network ensembles with different types of constraints. ^[5]

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:

$${\displaystyle 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 ${\displaystyle {\vec {F}}(\mathbf {a} )={\vec {C}}}$ is the constraint, and ${\displaystyle a_{ij}}$ (${\displaystyle a_{ij}\geq {0}}$) are the elements in the adjacency matrix, ${\displaystyle a_{ij}>0}$ if and only if there is a link between node i and node j. ${\displaystyle \Theta (a_{ij})}$ is a step function with ${\displaystyle \Theta (a_{ij})=1}$ if ${\displaystyle x>0}$, and ${\displaystyle \Theta (a_{ij})=0}$ if ${\displaystyle x=0}$. The auxiliary fields ${\displaystyle h_{ij}}$ and ${\displaystyle r_{ij}}$ have been introduced as analogy to the bath in classical mechanics.

For simple undirected networks, the partition function can be simplified as ^[6]

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

where ${\displaystyle a_{ij}\in \alpha }$, ${\displaystyle \alpha }$ is the index of the weight, and for a simple network ${\displaystyle \alpha =\{0,1\}}$.

Microcanonical ensembles and canonical ensembles are demonstrated with simple undirected networks.

For a microcanonical ensemble, the Gibbs entropy ${\displaystyle \Sigma }$ is defined by:

$${\displaystyle {\begin{aligned}\Sigma &={\frac {1}{N}}\log {\mathcal {N}}\\&={\frac {1}{N}}\log Z|_{h_{ij}(\alpha )=0\forall (i,j,\alpha )}\end{aligned}}}$$

where ${\displaystyle {\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 ${\displaystyle \alpha }$ is given by:

$${\displaystyle \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:

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

Relation between Gibbs and Shannon entropy

Network ensemble ${\displaystyle G(N,L)}$ with given number of nodes ${\displaystyle N}$ and links ${\displaystyle L}$, and its conjugate-canonical ensemble ${\displaystyle G(N,p)}$ are characterized as microcanonical and canonical ensembles and they have Gibbs entropy ${\displaystyle \Sigma }$ and the Shannon entropy S, respectively. The Gibbs entropy in the ${\displaystyle G(N,p)}$ ensemble is given by: ^[7]

$${\displaystyle {N}\Sigma =\log \left({\begin{matrix}{\cfrac {N(N-1)}{2}}\\L\end{matrix}}\right)}$$

For ${\displaystyle G(N,p)}$ ensemble,

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

Inserting ${\displaystyle p_{ij}}$ into the Shannon entropy: ^[6]

$${\displaystyle \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 ${\displaystyle \Sigma }$ and the Shannon entropy per node S/N of random graphs are equal in the thermodynamic limit ${\displaystyle N\to \infty }$.

See also

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

References