Drexel University Home Pagewww.drexel.edu DREXEL UNIVERSITY LIBRARIES HOMEPAGE >>

iDEA: Drexel E-repository and Archives > Drexel Theses and Dissertations > Drexel Theses and Dissertations > Finding groups of graphs in databases

Please use this identifier to cite or link to this item: http://hdl.handle.net/1860/179

Title: Finding groups of graphs in databases
Authors: Peabody, Mitchell
Keywords: Computer science;Engineering models;Graphic methods;Spectral graph theory;Solid model databases
Issue Date: 28-Jul-2003
Abstract: Presented with a database of solid models, the task is to group the solid models together by similarity. This similarity can be defined in a number of ways, including topological or feature interaction. It turns out that both of these similarity metrics can be represented by undirected, simple graphs, and the problem can be abtracted to grouping graphs by similarity. To do this, a metric that captures the differences in graphs is needed. Unfortunately, known metrics are $NP$-Hard to calculate. In this thesis, I further expand on an approximate similarity metric known as $\lambda$-distance and propose a way to handle cospectral graphs. In addition, I use a well established clustering algorithm to graphs these graphs into clusters. I use techniques from information theory to measure the quality of results on controlled datasets of random graphs. This work is applied to the problem of grouping a set of solid models.
URI: http://dspace.library.drexel.edu/handle/1860/179
Appears in Collections:Drexel Theses and Dissertations

Files in This Item:

File Description SizeFormat
Peabody_Mitchell.pdf1.29 MBAdobe PDFView/Open
View Statistics

Items in iDEA are protected by copyright, with all rights reserved, unless otherwise indicated.


Valid XHTML 1.0! iDEA Software Copyright © 2002-2010  Duraspace - Feedback