I am having trouble getting some intuition as to what graph entropy measures. The definition that I have is that given a graph $G$, $H(G) = \min_{X,Y}I(X ;Y)$, where $X$ is a uniformly random vertex in $G$ and $Y$ is an independent set containing $X$. Also, $I(X; Y)$ is the mutual information between $X$ and $Y$ defined by: $I(X; Y) = H(X) - H(X|Y)$, where $H$ is the regular entropy function.
First, could anyone provide some intuition as to what this is actually measuring? Also, if we are taking the minimum of both $X$ and $Y$, why does $X$ have to be a uniformly random vertex? If we are minimizing $I$, then there is some fixed vertex $X$ and independent set $Y$ such that $I$ is minimized. So why is there a notion of uniformly random vertex?
Thanks!
EDIT: I am using these notes as a reference for a reading group:
$\endgroup$2 Answers
$\begingroup$$X$ is the source with maximal entropy (uniform distribution), and $Y$ is the set of distinguishable symbols (distinguishability is given by the edges). Graph entropy is trying to quantify the encoding capacity of such system for an arbitrary $Y$.
$\endgroup$ 4 $\begingroup$This paper shows that any definition of Graph Entropy will fail and cannot be well defined [1608.05972] Low Algorithmic Complexity Entropy-deceiving Graphs It also explains what and how one can measure the Entropy of a graph, and even more interesting, gives some pointers on how to measure the algorithmic complexity and causal content of graphs, including some of other of my papers that you may want to look for.
One must be very careful with Entropy, both measuring it and as a concept. When measuring Entropy one is required to make arbitrary decisions, some can be circumvented, such as the granularity unit by taking what is called the Entropy rate (basically taking into consideration all possible granularities) but some other limitations are insurmountable. For example, one has to make an arbitrary choice on how to describe events, because Entropy is NOT invariant to the way you may describe the same object! And this is even a much greater limitation to the common and generally acknowledged limitation that for Entropy to be measured and make any sense one has to know the domain of the problem, i.e. all other objects or events in the set of interest and their distribution, to which Entropy is also not independent.
Entropy is, however, an extremely simple function, it basically counts (with a logarithm involved) the number of things that have certain property or the number of features of interest, and nothing more.
In summary, while Entropy is an interesting measure, intended originally to only quantify the size of a communication channel, it is not an intrinsic property of an object or event as it depends on a distribution, but furthermore, it can give contradictory values as you change the description of the same object, without losing or anything any information in the descriptions, and is, therefore a very fragile and not universal measure that has largely been used and abused.
$\endgroup$
