Back to search

University of British Columbia

Multiobjective graph clustering with variable neighbourhood descent

Abstract

dc:description

Graph clustering is a well-known combinatorial problem that appears in many different incarnations. The task is to partition the vertex set of a graph in order to minimize a given cost function. Clustering has applications in VLSI design, protein-protein interaction networks, data mining and many other areas. In the context of multiobjective optimization, we have more than one cost function, and instead of finding a single optimal solution, we are interested in a set of Pareto-optimal solutions. We present a multiobjective variable neighbourhood descent algorithm for this problem and its results on a collection of synthetic and real world data. On data sets that have a known "correct" clustering, our algorithm consistently finds interesting unsupported solutions (those that can not be found by any linear single-objective restriction of the problem), demonstrating a clear advantage of the multiobjective approach. Additionally, the shape of the Pareto front generated by the algorithm can give clues for the areas of the cost function space that contain non-trivial solutions. We compare our method to a single-objective clustering algorithm (RNSC, [41]) and a multiobjective algorithm (MOCK, [27]). On all data sets, our algorithm requires substantially longer CPU time, but produces higher quality results.

Degree

thesis:*
Name thesis:degree_name
Master of Science - MSc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
University of British Columbia
Year dc:date
2005

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Naverniouk, Igor

Rights

dc:rights
Statement dc:rights
  • For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/16364

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Naverniouk, Igor. Multiobjective graph clustering with variable neighbourhood descent. master's thesis, University of British Columbia, 2005. http://hdl.handle.net/2429/16364