Back to search

University of Southampton

A Morse-theoretical clustering algorithm for annotated networks and spectral bounds for fuzzy clustering

Abstract

dc:description.abstract

Given a set of objects X a clustering algorithm is a formal procedure that groups together objects which are similar and separates the ones which are not, thus mimicking the human ability to categorise and group together objects. Clustering algorithms have been growing for decades and clustering has become a standard data analytic technique for many fields. Standard clustering methods however fail to integrate object metadata, often readily available to the user, in the analysis.<br/><br/> We present in this thesis a novel clustering algorithm, called Morse, which integrates metadata information and Morse theory, a well-known topological theory, to reveal the "basins of attraction" induced by the metadata. The algorithm is described in its general form together with a study of its performance on the LFR benchmark model. We tested Morse in a real-world scenario and showed it helped to identify phenotypes of asthma based on blood gene expression profiles. We also looked at Morse in the axiomatic setting proposed by Kleinberg and introduce a novel axiom, Monotonic Consistency, that avoids the widely-reported problematic behaviour of Kleinberg's Consistency, and a possibility result for Monotonic Consistency given again by Morse. Furthermore, we extended Kleinberg's axiomatic setting to graph clustering and proved an impossibility result for Consistency, and a possibility result for Monotonic Consistency given again by Morse.<br/><br/> Lastly, we explored how a general clustering algorithm affects the structure of a graph using a graph spectral distance. In this direction, we proved two different bounds for such distance with respect a graph and its quotient graph induced by a hard partition, and generalised these results to fuzzy partitions.

Degree

thesis:*
Name dc:type.qualificationname
Ph.D.
Level dc:type.qualificationlevel
doctoral
Grantor dc:publisher.institution
University of Southampton
Year dc:date.issued
2018

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Strazzeri, Fabio
Advisor dc:contributor.advisor
  • Sanchez Garcia, Ruben
ORCID person:identifier.orcid

Rights

Language dc:language
English, eng

Chain of custody

source
Harvested from
University of Southampton
Base URL
eprints.soton.ac.uk/cgi/oai2
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Strazzeri, Fabio. A Morse-theoretical clustering algorithm for annotated networks and spectral bounds for fuzzy clustering. doctoral thesis, University of Southampton, 2018.