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.5 Alternative Bases for Structural Complexity

Colorings of a graph can be used to obtain a decomposition of the vertices. Sets of vertices of the same color (or independent sets) constitute equivalence classes. Unlike the orbits of the automorphism group, a partition of the vertices obtained in this way is not unique. However, an information measure may be defined by taking the minimum value over some set of decompositions linked to colorings [16]. This section explores such a measure, compares it with the symmetry-based measure, and shows its relationship to the graph entropy as defined in [11].

A coloring of a graph is an assignment of colors to the vertices so that no two adjacent vertices have the same color.

An n-coloring of a graph G = (V, E) is a coloring with n colors or, more precisely, a mapping f of V onto the set {1, 2,..., n} such that whenever [u, v] ∈ E, f(u) ≠ f(v).

The chromatic number κ(G) of a graph G is the smallest value of n for which there is an n-coloring. A graph may have more than one n-coloring.

An n-coloring is complete if, for every i, j with ij, there exist adjacent vertices u and v such that f(u) = i and f(v) = j.

A decomposition images of the set of vertices V is called a chromatic decomposition of G if u, vVi imply that [u, v] ∉ E. Note that Vi in a chromatic decomposition is a set of independent vertices. If f is an n-coloring, the collection of ...

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