Graph entropy: Difference between revisions

Revision as of 17:03, 19 June 2019

Latest revision as of 06:20, 15 May 2024

(5 intermediate revisions by 3 users not shown)

Line 1:

In [[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 conferenceConference on informationInformation theoryTheory|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==

Line 16:

Additionally, simple formulas exist for certain families classes of graphs.

* EdgeComplete balanced [[Multipartite graph|k-lesspartite graphs]] have entropy <math>0\log_2 k</math>. In particular,

** [[CompleteEdge-less graph]]s on <math>n</math> verticesgraphs have entropy <math>\log_2 n0</math>, where <math>\log_2</math> is the [[binary logarithm]].

* Complete balanced* [[MultipartiteComplete graph|k-partite graphs]]s have entropyon <math>\lg kn</math> where <math>lg</math> is the binary logarithm. In particular, complete balanced [[bipartite graphs]]vertices have entropy <math>1\log_2 n</math>.

** Complete balanced [[bipartite graphs]] have entropy <math>1</math>.

* Complete [[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]].

==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>\lglog_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) = \lglog_2 n</math>. Therefore, the union of fewer than <math>\lglog_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==