|
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
|
Items in iDEA are protected by copyright, with all rights reserved, unless otherwise indicated.
|
www.drexel.edu
