Barcode of a graph

Question

Using persistent homology, we can analyze the (topological) shape of a cloud of points using the following three-step method:

• convert the point set into a simplicial complex (and there are a few different ways of doing this) parameterized by a "noise" parameter
• Compute the homology groups of this complex (again parameterized by the parameter)
• look at the evolution of the groups as the parameter evolves.

The "time of life" of the different groups looks like a collection of intervals, which is called the "barcode" of the shape.

Is there an easy explanation of what the barcode looks like if the simplicial complex is merely a 1-skeleton (i.e a graph) ? In other words, suppose we start with a graph (rather than a point set) and then do the remaining two steps as above.

Answer 1

Betti-0 will be one interval for each vertex, with one of the involved intervals vanishing any time an edge connects two components. This will be very similar to a trace of a Union-Find running on the graph.

Betti-1 will be one interval for each essential closed loop; corresponding to a running updated basis for the Cycle Space. Since it is a graph, these will appear whenever an edge is added that does not connect two disjoint components, and never disappear again.

Answer 2

The graph is already a simplicial complex comprising of 0 and 1 simplices (nodes and edges). The barcode representation is meaningful only when the simplicial complex is constructed step-by-step such that the complex at step k is a subset of the complex at step k+1 i.e. the vertices and edges are inserted into it in some order.

Assuming that the vertices are added at "time"/"paramter value" 0 and all the edges are added at "time"/"parameter value" 1: the betti_0 barcode will simply be a set of lines representing the number of disjoint components of the graph and betti_1 will simply be a set of lines representing each "basic" loop in the graph (see cycle space of a graph).

There are several ways of constructing such ordering functions on a graph e.g. compute any function over the vertices (say the degree of any vertex) and say that vertices with lower degrees are 'born' before the vertices with higher degree. Now say that an edge is added whenever both the vertices come to exist. Now, you can construct a persistent homology view of the given graph under the degree distribution. Many other such functions can be constructed e.g. pagerank, laplacians etc.

Answer 3

What is said above is correct but I'll add an interesting wrinkle that should be better known.

If you use the graph distance as your persistence parameter and then calculate the persistence of the Rips complex you can actually find higher dimensional homology as well. For instance the persistence betti numbers for N points equally space on a circle look like:

$$ \begin{array}{*{27}{l}} N & b1 & b2 & b3 & b4 & b5 & b6 & b7 & b8 & b9 & b10 & b11 & b12 \\ 3 & & & & & & & & & & & \\ 4 & 1 & & & & & & & & & & \\ 5 & 1 & & & & & & & & & & \\ 6 & 1 & 1 & & & & & & & & & \\ 7 & 1 & & & & & & & & & & \\ 8 & 1 & 0 & 1& & & & & & & & & \\ 9 & 1 & 2 & & & & & & & & & \\ 10 & 1 & 0 & 0 & 1 & & & & & & & \\ 11 & 1 & 0 & 1 & & & & & & & & \\ 12 & 1 & 3 & 0 & 0 & 1 & & & & & & \\ 13 & 1 & 0 & 1 & & & & & & & & \\ 14 & 1 & 0 & 1 & 0 & 0 & 1 & & & & & \\ 15 & 1 & 4 & 0 & 2 & & & & & & & & \\ 16 & 1 & 0 & 1 & 0 & 0 & 0 &1 & & & & \\ 17 & 1 & 0 & 1 & 0 & 1 & & & & & & & \\ 18 & 1 & 5 & 1 & 0 & 0 & 0 & 0 & 1 & & & \\ \end{array} $$

(where persistence betti number just means count the number of bars of any length that appear in each dimension)

The distinction between this situation and the asked question is that I'm not filtering the graph - instead I'm persisting on the abstract metric space that is realized by the graph edge distances.