Graph clustering with restricted neighbourhood search.
Published: 2004
Language: eng
Number of pages: 99
Description: The object of this thesis is to outline the graph clustering problem and its applications, and to present the RNSC algorithm and its results in detail along with promising avenues of future research.Given a graph G = (V, E), a clustering of G is a partitioning of V that induces a set of subgraphs  C1, C2, ...,  Ck. These subgraphs are known as clusters. A good clustering induces clusters that are both dense and sparsely inter-connected, and represents a natural grouping of the vertices into highly interrelated sets.By assigning cost functions to the set of clusterings of a graph, we can apply local search techniques to the clustering problem in order to find a solution of low cost. We employ a specialized local search method to create the RNSC (Restricted Neighbourhood Search Clustering) algorithm, a new randomized algorithm that generates significantly lower-cost clusterings than previous approaches.
Notes: Adviser:  Rudi Mathon.

Thesis (M.Sc.)--University of Toronto, 2004.

Electronic version licensed for access by U. of T. users.

Source: Masters Abstracts International, Volume: 43-03, page: 0880.

MICR copy on microfiche (2 microfiches).