Entropie grafu - Graph entropy

v teorie informace, entropie grafu je míra informační rychlosti dosažitelné komunikací symbolů po kanálu, ve které mohou být zaměňovány určité páry hodnot.^[1] Toto opatření, poprvé zavedené Körnerem v 70. letech,^[2]^[3] od té doby se osvědčil i v jiných nastaveních, včetně kombinatoriky.^[4]

Definice

Nechat ${ displaystyle G = (V, E)}$ být neorientovaný graf. Entropie grafu ${ displaystyle G}$ , označeno ${ displaystyle H (G)}$ je definován jako

{ displaystyle H (G) = min _ {X, Y} I (X; Y)}

kde ${ displaystyle X}$ je vybrán jednotně z ${ displaystyle V}$ , ${ displaystyle Y}$ pohybuje se nad nezávislé sady G, společná distribuce ${ displaystyle X}$ a ${ displaystyle Y}$ je takový ${ displaystyle X v Y}$ s pravděpodobností jedna a ${ displaystyle I (X; Y)}$ je vzájemné informace z ${ displaystyle X}$ a ${ displaystyle Y}$ .^[5]

Tedy pokud to necháme ${ displaystyle { mathcal {I}}}$ označit nezávislé vrcholy zapadá ${ displaystyle G}$ , přejeme si najít společnou distribuci ${ displaystyle X, Y}$ na ${ displaystyle V times { mathcal {I}}}$ s nejnižšími vzájemnými informacemi takovými, že (i) okrajové rozdělení prvního členu je jednotné a (ii) ve vzorcích z rozdělení druhý člen téměř jistě obsahuje první člen. Vzájemná informace o ${ displaystyle X}$ a ${ displaystyle Y}$ se pak nazývá entropie ${ displaystyle G}$ .

Vlastnosti

Monotónnost. Li ${ displaystyle G_ {1}}$ je podgrafem ${ displaystyle G_ {2}}$ na stejné množině vrcholů ${ displaystyle H (G_ {1}) leq H (G_ {2})}$ .
Subadditivita. Vzhledem ke dvěma grafům ${ displaystyle G_ {1} = (V, E_ {1})}$ a ${ displaystyle G_ {2} = (V, E_ {2})}$ na stejné sadě vrcholů je grafová unie ${ displaystyle G_ {1} pohár G_ {2} = (V, E_ {1} pohár E_ {2})}$ splňuje ${ displaystyle H (G_ {1} pohár G_ {2}) leq H (G_ {1}) + H (G_ {2})}$ .
Aritmetický průměr disjunktních unií. Nechat ${ displaystyle G_ {1}, G_ {2}, cdots, G_ {k}}$ být posloupnost grafů na nesouvislých množinách vrcholů, s ${ displaystyle n_ {1}, n_ {2}, cdots, n_ {k}}$ vrcholy. Pak ${ displaystyle H (G_ {1} pohár G_ {2} pohár cdots G_ {k}) = { tfrac {1} { součet _ {i = 1} ^ {k} n_ {i}}} sum _ {i = 1} ^ {k} {n_ {i} H (G_ {i})}}$ .

Kromě toho existují jednoduché vzorce pro třídy grafů určitých rodin.

Grafy bez okrajů mají entropii ${ displaystyle 0}$ .
Kompletní grafy na ${ displaystyle n}$ vrcholy mají entropii ${ displaystyle log _ {2} n}$ .
Úplně vyvážený k-partitové grafy mít entropii ${ displaystyle log _ {2} k}$ . Zejména úplné vyvážené bipartitní grafy mít entropii ${ displaystyle 1}$ .
Kompletní bipartitní grafy s ${ displaystyle n}$ vrcholy v jednom oddílu a ${ displaystyle m}$ v druhé mají entropii ${ displaystyle H left ({ frac {n} {m + n}} right)}$ , kde ${ displaystyle H}$ je funkce binární entropie.

Příklad

Zde používáme vlastnosti entropie grafu k poskytnutí jednoduchého důkazu, že je to úplný graf ${ displaystyle G}$ na ${ displaystyle n}$ vrcholy nelze vyjádřit jako spojení méně než ${ displaystyle log _ {2} n}$ bipartitní grafy.

