Representation and generation of plans using graph spectra
Sean Hanna · UCL Discovery (University College London) · 2007
Numerical comparison of spaces with one another is often achieved with set scalarmeasures such as global and local integration, connectivity, etc., which capture aparticular quality of the space but therefore lose much of the detail of its overallstructure. More detailed methods such as graph edit distance are difficult to calculate,particularly for large plans. This paper proposes the use of the graph spectrum, or theordered eigenvalues of a graph adjacency matrix, as a means to characterise the spaceas a whole. The result is a vector of high dimensionality that can be easily measuredagainst others for detailed comparison.Several graph types are investigated, including boundary and axial representations, asare several methods for deriving the spectral vector. The effectiveness of these isevaluated using a genetic algorithm optimisation to generate plans to match a givenspectrum, and evolution is seen to produce plans similar to the initial targets, even invery large search spaces. Results indicate that boundary graphs alone can capture thegross topological qualities of a space, but axial graphs are needed to indicate localrelationships. Methods of scaling the spectra are investigated in relation to both globallocal changes to plan arrangement. For all graph types, the spectra were seen tocapture local patterns of spatial arrangement even as global size is varied.