There are many definitions of graph entropy, my favorite is very well described in the work of J.Körner: Coding of an information source having ambiguous alphabet and the entropy of graphs (1973).
Why Graph Entropy is so important?
Based on the main concept of entropy the following assumptions are true:
* The entropy of a graph should be a functional of the stability of the structure (so that it depicts in some way the distribution of the edges of the graph).
* Sub sets of vertexes quite isolated from the rest of the graph are characterized by a high stability (low entropy).
* It's quite easy use the entropy as a measure for graph clustering.