Topological Data Analysis

Analyze graph topology using Betti numbers, persistent homology, and the Mapper algorithm.

Topological Data Analysis (TDA) reveals the "shape" of data using tools from algebraic topology. In dependency graphs, TDA identifies cycles, holes, and the overall connectivity structure.

Betti Numbers

Betti numbers count the topological features at each dimension.

Definition

Formulas

For a graph treated as a 1-dimensional simplicial complex:

$\beta_0 = \text{number of connected components}$

$\beta_1 = |E| - |V| + \beta_0$

This follows from Euler's formula for the Euler characteristic:

$\chi = |V| - |E| = \beta_0 - \beta_1$

Cyclomatic Complexity

$M = |E| - |V| + 2\beta_0$

Measures the number of independent paths through the graph. Higher values indicate more complex control flow.

Interpretation in Lean

Persistent Homology

Persistent homology tracks how topological features appear and disappear as we "grow" the graph through a filtration.

Filtration

A filtration is a nested sequence of subgraphs:

$G_0 \subseteq G_1 \subseteq \cdots \subseteq G_n = G$

Astrolabe supports three filtration types:

Birth-Death Diagram

Each topological feature has:

• Birth time: When the feature appears
• Death time: When the feature merges or fills in
• Persistence: death - birth

Features with high persistence are "real" structure; low persistence are noise.

Parameters

Output

{
  "persistence_diagrams": {
    "0": [{"birth": 0.0, "death": 0.3, "persistence": 0.3}],
    "1": [{"birth": 0.5, "death": 0.8, "persistence": 0.3}]
  },
  "betti_curve": [{"threshold": 0.1, "beta_0": 5, "beta_1": 2}],
  "summary": {"total_features": 42, "long_lived_features": 7}
}

Persistence Entropy

Persistence entropy measures the diversity of topological feature lifespans.

Formula

$H = -\sum_i p_i \log(p_i)$

Where p_i = persistence_i / Σ persistence_j

Interpretation

Persistence Landscape

Persistence landscapes provide a stable vectorization of persistence diagrams for machine learning.

Construction

For each persistence pair (b, d) and parameter t:

$\Lambda(t) = \max(0, \min(t - b, d - t))$

This creates "tent" functions over each feature.

Parameters

Use Case

Landscapes can be used as feature vectors for:

• Comparing graph structures
• Clustering similar projects
• Anomaly detection

Mapper Algorithm

The Mapper algorithm creates a simplified topological skeleton of the graph by combining filtration, covering, and clustering.

Algorithm

1. Filter: Compute a function f: V → ℝ (degree, PageRank, closeness, or depth)
2. Normalize: Scale values to [0, 1]
3. Cover: Create overlapping intervals
4. Cluster: Within each interval, find connected components
5. Connect: Link clusters that share original nodes

Parameters

Filter Functions

Output

The Mapper graph is a simplified representation:

{
  "mapper_nodes": [
    {"id": 0, "interval": 2, "members": ["node1", "node2"], "size": 2}
  ],
  "mapper_edges": [
    {"source": 0, "target": 1, "weight": 1}
  ],
  "summary": {
    "num_mapper_nodes": 15,
    "num_mapper_edges": 20,
    "mapper_beta_1": 3
  }
}

Interpretation in Lean

Application Example

Consider analyzing a Lean project's dependency structure:

1. Betti numbers: β₀ = 1 (connected), β₁ = 5 (has cycles)
2. Persistent homology: Long-lived H₀ features reveal major components
3. Mapper with PageRank: Shows hierarchy from core theorems to applications

API Endpoints

GET /api/project/analysis/topology        # Betti numbers and Euler characteristic
GET /api/project/analysis/mapper          # Mapper algorithm
GET /api/project/analysis/geometry        # Includes persistent homology (if GUDHI available)