Důkaz Podle monotónnosti žádný bipartitní graf nemůže mít entropii grafu větší než u úplného bipartitního grafu, který je ohraničen ${ displaystyle 1}$ . Sub-aditivitou tedy spojení ${ displaystyle k}$ bipartitní grafy nemohou mít entropii větší než ${ displaystyle k}$ . Teď nech ${ displaystyle G = (V, E)}$ být kompletní graf na ${ displaystyle n}$ vrcholy. Díky výše uvedeným vlastnostem ${ displaystyle H (G) = log _ {2} n}$ . Proto je spojení méně než ${ displaystyle log _ {2} n}$ bipartitní grafy nemohou mít stejnou entropii jako ${ displaystyle G}$ , tak ${ displaystyle G}$ nelze vyjádřit jako takový svazek. ${ displaystyle blacksquare}$

Obecné odkazy

Matthias Dehmer; Frank Emmert-Streib; Zengqiang Chen; Xueliang Li; Yongtang Shi (25. července 2016). Matematické základy a aplikace entropie grafů. Wiley. ISBN 978-3-527-69325-2.

Poznámky

^ Matthias Dehmer; Abbe Mowshowitz; Frank Emmert-Streib (21. června 2013). Pokroky ve složitosti sítě. John Wiley & Sons. str. 186–. ISBN 978-3-527-67048-2.
^ Körner, János (1973). "Kódování informačního zdroje s dvojznačnou abecedou a entropií grafů". 6. pražská konference o teorii informací: 411–425.
^ Niels da Vitoria Lobo; Takis Kasparis; Michael Georgiopoulos (24. listopadu 2008). Strukturální, syntaktické a statistické rozpoznávání vzorů: Společný mezinárodní seminář IAPR, SSPR a SPR 2008, Orlando, USA, 4. – 6. Prosince 2008. Sborník. Springer Science & Business Media. 237–. ISBN 978-3-540-89688-3.
^ Bernadette Bouchon; Lorenza Saitta; Ronald R. Yager (8. června 1988). Nejistota a inteligentní systémy: 2. mezinárodní konference o zpracování informací a řízení nejistoty ve znalostních systémech IPMU '88. Urbino, Itálie, 4. – 7. Července 1988. Sborník. Springer Science & Business Media. str. 112–. ISBN 978-3-540-19402-6.
^ G. Simonyi, "Perfektní grafy a entropie grafů. Aktualizovaný průzkum," Perfect Graphs, John Wiley and Sons (2001), str. 293-328, Definice 2 "

[DehmerMowshowitz2013-1] Matthias Dehmer; Abbe Mowshowitz; Frank Emmert-Streib (21. června 2013). Pokroky ve složitosti sítě. John Wiley & Sons. str. 186–. ISBN 978-3-527-67048-2.

[2] Körner, János (1973). "Kódování informačního zdroje s dvojznačnou abecedou a entropií grafů". 6. pražská konference o teorii informací: 411–425.

[LoboKasparis2008-3] Niels da Vitoria Lobo; Takis Kasparis; Michael Georgiopoulos (24. listopadu 2008). Strukturální, syntaktické a statistické rozpoznávání vzorů: Společný mezinárodní seminář IAPR, SSPR a SPR 2008, Orlando, USA, 4. – 6. Prosince 2008. Sborník. Springer Science & Business Media. 237–. ISBN 978-3-540-89688-3.

[BouchonSaitta1988-4] Bernadette Bouchon; Lorenza Saitta; Ronald R. Yager (8. června 1988). Nejistota a inteligentní systémy: 2. mezinárodní konference o zpracování informací a řízení nejistoty ve znalostních systémech IPMU '88. Urbino, Itálie, 4. – 7. Července 1988. Sborník. Springer Science & Business Media. str. 112–. ISBN 978-3-540-19402-6.

[5] G. Simonyi, "Perfektní grafy a entropie grafů. Aktualizovaný průzkum," Perfect Graphs, John Wiley and Sons (2001), str. 293-328, Definice 2 "

[1]

[2]

[3]

[4]

[5]