Graph entropy

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. This measure, first introduced by Körner, has since also proven itself useful in other settings.

Definition

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

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

where $X$ is chosen uniformly from $V$, $Y$ is an independent set in G, and $I(X;Y)$ is the mutual information of $X$ and $Y$.

Properties

• Monotonicity. If $G_{1}$ is a subgraph of $G_{2}$ on the same vertex set, then $H(G_{1})\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}\cup G_{2}=(V,E_{1}\cup E_{2})$ satisfies $H(G_{1}\cup G_{2})\leq H(G_{1})+H(G_{2})$.
• Arithmetic mean of disjoint unions. Let $G_{1},G_{2},\cdots \cup G_{k}$ be a sequence of graphs on disjoint sets of vertices, with $n_{1},n_{2},\cdots ,n_{k}$ vertices, respectively. Then $H(G_{1}\cup G_{2}\cup \cdots G_{k})={\tfrac {1}{\sum _{i=1}^{k}n_{i}}}\sum {n_{i}H(G_{i})}$.

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

• Edge-less graphs have entropy $0$.
• Complete graphs on $n$ vertices have entropy $\lg n$, where $\lg$ is the binary logarithm.
• Complete balanced k-partite graphs have entropy $\lg r$ where $r$ is the binary logarithm. In particular, complete balanced bipartite graphs have entropy $1$.
• Complete bipartite graphs with $n$ vertices in one partition and $m$ in the other have entropy $H\left({\frac {n}{m+n}}\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 $\lg 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)=\lg n$. Therefore, the union of fewer than $\lg n$ bipartite graphs cannot have the same entropy as $G$, so $G$ cannot be expressed as such a union. $\blacksquare$

General References

Lecture notes on graph entropy.