1.2 Entropy or the Information Content of Graphs

Given a decomposition of the vertices or edges of a graph, one can construct a finite probability scheme [10] and compute its entropy. A finite probability scheme assigns a probability to each subset in the decomposition. Such a numerical measure can be seen to capture the information contained in some particular aspect of the graph structure.

The orbits of the automorphism group of a graph constitute a decomposition of the vertices of the graph. As noted above, this decomposition captures the symmetry structure of the graph, and the entropy of the finite probability scheme obtained from the automorphism group provides an index of the complexity of the graph relative to the symmetry structure.

Let G = (V, E) be a graph with vertex set V (with |V | = n) and edge set E. The automorphism group of G, denoted by Aut(G), is the set of all adjacency preserving bijections of V. Let{Vi |1 ≤ ik} be the collection of orbits of Aut(G), and suppose |Vi | = ni for 1 ≤ ik. The entropy or information content of G is given by the following formula ([13]):


For example, the orbits of the graph of Figure 1.1 are {1}, {2,5}, and {3,4}, so the information content of the graph is images.

Figure 1.1 Information content of a graph.

Clearly, Ia(G) satisfies ...

Get Analysis of Complex Networks now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.