A study on compressing graphical structures

Many real-world systems such as the WWW, Semantic Web, logical expressions, and social networks can be represented in graphical forms. This paper studies compressing graphical structures from a graph entropy point of view. We show that structural entropy is equal to the chromatic entropy of the characteristic graph, termed the structural characteristic graph. We establish the relation between structural entropy and graph entropy, and investigate the cases when (conditional) graph entropy is equal to (conditional) chromatic entropy.