Entropy of network ensembles

A set of networks that satisfies given structural characteristics can be treated as a network ensemble. 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.
The entropy is the logarithm of the number of graphs. Entropy can also be defined in one network. Basin entropy is the logarithm of the attractors in one Boolean network.
Employing approaches from statistical mechanics, the complexity, uncertainty, and randomness of networks can 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:
formula_1
where formula_2 is the constraint, and formula_3 (formula_4) are the elements in the adjacency matrix, formula_5 if and only if there is a link between node i and node j. formula_6 is a step function with formula_7 if formula_8, and formula_9 if formula_10. The auxiliary fields formula_11 and formula_12 have been introduced as analogy to the bath in classical mechanics.
For simple undirected networks, the partition function can be simplified as
formula_13
where formula_14, formula_15 is the index of the weight, and for a simple network formula_16.
Microcanonical ensembles and canonical ensembles are demonstrated with simple undirected networks.
For a microcanonical ensemble, the Gibbs entropy formula_17 is defined by:
formula_18
where formula_19 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 formula_15 is given by:
formula_21
For a canonical ensemble, the entropy is presented in the form of a Shannon entropy:
formula_22
Relation between Gibbs and Shannon entropy.
Network ensemble formula_23 with given number of nodes formula_24 and links formula_25, and its conjugate-canonical ensemble formula_26 are characterized as microcanonical and canonical ensembles and they have Gibbs entropy formula_17 and the Shannon entropy S, respectively. The Gibbs entropy in the formula_26 ensemble is given by:
formula_29
For formula_26 ensemble,
formula_31
Inserting formula_32 into the Shannon entropy:
formula_33
The relation indicates that the Gibbs entropy formula_17 and the Shannon entropy per node S/N of random graphs are equal in the thermodynamic limit formula_35.
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 formula_36 with the expression of Laplacian matrix L associated with the network. The average von Neumann entropy of an ensemble is calculated as:
formula_37
For random network ensemble formula_26, the relation between formula_39 and formula_40 is nonmonotonic when the average connectivity formula_41 is varied.
For canonical power-law network ensembles, the two entropies are linearly related.
formula_42
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.