Finding groups of graphs in databases
Mitchell Peabody, William Clement Regli, William Clement Regli · 2002
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.