Morse Theory and an Impossibility Theorem for Graph Clustering

  • 2019-07-18 15:34:19
  • Fabio Strazzeri, Rubén J. Sánchez-García
  • 0

Abstract

Kleinberg introduced three natural clustering properties, or axioms, andshowed they cannot be simultaneously satisfied by any clustering algorithm. Wepresent a new clustering property, Monotonic Consistency, which avoids thewell-known problematic behaviour of Kleinberg's Consistency axiom, and theimpossibility result. Namely, we describe a clustering algorithm, MorseClustering, inspired by Morse Theory in Differential Topology, which satisfiesKleinberg's original axioms with Consistency replaced by Monotonic Consistency.Morse clustering uncovers the underlying flow structure on a set or graph andreturns a partition into trees representing basins of attraction of criticalvertices. We also generalise Kleinberg's axiomatic approach to sparse graphs,showing an impossibility result for Consistency, and a possibility result forMonotonic Consistency and Morse clustering.

 

Quick Read (beta)

loading the full paper ...