On Diffusion Character Matrices

Thumbnail Image
Lee, Colin R.
Journal Title
Journal ISSN
Volume Title
University of Guelph

Graphs or networks are ubiquitous and useful mathematical objects, but comparing graphs can be computationally expensive and problematic for certain applications. This thesis introduces diffusion character matrices which are a way of transforming adjacency matrices of graphs in a useful manner for graph comparison. This thesis examines some mathematical theory behind diffusion character matrices, and investigates some of their applications. Diffusion character matrices are a useful way of generating graph invariants, and this thesis demonstrates that they can be used as a witness that graphs are non-isomorphic, can drastically reducing the number of permutations that need to be tested when computing the automorphism group of a graph, and can be used to construct useful pseudometrics on graphs. The primary application of diffusion character matrices examined in this thesis is the use of diffusion character based pseudometrics for distinguishing between different distributions of graphs. Several diffusion character based pseudometrics on graphs are used to provide statistical evidence that samples of graphs evolved to exhibit different epidemiological properties are drawn from different distributions of graphs. It is shown that for graph based epidemiological applications several diffusion character based pseudometrics are quite good at distinguishing between distributions of graphs.

graph theory, pseudometrics, diffusion character matrices, pseudometric embedding, combinatorial graphs, evolutionary computation