# Test Problems and Representations for Graph Evolution

### Daniel Ashlock, Justin Schonfeld, Lee-Ann Barlow, and Colin Lee

Submitted to SSCI 2014

Graph evolution - evolving a graph or network to fit specific
criteria - is a recent enterprise because of the difficulty of
representing a graph in an easily evolvable form. Simple, obvious
representations such as adjacency matrices can prove to be very hard
to evolve and some easy-to-evolve representations place severe limits
on the space of graphs that is explored. This study fills in a gap in
the literature by presenting two scalable families of benchmark
functions. These functions are tested on a number of
representations. The first family of benchmark functions is matching
the eccentricity sequences of graphs, the second is locating graphs
that are relatively easy to color non-optimally. One hundred examples
of the eccentricity sequence matching problem are tested. The examples
have a difficulty, measured in time to solution, that varies through
four orders of magnitude, demonstrating that this test problem
exhibits scalability even within a particular size of problem. The
ordering by problem hardness, for different representations, varies
significantly from representation to representation. For the difficult
coloring problem, a parameter study is presented demonstrating that
the problem exhibits very different results for different algorithm
parameters, demonstrating its effectiveness as a benchmark problem.