Network entropy

{{Short description|Measure of connection disorder in a network}}

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.<ref name="anand2014entropy">{{cite journal |last1=Anand |first1=Kartik |last2=Krioukov |first2=Dmitri |last3=Bianconi |first3=Ginestra |title=Entropy distribution and condensation in random networks with a given degree distribution |journal=Physical Review E |date=2014 |volume=89 |issue=6 |article-number=062807 |doi=10.1103/PhysRevE.89.062807 |pmid=25019833 |arxiv=1403.5884 |bibcode=2014PhRvE..89f2807A |s2cid=761765 |url=https://journals.aps.org/pre/abstract/10.1103/PhysRevE.89.062807 |ref=anand2014entropy}}</ref> It is a relevant metric to quantitatively characterize real complex networks and can also be used to quantify network complexity<ref name="anand2014entropy" /><ref name="freitas2019detailed">{{cite journal|ref=freitas2019detailed|last1=Freitas |first1=Cristopher GS |last2=Aquino |first2=Andre LL |last3=Ramos |first3=Heitor S |last4=Frery |first4=Alejandro C |last5=Rosso |first5=Osvaldo A |title=A detailed characterization of complex networks using Information Theory |journal=Scientific Reports |date=2019 |volume=9 |issue=1 |page=16689 |doi=10.1038/s41598-019-53167-5 |pmid=31723172 |pmc=6853913 |bibcode=2019NatSR...916689F |s2cid=207987035 }}</ref>

== Formulations == According to a 2018 publication by Zenil ''et al.'' there are several formulations by which to calculate 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.<ref name="zenil2018review" />

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

<math>\mathcal{H} = - \sum_{k=1}^{N - 1} P(k) \ln{P(k)}</math>

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.<ref name="zenil2018review">{{cite journal |last1=Zenil |first1=Hector |last2=Kiani |first2=Narsis A |last3=Tegnér |first3=Jesper |title=A review of graph and network complexity from an algorithmic information perspective |journal=Entropy |date=2018 |volume=20 |issue=8 |page=551 |doi=10.3390/e20080551 |pmid=33265640 |pmc=7513075 |bibcode=2018Entrp..20..551Z |ref=zenil2018review|doi-access=free }}</ref>

=== Random Walker Shannon Entropy ===

Due to the limits of the previous formulation, it is possible to take a different approach while keeping the usage of the original Shannon Entropy equation.

Consider a random walker that travels around the graph, going from a node <math>i</math> to any node <math>j</math> adjacent to <math>i</math> with equal probability. The probability distribution <math>p_{ij}</math> that describes the behavior of this random walker would thus be

<math>p_{ij} = \begin{cases} \frac{1}{k_i}, & \text{if } A_{ij} = 1 \\ 0, & \text{if } A_{ij} = 0 \\ \end{cases}</math>,

where <math>(A_{ij})</math> is the graph adjacency matrix and <math>k_i</math> is the node <math>i</math> degree.

From that, the Shannon entropy from each node <math>\mathcal{S}_i</math> can be defined as

<math>\mathcal{S}_i = - \sum_{j = 1}^{N - 1} p_{ij} \ln{p_{ij}} = \ln{k_i}</math>

and, since <math>max(k_i) = N - 1</math>, the normalized node entropy <math>\mathcal{H}_i</math> is calculated

<math>\mathcal{H}_i = \frac{\mathcal{S}_i}{max(\mathcal{S}_i)} = \frac{\ln{k_i}}{\ln(max(k_i))} = \frac{\ln{k_i}}{\ln(N - 1)}</math>

This leads to a normalized network entropy <math>\mathcal{H}</math>, calculated by averaging the normalized node entropy over the whole network:<ref name="small2013complex">{{cite book |last1=Small |first1=Michael |title=2013 IEEE International Symposium on Circuits and Systems (ISCAS2013) |chapter=Complex networks from time series: Capturing dynamics |date=2013 |pages=2509–2512 |doi=10.1109/ISCAS.2013.6572389 |isbn=978-1-4673-5762-3 |s2cid=9275909 |ref=small2013complex}}</ref>

<math>\mathcal{H} = \frac{1}{N} \sum_{i = 1}^N \mathcal{H}_i = \frac{1}{N \ln(N - 1)} \sum_{i = 1}^N \ln{k_i}</math>

The normalized network entropy is maximal <math>\mathcal{H} = 1</math> when the network is fully connected and decreases the sparser the network becomes <math>\mathcal{H} = 0</math>. Notice that isolated nodes <math>k_i = 0</math> do not have its probability <math>p_{ij}</math> 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.,<ref name="small2013complex"/> what ultimately makes it hard to differentiate scale-free networks using this measure alone.<ref name="freitas2019detailed"/>

=== 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 <math>(A_{ij})</math> and the random walker Shannon entropy is called the ''dynamic entropy'' of the network. From that, let <math>\lambda</math> be the dominant eigenvalue of <math>(A_{ij})</math>. It is proven that <math>\ln \lambda</math> satisfies a variational principal<ref>{{cite journal |last1=Arnold |first1=Ludwig |last2=Gundlach |first2=Volker Matthias |last3=Demetrius |first3=Lloyd |title=Evolutionary formalism for products of positive random matrices |journal=The Annals of Applied Probability |date=1994 |volume=4 |issue=3 |pages=859–901|doi=10.1214/aoap/1177004975 |jstor=2245067 |doi-access=free }}</ref> 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

<math>\mathcal{H} = \ln \lambda</math>

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, which is especially important 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.<ref name="demetrius2005robustness">{{cite journal |last1=Demetrius |first1=Lloyd |last2=Manke |first2=Thomas |title=Robustness and network evolution—an entropic principle |journal=Physica A: Statistical Mechanics and Its Applications |date=2005 |volume=346 |issue=3 |pages=682–696|doi=10.1016/j.physa.2004.07.011 |bibcode=2005PhyA..346..682D |url=https://www.sciencedirect.com/science/article/abs/pii/S0378437104009975|url-access=subscription }}</ref>

Other than that, the Kolmogorov entropy is related to the Ricci curvature of the network,<ref>{{cite journal |last1=Lott |first1=J. |last2=Villani |first2=C. |title=Ricci curvature for metric-measure spaces via optimal transport |journal=Annals of Mathematics |date=2009|volume=169 |issue=3 |pages=903–991 |doi=10.4007/annals.2009.169.903 |s2cid=15556613 |arxiv=math/0412127 }}</ref> a metric that has been used to differentiate stages of cancer from gene co-expression networks,<ref>{{cite journal |last1=Sandhu |first1=R. |last2=Georgiou |first2=T. |last3=Reznik |first3=E. |last4=Zhu |first4=L. |last5=Kolesov |first5=I. |last6=Senbabaoglu |first6=Y. |last7=Tannenbaum |first7=A. |title=Graph curvature for differentiating cancer networks |journal=Scientific Reports |date=2015|volume=5 |article-number=12323 |doi=10.1038/srep12323 |pmid=26169480 |pmc=4500997 |bibcode=2015NatSR...512323S }}</ref> as well as to give hallmarks of financial crashes from stock correlation networks<ref>{{cite journal |last1=Sandhu |first1=Romeil S |last2=Georgiou |first2=Tryphon T |last3=Tannenbaum |first3=Allen R |title=Ricci curvature: An economic indicator for market fragility and systemic risk |journal=Science Advances |date=2016|volume=2 |issue=5 |article-number=e1501495 |doi=10.1126/sciadv.1501495 |pmid=27386522 |pmc=4928924 |bibcode=2016SciA....2E1495S }}</ref>

===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 <math>\rho</math>: historically, the first proposed candidate for such a density matrix has been an expression of the Laplacian matrix L associated with the network. The average von Neumann entropy of an ensemble is calculated as:<ref>{{cite journal |last1=Du |first1=Wenxue |last2=Li |first2=Xueliang |last3=Li |first3=Yiyang |last4=Severini |first4=Simone |title=A note on the von Neumann entropy of random graphs |journal=Linear Algebra and Its Applications |date=30 December 2010 |volume=433 |issue=11 |pages=1722–1725 |doi=10.1016/j.laa.2010.06.040 |language=en |issn=0024-3795|doi-access=free }}</ref>

<math display="block">{S}_{VN} = -\langle\mathrm{Tr}\rho\log(\rho)\rangle</math>

For random network ensemble <math>G(N,p)</math>, the relation between <math>S_{VN}</math> and <math>S</math> is nonmonotonic when the average connectivity <math>p(N-1)</math> is varied.

For canonical power-law network ensembles, the two entropies are linearly related.<ref name=highlight>{{cite journal |last1=Anand |first1=Kartik |last2=Bianconi |first2=Ginestra |title=Entropy measures for networks: Toward an information theory of complex topologies |journal=Physical Review E |date=13 October 2009 |volume=80 |issue=4 |article-number=045102 |doi=10.1103/PhysRevE.80.045102 |pmid=19905379 |arxiv=0907.1514 |bibcode=2009PhRvE..80d5102A |s2cid=27419558 }}</ref>

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.<ref>{{cite journal |last1=Anand |first1=Kartik |last2=Bianconi |first2=Ginestra |last3=Severini |first3=Simone |title=Shannon and von Neumann entropy of random networks with heterogeneous expected degree |journal=Physical Review E |date=18 March 2011 |volume=83 |issue=3 |article-number=036109 |doi=10.1103/PhysRevE.83.036109 |pmid=21517560 |arxiv=1011.1565 |bibcode=2011PhRvE..83c6109A |s2cid=1482301 }}</ref>

This definition of the Von Neumann entropy can also be extended to multilayer networks with tensorial approach<ref>{{cite journal |last1=De Domenico |first1=Manlio |last2=Solé-Ribalta |first2=Albert |last3=Cozzo |first3=Emanuele |last4=Kivelä |first4=Mikko |last5=Moreno |first5=Yamir |last6=Porter |first6=Mason A. |last7=Gómez |first7=Sergio |last8=Arenas |first8=Alex |title=Mathematical Formulation of Multilayer Networks |journal=Physical Review X |date=4 December 2013 |volume=3 |issue=4 |article-number=041022 |doi=10.1103/PhysRevX.3.041022 |arxiv=1307.4977 |bibcode=2013PhRvX...3d1022D |s2cid=16611157 }}</ref> and has been used successfully to reduce their dimensionality from a structural point of perspective.<ref>{{cite journal |last1=De Domenico |first1=Manlio |last2=Nicosia |first2=Vincenzo |last3=Arenas |first3=Alex |last4=Latora |first4=Vito |title= Structural reducibility of multilayer networks |journal=Nature Communications |date=23 April 2015 |volume=6 |article-number= 6864 |doi= 10.1038/ncomms7864 |pmid=25904309 |bibcode=2015NatCo...6.6864D |s2cid=16776349 |url=http://deim.urv.cat/%7Ealephsys/papers/reducibility.pdf }}</ref>

However, it has been shown that this definition of entropy does not satisfy the property of sub-additivity (see Von Neumann entropy's subadditivity), expected to hold theoretically. A more grounded definition, satisfying this fundamental property, has been introduced by Manlio De Domenico and Biamonte<ref>{{cite journal |last1=De Domenico |first1=Manlio |last2=Biamonte |first2=Jacob|title=Spectral Entropies as Information-Theoretic Tools for Complex Network Comparison |journal=Physical Review X |date=21 December 2016 |volume=6 |issue=4 |article-number=041062 |doi=10.1103/PhysRevX.6.041062|arxiv=1609.01214 |bibcode=2016PhRvX...6d1062D |s2cid=51786781 }}</ref> as a quantum-like Gibbs state

where <math display="block">Z(\beta)=Tr[e^{-\beta L}]</math> is a normalizing factor which plays the role of the partition function, and <math>\beta</math> is a tunable parameter which allows multi-resolution analysis. If <math>\beta</math> is interpreted as a temporal parameter, this density matrix is formally proportional to the propagator of a diffusive process on the top of the network.

This feature has been used to build a statistical field theory of complex information dynamics, where the density matrix can be interpreted in terms of the super-position of streams operators whose action is to activate information flows among nodes.<ref>{{cite journal |last1=Ghavasieh |first1=Arsham|last2=Nicolini |first2=Carlo|last3=De Domenico |first3=Manlio|title= Statistical physics of complex information dynamics |journal=Physical Review E |date=10 November 2020 |volume=102 |issue=5 |article-number= 052304 |doi=10.1103/PhysRevE.102.052304|pmid=33327131 |arxiv=2010.04014 |bibcode=2020PhRvE.102e2304G |s2cid=222208856 }}</ref> The framework has been successfully applied to analyze the protein-protein interaction networks of virus-human interactomes, including the SARS-CoV-2, to unravel the systemic features of infection of the latter at microscopic, mesoscopic and macroscopic scales,<ref>{{cite journal |last1=Ghavasieh |first1=Arsham|last2=Bontorin |first2=Sebastiano|last3=Artime |first3=Oriol|last4=Verstraete |first4=Nina|last5=De Domenico |first5=Manlio|title= Multiscale statistical physics of the pan-viral interactome unravels the systemic nature of SARS-CoV-2 infections |journal=Communications Physics |date=23 April 2021 |volume=4 |issue=1 |page= 83 |doi=10.1038/s42005-021-00582-8|arxiv=2008.09649|bibcode=2021CmPhy...4...83G |doi-access=free }}</ref> as well as to assess the importance of nodes for integrating information flows within the network and the role they play in network robustness.<ref>{{cite journal |last1=Ghavasieh |first1=Arsham|last2=Stella |first2=Massimo|last3=Biamonte |first3=Jacob|last4=De Domenico |first4=Manlio|title= Unraveling the effects of multiscale network entanglement on empirical systems|journal=Communications Physics |date=10 June 2021 |volume=4 |issue=1 |page= 129 |doi=10.1038/s42005-021-00633-0|arxiv=2008.05368|bibcode=2021CmPhy...4..129G |s2cid=221104066 }}</ref>

This approach has been generalized to deal with other types of dynamics, such as random walks, on the top of multilayer networks, providing an effective way to reduce the dimensionality of such systems without altering their structure.<ref>{{cite journal |last1=Ghavasieh |first1=Arsham|last2=De Domenico |first2=Manlio|title= Enhancing transport properties in interconnected systems without altering their structure |journal=Physical Review Research |date= 13 February 2020 |volume=2 |issue=1 |pages= 13–15 |doi=10.1103/PhysRevResearch.2.013155|arxiv=2001.04450 |bibcode=2020PhRvR...2a3155G |s2cid=210165034 }}</ref> Using both classical and maximum-entropy random walks, the corresponding density matrices have been used to encode the network states of the human brain and to assess, at multiple scales, connectome's information capacity at different stages of dementia.<ref>{{cite journal |last1=Benigni |first1=Barbara|last2=Ghavasieh |first2=Arsham|last3=Corso |first3=Alessandra|last4=D'Andrea |first4=Valeria|last5=De Domenico |first5=Manlio|title=Persistence of information flow: a multiscale characterization of human brain |journal=Network Neuroscience |date= 22 June 2021 |volume= 5|issue=3 |pages= 831–850 |doi=10.1162/netn_a_00203 |pmid=34746629 |pmc=8567833 |arxiv=|doi-access=free }}</ref>

== Maximum Entropy Principle == {{Main|Principle of maximum entropy}} 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.<ref>{{cite journal |last=Jaynes |first=E. T. |author-link = Edwin Thompson Jaynes |year=1957 |title=Information Theory and Statistical Mechanics |url=http://bayes.wustl.edu/etj/articles/theory.1.pdf |journal=Physical Review |series=Series II |volume=106 |issue=4 |pages=620–630 |doi=10.1103/PhysRev.106.620 |mr=87305 |bibcode = 1957PhRv..106..620J |s2cid=17870175 }}</ref> 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<ref name="cimini2019statistical">{{cite journal |last1=Cimini |first1=Giulio |last2=Squartini |first2=Tiziano |last3=Saracco |first3=Fabio |last4=Garlaschelli |first4=Diego |last5=Gabrielli |first5=Andrea |last6=Caldarelli |first6=Guido |title=The statistical physics of real-world networks |journal=Nature Reviews Physics |date=2019 |volume=1 |issue=1 |pages=58–71|doi=10.1038/s42254-018-0002-6 |arxiv=1810.05095 |bibcode=2019NatRP...1...58C |s2cid=52963395 }}</ref>

== Network Ensembles ==

It is possible to extend the network entropy formulations to instead measure the ensemble entropy. A set of networks that satisfies given structural characteristics can be treated as a network ensemble.<ref>{{cite journal |last1=Levin |first1=E. |last2=Tishby |first2=N. |last3=Solla |first3=S.A.|author3-link=Sara Solla |title=A statistical approach to learning and generalization in layered neural networks |journal=Proceedings of the IEEE |date=October 1990 |volume=78 |issue=10 |pages=1568–1574 |doi=10.1109/5.58339 |s2cid=5254307 |issn=1558-2256}}</ref> 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.<ref name=year2007>{{cite journal |title=The entropy of randomized network ensembles |journal=EPL (Europhysics Letters) |year=2008 |volume=81 |issue=2 |doi=10.1209/0295-5075/81/28005 |language=en |issn=0295-5075|last1=Bianconi |first1=Ginestra |article-number=28005 |arxiv=0708.0153 |bibcode=2008EL.....8128005B |s2cid=17269886 }}</ref>

The entropy is the logarithm of the number of graphs.<ref>{{cite journal |last1=Menichetti |first1=Giulia |last2=Remondini |first2=Daniel |title=Entropy of a network ensemble: definitions and applications to genomic data |journal=Theoretical Biology Forum |date=2014 |volume=107 |issue=1–2 |pages=77–87 |pmid=25936214 |issn=0035-6050}}</ref> Entropy can also be defined in one network. Basin entropy is the logarithm of the attractors in one Boolean network.<ref>{{cite journal |last1=Krawitz |first1=Peter |last2=Shmulevich |first2=Ilya |title=Entropy of complex relevant components of Boolean networks |journal=Physical Review E |date=27 September 2007 |volume=76 |issue=3 |article-number=036115 |doi=10.1103/PhysRevE.76.036115 |pmid=17930314 |arxiv=0708.1538 |bibcode=2007PhRvE..76c6115K |s2cid=6192682 }}</ref>

Employing approaches from statistical mechanics, the complexity, uncertainty, and randomness of networks can be described by network ensembles with different types of constraints.<ref>{{cite journal |last1=Bianconi |first1=Ginestra |title=Entropy of network ensembles |journal=Physical Review E |date=27 March 2009 |volume=79 |issue=3 |article-number=036114 |doi=10.1103/PhysRevE.79.036114 |pmid=19392025 |arxiv=0802.2888 |bibcode=2009PhRvE..79c6114B |s2cid=26082469 }}</ref>

===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: <math display="block">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)</math>

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

For simple undirected networks, the partition function can be simplified as<ref name=highlight>{{cite journal |last1=Anand |first1=Kartik |last2=Bianconi |first2=Ginestra |title=Entropy measures for networks: Toward an information theory of complex topologies |journal=Physical Review E |date=13 October 2009 |volume=80 |issue=4 |article-number=045102 |doi=10.1103/PhysRevE.80.045102 |pmid=19905379 |arxiv=0907.1514 |bibcode=2009PhRvE..80d5102A |s2cid=27419558 }}</ref>

<math display="block">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)</math>

where <math>a_{ij}\in\alpha</math>, <math>\alpha</math> is the index of the weight, and for a simple network <math>\alpha=\{0,1\}</math>.

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

'''For a microcanonical ensemble''', the Gibbs entropy <math>\Sigma</math> is defined by:

<math display="block">\begin{align} \Sigma &= \frac{1}{N} \log\mathcal{N} \\ &= \frac{1}{N} \log Z|_{h_{ij}(\alpha)=0\forall(i,j,\alpha)} \end{align}</math>

where <math>\mathcal{N}</math> 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 <math>\alpha</math> is given by:

<math display="block">\pi_{ij}(\alpha) = \frac{\partial \log Z}{\partial{h_{ij}}(\alpha)}</math>

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

===Relation between Gibbs and Shannon entropy=== Network ensemble <math>G(N,L)</math> with given number of nodes <math>N</math> and links <math>L</math>, and its conjugate-canonical ensemble <math>G(N,p)</math> are characterized as microcanonical and canonical ensembles and they have Gibbs entropy <math>\Sigma</math> and the Shannon entropy S, respectively. The Gibbs entropy in the <math>G(N,p)</math> ensemble is given by:<ref>{{cite journal |last1=Bogacz |first1=Leszek |last2=Burda |first2=Zdzisław |last3=Wacław |first3=Bartłomiej |title=Homogeneous complex networks |journal=Physica A: Statistical Mechanics and Its Applications |date=1 July 2006 |volume=366 |pages=587–607 |doi=10.1016/j.physa.2005.10.024 |arxiv=cond-mat/0502124 |bibcode=2006PhyA..366..587B |s2cid=119428248 |url=https://www.sciencedirect.com/science/article/pii/S0378437105011180 |language=en |issn=0378-4371}}</ref>

<math display="block">{N}\Sigma = \log\left(\begin{matrix}\cfrac{N(N-1)}{2}\\L\end{matrix}\right)</math>

For <math>G(N,p)</math> ensemble,

<math display="block">{p}_{ij} = p = \cfrac{2L}{N(N-1)}</math>

Inserting <math>p_{ij}</math> into the Shannon entropy:<ref name=highlight/>

<math display="block">\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]</math>

The relation indicates that the Gibbs entropy <math>\Sigma</math> and the Shannon entropy per node S/N of random graphs are equal in the thermodynamic limit <math>N\to\infty</math>.

== References ==

Network Entropy