O'Reilly logo

Analysis of Complex Networks by Frank Emmert-Streib, Matthias Dehmer

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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]):

images

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required