Development of Graph Clustering Algorithms
M.S. Plan B Project Report
Sushrut S. Karanjkar
Id. No - 1826347
Project Advisor: Dr. George Karypis
Department of Computer Science
University of Minnesota
Minneapolis, MN
April 21, 1998
Abstract
Clustering algorithms group a given set of objects into a set of classes i.e.
clusters, such that the intra-cluster connectivity is maximized and
the inter-cluster connectivity is minimized. A lot of problems in the
area of Data Mining and VLSI-CAD can be formulated as graph based
problems. Thus the problem of clustering can effectively be mapped
onto the problem of clustering the graph. Motivated by this, two
schemes for graph based clustering are proposed in this report. The
effectiveness of the schemes is tested by conducting experiments on
two data sets namely, Web Documents data and Stock Market Data. The
results are presented in two contexts viz. graph theoretical context
and data mining context, where the labels of the data items are known
a-priori. The results are also compared with two already known
schemes.
Acknowledgments
First of all I would like to thank Prof. George Karypis for his excellent guidance, invaluable suggestions and personal involvement in this project. I would like to thank Prof. Vipin Kumar for numerous encouraging discussions and also for being my mentor for all the time. Thanks are due to Prof. Sapatnekar for being a member of the examination committee. Finally, I would like to thank Aparna for all her help and support for this project