Graph clustering with overlap.
Published: 2006
Language: eng
Number of pages: 86
ISBN-13: 9780494210703
Description: Given a graph G = (V, E), a  clustering of G is a set   C  of subsets of V which induces a set of subgraphs  C1,C2,...,Ck . These subgraphs are known as clusters. The study of graph clustering focuses on finding clusterings such that edges within clusters are maximized and those between different clusters are minimized, so that each cluster represents a grouping of highly interrelated nodes.Traditionally the study of graph clustering has been restricted to the case where every vertex v &isin; V is a member of exactly one cluster. We extend consideration to the case of  overlapping clusters, where each vertex may participate in an arbitrary number of clusters. We develop metrics for measuring the quality of an overlapping clustering, and a new stochastic local search algorithm for finding good overlapping clusterings. Finally we obtain experimental results showing the applicability of overlapping-clustering, and our algorithm, to some important applications.
Notes: Source: Masters Abstracts International, Volume: 45-03, page: 1544.

Advisor: Rudi Mathon.

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

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

ROBARTS MICROTEXT copy on microfiche.