Comparing networks using their fine structure

Abstract

We introduce a novel technique for characterising networks using the structure of their sub-graphs, which we call the network's fine structure. To judge the similarities between networks we use the earth mover's distance between the distributions of features of their constituent sub-graphs. This technique is an abstraction of graph edit-distance. Given these similarity measures we explore their use in hierarchical clustering on several networks derived from a variety of sources including social interaction data.