Entropy of network ensembles

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

1. Levin, E.; Tishby, N.; Solla, S.A. (October 1990). "A statistical approach to learning and generalization in layered neural networks". Proceedings of the IEEE. 78 (10): 1568–1574. doi:10.1109/5.58339. ISSN   1558-2256. S2CID   5254307.
2. Bianconi, Ginestra (2008). "The entropy of randomized network ensembles". EPL (Europhysics Letters). 81 (2): 28005. arXiv: 0708.0153 . Bibcode:2008EL.....8128005B. doi:10.1209/0295-5075/81/28005. ISSN   0295-5075. S2CID   17269886.
3. Menichetti, Giulia; Remondini, Daniel (2014). "Entropy of a network ensemble: definitions and applications to genomic data". Theoretical Biology Forum. 107 (1–2): 77–87. ISSN   0035-6050. PMID   25936214.
4. Krawitz, Peter; Shmulevich, Ilya (27 September 2007). "Entropy of complex relevant components of Boolean networks". Physical Review E. 76 (3): 036115. arXiv: 0708.1538 . Bibcode:2007PhRvE..76c6115K. doi:10.1103/PhysRevE.76.036115. PMID   17930314. S2CID   6192682.
5. Bianconi, Ginestra (27 March 2009). "Entropy of network ensembles". Physical Review E. 79 (3): 036114. arXiv: 0802.2888 . Bibcode:2009PhRvE..79c6114B. doi:10.1103/PhysRevE.79.036114. PMID   19392025. S2CID   26082469.
6. Anand, Kartik; Bianconi, Ginestra (13 October 2009). "Entropy measures for networks: Toward an information theory of complex topologies". Physical Review E. 80 (4): 045102. arXiv: 0907.1514 . Bibcode:2009PhRvE..80d5102A. doi:10.1103/PhysRevE.80.045102. PMID   19905379. S2CID   27419558.
7. Bogacz, Leszek; Burda, Zdzisław; Wacław, Bartłomiej (1 July 2006). "Homogeneous complex networks". Physica A: Statistical Mechanics and Its Applications. 366: 587–607. arXiv: cond-mat/0502124 . Bibcode:2006PhyA..366..587B. doi:10.1016/j.physa.2005.10.024. ISSN   0378-4371. S2CID   119428248.