Cluster Persistence for Weighted Graphs

Area of Science:

• Computational Topology
• Graph Theory
• Data Analysis

Background:

• Persistent homology is a key tool for analyzing topological features of weighted graphs, particularly their 0-dimensional homology.
• Existing methods often provide limited signatures for connected components and can be sensitive to noise.
• There is a need for advanced filtration techniques in persistent homology for robust cluster analysis.

Purpose of the Study:

• To develop a new filtration method for cluster analysis using persistent homology on weighted graphs.
• To introduce non-trivial birth times for richer topological signatures of connected components.
• To enhance robustness against outliers in graph-based cluster analysis.

Main Methods:

• A novel filtration is constructed for weighted graphs based on persistent homology.
• The method prioritizes nodes that become part of sufficiently large clusters, effectively ignoring outliers initially.
• The approach focuses on 0-dimensional homology to capture connectivity patterns.

Main Results:

• The new filtration yields richer topological signatures for connected components by incorporating non-trivial birth times.
• The proposed method demonstrates significant robustness to outliers in the data.
• Computational efficiency and practical effectiveness were demonstrated on random graphs.

Conclusions:

• The developed persistent homology filtration offers an advanced tool for cluster analysis in weighted graphs.
• Its ability to provide richer signatures and outlier robustness makes it valuable for complex network analysis.
• The method shows promise for applications in various fields dealing with graph-structured data.