# Graph entropy

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Graph_entropy
> Markdown URL: https://mediated.wiki/source/Graph_entropy.md
> Source: https://en.wikipedia.org/wiki/Graph_entropy
> Source revision: 1320447899
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

In [information theory](/source/information_theory), the '''graph entropy''' is a measure of the information rate achievable by communicating symbols over a channel in which certain pairs of values may be confused.<ref name="DehmerMowshowitz2013">{{cite book|author1=Matthias Dehmer|author2=Abbe Mowshowitz|author3=Frank Emmert-Streib|title=Advances in Network Complexity|url=https://books.google.com/books?id=fHxARaCPTKwC&pg=PT186|date=21 June 2013|publisher=John Wiley & Sons|isbn=978-3-527-67048-2|pages=186–}}</ref> This measure, first introduced by Körner in the 1970s,<ref>{{cite journal|last=Körner|first=János|date=1973|title=Coding of an information source having ambiguous alphabet and the entropy of graphs.|journal=6th Prague Conference on Information Theory|pages= 411–425}}</ref><ref name="LoboKasparis2008">{{cite book|author1=Niels da Vitoria Lobo|author2=Takis Kasparis|author3=Michael Georgiopoulos|title=Structural, Syntactic, and Statistical Pattern Recognition: Joint IAPR International Workshop, SSPR & SPR 2008, Orlando, USA, December 4-6, 2008. Proceedings|url=https://books.google.com/books?id=DWZc9Ti_vBwC&pg=PA237|date=24 November 2008|publisher=Springer Science & Business Media|isbn=978-3-540-89688-3|pages=237–}}</ref> has since also proven itself useful in other settings, including combinatorics.<ref name="BouchonSaitta1988">{{cite book|author1=Bernadette Bouchon|author1-link= Bernadette Bouchon-Meunier |author2=Lorenza Saitta|author2-link= Lorenza Saitta |author3=Ronald R. Yager|title=Uncertainty and Intelligent Systems: 2nd International Conference on Information Processing and Management of Uncertainty in Knowledge Based Systems IPMU '88. Urbino, Italy, July 4-7, 1988. Proceedings|url=https://books.google.com/books?id=V5-6G433s_wC&pg=PA112|date=8 June 1988|publisher=Springer Science & Business Media|isbn=978-3-540-19402-6|pages=112–}}</ref>

==Definition==
Let <math>G = (V, E)</math> be an [undirected graph](/source/undirected_graph). The graph entropy of <math>G</math>, denoted <math>H(G)</math> is defined as

::<math>H(G) = \min_{X,Y} I(X ; Y)</math>

where <math>X</math> is chosen [uniformly](/source/Discrete_uniform_distribution) from <math>V</math>, <math>Y</math> ranges over [independent sets](/source/Independent_set_(graph_theory)) of G, the joint distribution of <math>X</math> and <math>Y</math> is such that <math>X\in Y</math> with probability one, and <math>I(X ; Y)</math> is the [mutual information](/source/mutual_information) of <math>X</math> and <math>Y</math>.<ref>G. Simonyi, "Perfect graphs and graph entropy. An updated survey," Perfect Graphs, John Wiley and Sons (2001) pp. 293-328, Definition 2”</ref> 

That is, if we let <math>\mathcal{I}</math> denote the independent vertex sets in <math>G</math>, we wish to find the joint distribution <math>X,Y</math> on <math>V \times \mathcal{I}</math> with the lowest mutual information such that (i) the [marginal distribution](/source/marginal_distribution) of the first term is uniform and (ii) in samples from the distribution, the second term contains the first term almost surely. The mutual information of <math>X</math> and <math>Y</math> is then called the entropy of <math>G</math>.

==Properties==
* Monotonicity. If <math>G_1</math> is a subgraph of <math>G_2</math> on the same vertex set, then <math>H(G_1) \leq H(G_2)</math>.
* Subadditivity. Given two graphs <math>G_1 = (V, E_1)</math> and <math>G_2 = (V, E_2)</math> on the same set of vertices, the [graph union](/source/Graph_operations) <math>G_1 \cup G_2 = (V, E_1 \cup E_2)</math> satisfies <math>H(G_1 \cup G_2) \leq H(G_1) + H(G_2)</math>.
* Arithmetic mean of disjoint unions. Let <math>G_1, G_2, \cdots, G_k</math> be a sequence of graphs on [disjoint sets](/source/disjoint_sets) of vertices, with <math>n_1, n_2, \cdots, n_k</math> vertices, respectively. Then <math>H(G_1 \cup G_2 \cup \cdots G_k) = \tfrac{1}{\sum_{i=1}^{k}n_i}\sum_{i=1}^{k}{n_i H(G_i)}</math>.

Additionally, simple formulas exist for certain families classes of graphs.
* Complete balanced [k-partite graphs](/source/Multipartite_graph) have entropy <math>\log_2 k</math>. In particular, 
** Edge-less graphs have entropy <math>0</math>.
** [Complete graph](/source/Complete_graph)s on <math>n</math> vertices have entropy <math>\log_2 n</math>.
** Complete balanced [bipartite graphs](/source/bipartite_graphs) have entropy <math>1</math>.
* Complete [bipartite graphs](/source/bipartite_graphs) with <math>n</math> vertices in one partition and <math>m</math> in the other have entropy <math>H\left(\frac{n}{m+n}\right)</math>, where <math>H</math> is the [binary entropy function](/source/binary_entropy_function).

==Example==
Here, we use properties of graph entropy to provide a simple proof that a complete graph <math>G</math> on <math>n</math> vertices cannot be expressed as the union of fewer than <math>\log_2 n</math> bipartite graphs.

''Proof'' By monotonicity, no bipartite graph can have graph entropy greater than that of a complete bipartite graph, which is bounded by <math>1</math>. Thus, by sub-additivity, the union of <math>k</math> bipartite graphs cannot have entropy greater than <math>k</math>. Now let <math>G = (V, E)</math> be a complete graph on <math>n</math> vertices. By the properties listed above, <math>H(G) = \log_2 n</math>. Therefore, the union of fewer than <math>\log_2 n</math> bipartite graphs cannot have the same entropy as <math>G</math>, so <math>G</math> cannot be expressed as such a union. <math>\blacksquare</math>

==General References==
*{{cite book|author1=Matthias Dehmer|author2=Frank Emmert-Streib|author3=Zengqiang Chen |author4=Xueliang Li |author5=Yongtang Shi |title=Mathematical Foundations and Applications of Graph Entropy|url=https://books.google.com/books?id=CZ-_DAAAQBAJ|date=25 July 2016|publisher=Wiley|isbn=978-3-527-69325-2}}

==Notes==
{{reflist}}

Category:Information theory
Category:Graph theory

---
Adapted from the Wikipedia article [Graph entropy](https://en.wikipedia.org/wiki/Graph_entropy) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Graph_entropy?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.