Alex Ng, Department of Engineering, University of Oxford

Abstract: A network structural evolution scheme is developed to construct a network configuration for any level of robustness, constrained by one or more other network properties. The scheme operates by first constructing a Minimum Spanning Tree to connect all nodes, then adding additional links, subject to a halting condition that tests both the achievement of the desired level of robustness, and the rate of approach to the desired level. The resulting algorithm has complexity of order O(n2), which compares well with previous work in this field, O(n!). Three evolution strategies for identifying links to be added to the tree are tested and compared against a number of different performance criteria. Applications of this work in telephone and distribution networks are considered.