Graph entropy

 ( Information Theory ) 

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.

(2013). 9783527670482, John Wiley & Sons. . ISBN 9783527670482

This measure, first introduced by Körner in the 1970s,

(2008). 9783540896883, Springer Science & Business Media. . ISBN 9783540896883

has since also proven itself useful in other settings, including combinatorics.

(1988). 9783540194026, Springer Science & Business Media. . ISBN 9783540194026

---

Definition Let $G\; =\; (V,\; E)$ be an undirected graph. The graph entropy of $G$, denoted $H(G)$ is defined as

:$H(G)\; =\; \backslash min\_\{X,Y\}\; I(X\; ;\; Y)$

where $X$ is chosen uniformly from $V$, $Y$ ranges over independent sets of G, the joint distribution of $X$ and $Y$ is such that $X\backslash in\; Y$ with probability one, and $I(X\; ;\; Y)$ is the mutual information of $X$ and $Y$.G. Simonyi, "Perfect graphs and graph entropy. An updated survey," Perfect Graphs, John Wiley and Sons (2001) pp. 293-328, Definition 2”

That is, if we let $\backslash mathcal\{I\}$ denote the independent vertex sets in $G$, we wish to find the joint distribution $X,Y$ on $V\; \backslash times\; \backslash mathcal\{I\}$ with the lowest mutual information such that (i) the 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 $X$ and $Y$ is then called the entropy of $G$.

---

Properties

• Monotonicity. If $G\_1$ is a subgraph of $G\_2$ on the same vertex set, then $H(G\_1)\; \backslash leq\; H(G\_2)$.
• Subadditivity. Given two graphs $G\_1\; =\; (V,\; E\_1)$ and $G\_2\; =\; (V,\; E\_2)$ on the same set of vertices, the graph union $G\_1\; \backslash cup\; G\_2\; =\; (V,\; E\_1\; \backslash cup\; E\_2)$ satisfies $H(G\_1\; \backslash cup\; G\_2)\; \backslash leq\; H(G\_1)\; +\; H(G\_2)$.
• Arithmetic mean of disjoint unions. Let $G\_1,\; G\_2,\; \backslash cdots,\; G\_k$ be a sequence of graphs on disjoint sets of vertices, with $n\_1,\; n\_2,\; \backslash cdots,\; n\_k$ vertices, respectively. Then $H(G\_1\; \backslash cup\; G\_2\; \backslash cup\; \backslash cdots\; G\_k)\; =\; \backslash tfrac\{1\}\{\backslash sum\_\{i=1\}^\{k\}n\_i\}\backslash sum\_\{i=1\}^\{k\}\{n\_i\; H(G\_i)\}$.

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

• Complete balanced k-partite graphs have entropy $\backslash log\_2\; k$. In particular,
• Edge-less graphs have entropy $0$.
• on $n$ vertices have entropy $\backslash log\_2\; n$.
• Complete balanced bipartite graphs have entropy $1$.
• Complete bipartite graphs with $n$ vertices in one partition and $m$ in the other have entropy $H\backslash left(\backslash frac\{n\}\{m+n\}\backslash right)$, where $H$ is the binary entropy function.

---

Example Here, we use properties of graph entropy to provide a simple proof that a complete graph $G$ on $n$ vertices cannot be expressed as the union of fewer than $\backslash log\_2\; n$ bipartite graphs.

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

---

General References

• (2016). 9783527693252, Wiley. . ISBN 9783527693252

---

Notes

Post Comment