Graph entropy is a collective name for several entropy-like quantities attached to a graph. Two important but distinct constructions are Körner graph entropy, which arose in information theory, and structural graph entropies obtained from partitions of graph elements (Dehmer and Mowshowitz 2011).
For a finite graph 
with vertex set 
and a probability distribution
, let 
be the vertex-packing polytope: the convex
hull of the 0-1 vectors of the independent
vertex sets of 
.
An equivalent finite-dimensional definition of Körner graph entropy is
 |
A term with 
is taken to be 0, while a vector with 
and 
makes the objective
function infinite (Csiszár et al. 1990, Simonyi 1995). Operationally,
graph edges specify pairs of source symbols that must
be distinguished, and 
is the optimal asymptotic coding rate in bits per symbol
(Körner 1973, Simonyi 1995).
For the empty graph 
, 
, while for the complete
graph 
,
is the Shannon
entropy 
.
Maximizing over 
gives 
,
where 
is the fractional chromatic number
(Simonyi 1995). Körner graph entropy is distinct from the Shannon
capacity of a graph, although both arose in zero-error
information theory.
A common structural construction starts with a finite set 
associated with a graph
and an equivalence rule 
that partitions it into equivalence classes 
. Its partition entropy is
 |
For example, 
may be the vertex set and the equivalence
classes may be the orbits of the automorphism
group; this gives a classical measure of structural information content (Mowshowitz
1968, Dehmer and Mowshowitz 2011). If the graph represents
a molecule, 
may instead consist of graph vertices, graph
edges, or selected fragments, with equivalence
classes determined by chemistry. The resulting quantities describe how a molecule's
atoms and bonds are arranged (Sabirov and Shepelevich 2021).
Many other definitions apply Shannon entropy to distributions derived from vertex degrees, graph distances, graph spectra, or other graph data. In particular, applying von Neumann entropy to a suitably normalized Laplacian matrix gives a spectral graph entropy. Consequently, the phrase "graph entropy" should be accompanied by the definition in use (Dehmer and Mowshowitz 2011).
In the Season 4 episode "Black Swan" of the television crime drama NUMB3RS, the character Amita Ramanujan refers to graph entropies while studying a map of Los Angeles.
