Optimal hierarchical clustering on a graph

Gökçe Kahvecioğlu, David P. Morton*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

Given an undirected graph with positive weights on the edges we study a parametric biobjective graph clustering problem. We remove a subset of edges to break the graph into smaller pieces, that is, connected components, or clusters. We seek to maximize the number of clusters while minimizing the weight of the removed edges. We identify nested solutions that lie on the concave envelope of the efficient frontier, yielding a hierarchical family of clusters, in strongly polynomial time. We demonstrate the performance of our approach on a graph defined by the schedule of football teams within the National Collegiate Athletic Association, which has a known hierarchical structure, and on a set of synthetic graphs generated from a stochastic block model with embedded hierarchical structure.

Original languageEnglish (US)
JournalNetworks
DOIs
StateAccepted/In press - 2021

Keywords

  • discrete optimization
  • hierarchical clustering
  • multiobjective optimization

ASJC Scopus subject areas

  • Information Systems
  • Computer Networks and Communications

Fingerprint

Dive into the research topics of 'Optimal hierarchical clustering on a graph'. Together they form a unique fingerprint.

Cite this