グラフエントロピー

情報理論において、グラフエントロピーとは、特定の値のペアが混同される可能性のあるチャネルを介してシンボルを通信することによって達成可能な情報速度の尺度です。^[1]この尺度は、1970年代にケルナーによって初めて導入され、^{[2] [3]}それ以来、組合せ論を含む他の設定でも有用であることが証明されています。^[4]

を無向グラフとする。 のグラフエントロピーは次のように定義される 。${\displaystyle G=(V,E)}$${\displaystyle G}$${\displaystyle H(G)}$

${\displaystyle H(G)=\min_{X,Y}I(X;Y)}$

ここで、はから一様に選ばれ、は G の独立集合にわたって分布し、との結合分布は確率 1 で となるようなものであり、 はとの相互情報量である。^[5]${\displaystyle X}$${\displaystyle V}$${\displaystyle Y}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle X\in Y}$${\displaystyle I(X;Y)}$${\displaystyle X}$${\displaystyle Y}$

つまり、における独立した頂点集合を とすると、における最小の相互情報量を持つ結合分布を見つけたいのですが、その条件は (i) 最初の項の周辺分布が一様であり、 (ii) 分布からのサンプルにおいて、 2 番目の項にはほぼ確実に最初の項が含まれます。との相互情報量は のエントロピーと呼ばれます。 ${\displaystyle {\mathcal {I}}}$${\displaystyle G}$${\displaystyle X,Y}$${\displaystyle V\times {\mathcal {I}}}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle G}$

• 単調性。 が同じ頂点集合上ののサブグラフである場合、 となります。${\displaystyle G_{1}}$${\displaystyle G_{2}}$${\displaystyle H(G_{1})\leq H(G_{2})}$
• 劣加法性。同じ頂点集合上の2 つのグラフとが与えられた場合、グラフの和は を満たします。${\displaystyle G_{1}=(V,E_{1})}$${\displaystyle G_{2}=(V,E_{2})}$ ${\displaystyle G_{1}\cup G_{2}=(V,E_{1}\cup E_{2})}$${\displaystyle H(G_{1}\cup G_{2})\leq H(G_{1})+H(G_{2})}$
• 互いに素な和集合の算術平均。 を、それぞれ頂点を持つ互いに素な頂点集合上のグラフのシーケンスとします。このとき、 となります。${\displaystyle G_{1},G_{2},\cdots ,G_{k}}$${\displaystyle n_{1},n_{2},\cdots ,n_{k}}$${\displaystyle 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})}}$

さらに、グラフの特定のファミリ クラスには簡単な数式が存在します。

• 完全バランスk部グラフはエントロピーを持つ。特に、 ${\displaystyle \log_{2}k}$
  • エッジのないグラフにはエントロピーがあります。${\displaystyle 0}$
  • 頂点上の完全グラフにはエントロピーがあります。${\displaystyle n}$${\displaystyle \log_{2}n}$
  • 完全バランス二部グラフにはエントロピーがあります。${\displaystyle 1}$
• 一方のパーティションに頂点があり、もう一方のパーティションに頂点がある完全二部グラフにはエントロピー があり、ここで はバイナリ エントロピー関数です。${\displaystyle n}$${\displaystyle m}$${\displaystyle H\left({\frac {n}{m+n}}\right)}$${\displaystyle H}$

ここでは、グラフ エントロピーの特性を使用して、頂点上の完全グラフは二部グラフより少ないグラフの和集合として表現できないことを簡単に証明します。 ${\displaystyle G}$${\displaystyle n}$${\displaystyle \log_{2}n}$

証明単調性により、2 部グラフは によって境界が定められる完全 2 部グラフよりも大きなグラフ エントロピーを持つことはできません。したがって、劣加法性により、2 部グラフの和集合は よりも大きなエントロピーを持つことはできません。ここで、 を頂点上の完全グラフとします。上記の特性により、 です。したがって、 より少ない 2 部グラフの和集合はと同じエントロピーを持つことはできないため、そのような和集合として表現することはできません。${\displaystyle 1}$${\displaystyle k}$${\displaystyle k}$${\displaystyle G=(V,E)}$${\displaystyle n}$${\displaystyle H(G)=\log _{2}n}$${\displaystyle \log_{2}n}$${\displaystyle G}$${\displaystyle G}$${\displaystyle \blacksquare}$

• Matthias Dehmer、Frank Emmert-Streib、Zengqiang Chen、Xueliang Li、Yongtang Shi (2016 年 7 月 25 日)。グラフエントロピーの数学的基礎と応用。Wiley。ISBN 978-3-527-69325-2。