Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

3 Answers 3

up vote 9 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
    
so if I understand correctly the complex at "time" t is the induced graph on all vertices at distance at most $t$ from some canonical vertex ? –  Suresh Venkat May 16 at 6:00
1  
A time t we connect all vertices at a distance t from each other, but we also build the rest of the rips complex. That is, what you described is the one-complex of the rips complex at level t - if a triple of vertices is connected we automatically add a face etc. It's relatively straight forward to work out the N=6 case with a pen and paper picture. –  Anthony Bak May 16 at 21:03
    
@SureshVenkat - I realized that I misread your comment. There is no canonical vertex. If you want to think just about the one-skeleton (the graph) I'm saying that you for each vertex add in edges to all vertices within distance t (distance in the original graph). You also add in higher dimensional simplices if all of their faces are already included. –  Anthony Bak May 19 at 18:18
    
@DavidRicherby - I think you misread my answer. –  Anthony Bak May 19 at 18:20
    
@AnthonyBak You're right -- sorry. I'd still recommend a rephrase, though, since the order of answers changes as they receive votes. That means that what was above when you wrote the answer isn't necessarily above when somebody comes to read it. –  David Richerby May 19 at 20:14
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.