Código de barras de un gráfico

Usando homología persistente, podemos analizar la forma (topológica) de una nube de puntos usando el siguiente método de tres pasos:

• convertir el conjunto de puntos en un complejo simplicial (y hay algunas formas diferentes de hacerlo) parametrizado por un parámetro de "ruido"
• Calcule los grupos de homología de este complejo (nuevamente parametrizado por el parámetro)
• Mire la evolución de los grupos a medida que evoluciona el parámetro.

El "tiempo de vida" de los diferentes grupos parece una colección de intervalos, que se llama el "código de barras" de la forma.

¿Existe una explicación fácil de cómo se ve el código de barras si el complejo simplicial es simplemente un esqueleto 1 (es decir, un gráfico)? En otras palabras, supongamos que comenzamos con un gráfico (en lugar de un conjunto de puntos) y luego hacemos los dos pasos restantes como se indicó anteriormente.

Betti-0 será un intervalo para cada vértice, y uno de los intervalos involucrados desaparecerá cada vez que un borde conecte dos componentes. Esto será muy similar a la traza de un Union-Find que se ejecuta en el gráfico.

Betti-1 será un intervalo para cada ciclo cerrado esencial; correspondiente a una base actualizada actualizada para el Cycle Space . Como se trata de un gráfico, estos aparecerán cada vez que se agregue un borde que no conecte dos componentes disjuntos y que nunca vuelva a desaparecer.

El gráfico ya es un complejo simplicial compuesto por 0 y 1 simplices (nodos y aristas). La representación del código de barras es significativa solo cuando el complejo simplicial se construye paso a paso de manera que el complejo en el paso k es un subconjunto del complejo en el paso k + 1, es decir, los vértices y bordes se insertan en él en algún orden.

Suponiendo que los vértices se agregan en "tiempo" / "valor de parámetro" 0 y todos los bordes se agregan en "tiempo" / "valor de parámetro" 1: el código de barras betti_0 simplemente será un conjunto de líneas que representa el número de componentes disjuntos de el gráfico y betti_1 serán simplemente un conjunto de líneas que representan cada bucle "básico" en el gráfico (ver el espacio del ciclo de un gráfico).

Hay varias formas de construir tales funciones de ordenamiento en un gráfico, por ejemplo, calcular cualquier función sobre los vértices (digamos el grado de cualquier vértice) y decir que los vértices con grados más bajos nacen antes que los vértices con un grado más alto. Ahora digamos que se agrega un borde cada vez que ambos vértices llegan a existir. Ahora, puede construir una vista de homología persistente del gráfico dado bajo la distribución de grados. Se pueden construir muchas otras funciones similares, por ejemplo, pagerank, laplacians, etc.

Lo que se dijo anteriormente es correcto, pero agregaré una arruga interesante que debería ser mejor conocida.

Si usa la distancia del gráfico como parámetro de persistencia y luego calcula la persistencia del complejo Rips, también puede encontrar una homología dimensional más alta. Por ejemplo, los números de persistencia betti para N puntos igualmente espaciados en un círculo se ven así:

$$\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}$$

(donde el número de persistencia betti solo significa contar el número de barras de cualquier longitud que aparecen en cada dimensión)

La distinción entre esta situación y la pregunta que se hace es que no estoy filtrando el gráfico, sino que persisto en el espacio métrico abstracto que se obtiene por las distancias al borde del gráfico.