Graph entropy explained
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.[1] This measure, first introduced by Körner in the 1970s,[2] [3] has since also proven itself useful in other settings, including combinatorics.[4]
Definition
Let
be an undirected graph. The graph entropy of
, denoted
is defined as
where
is chosen
uniformly from
,
ranges over
independent sets of G, the joint distribution of
and
is such that
with probability one, and
is the
mutual information of
and
.
[5] That is, if we let
denote the independent vertex sets in
, we wish to find the joint distribution
on
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
and
is then called the entropy of
.
Properties
is a subgraph of
on the same vertex set, then
.
- Subadditivity. Given two graphs
and
on the same set of vertices, the graph union
satisfies
H(G1\cupG2)\leqH(G1)+H(G2)
.
- Arithmetic mean of disjoint unions. Let
be a sequence of graphs on disjoint sets of vertices, with
vertices, respectively. Then
H(G1\cupG2\cup … Gk)=
ni}\sum
{niH(Gi)}
.
Additionally, simple formulas exist for certain families classes of graphs.
. In particular,
- Edge-less graphs have entropy
.
vertices have entropy
.
.
vertices in one partition and
in the other have entropy
, where
is the
binary entropy function.
Example
Here, we use properties of graph entropy to provide a simple proof that a complete graph
on
vertices cannot be expressed as the union of fewer than
bipartite graphs.
Proof By monotonicity, no bipartite graph can have graph entropy greater than that of a complete bipartite graph, which is bounded by
. Thus, by sub-additivity, the union of
bipartite graphs cannot have entropy greater than
. Now let
be a complete graph on
vertices. By the properties listed above,
. Therefore, the union of fewer than
bipartite graphs cannot have the same entropy as
, so
cannot be expressed as such a union.
General References
Notes and References
- Book: Matthias Dehmer. Abbe Mowshowitz. Frank Emmert-Streib. Advances in Network Complexity. 21 June 2013. John Wiley & Sons. 978-3-527-67048-2. 186–.
- Körner. János. 1973. Coding of an information source having ambiguous alphabet and the entropy of graphs.. 6th Prague Conference on Information Theory. 411–425.
- Book: Niels da Vitoria Lobo. Takis Kasparis. Michael Georgiopoulos. Structural, Syntactic, and Statistical Pattern Recognition: Joint IAPR International Workshop, SSPR & SPR 2008, Orlando, USA, December 4-6, 2008. Proceedings. 24 November 2008. Springer Science & Business Media. 978-3-540-89688-3. 237–.
- Book: Bernadette Bouchon. Bernadette Bouchon-Meunier . Lorenza Saitta. Lorenza Saitta . Ronald R. Yager. 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. 8 June 1988. Springer Science & Business Media. 978-3-540-19402-6. 112–.
- G. Simonyi, "Perfect graphs and graph entropy. An updated survey," Perfect Graphs, John Wiley and Sons (2001) pp. 293-328, Definition 2”