Small-Graph Matching and Building Genotypes

This paper introduces a new method, known as small-graph matching, and demonstrates how it may be used to determine the genotype signature of a sample of buildings. First, the origins of the method and its relationship to other ‘similarity’ testing techniques are discussed. Then the range of possible actions and transformations are established through the creation of a set of rules. The next section of the paper suggests which real-world actions would be represented by such transformations, were the graph representing a building. By considering the real-world equivalent actions, as opposed to transformations at the level of the graph abstraction, a system of costs or weightings is developed and subsequently applied to the range of possible actions. Next, in order to fully explain this method, a technique of normalizing the similarity measure is presented in order to permit the comparison of graphs of differing magnitude. The last stage of this method is presented, this being the comparison of all possible graph pairs within a given sample and the mean distance calculated for all individual graphs. This results in the identification of a genotype signature. Finally, the paper presents an empirical application of this method and shows how effective it is, not only for the identification of a building genotype, but also for assessing the homogeneity of a sample or subsamples.