Distances between directed networks and applications

Abstract

Networks which show the relationships within and between complex systems are key tools in a variety of current scientific areas. A central aim in network analysis is to find a suitable metric for network similarity and comparison. We propose a definition for the space of all networks, and show that our definition leads to a natural and meaningful notion of distance between networks. We discuss the computational complexity involved in computing our network distance, and develop lower bounds by using invariants of networks that are significantly simpler to compute. By constructing a wide range of explicit examples, we show that these lower bounds are effective in distinguishing between networks. We describe multiple invariants and prove that all of them are stable in a quantitative sense.