A distance metric between directed weighted graphs

Directed weighted graphs are increasingly used to model complex systems and interactions, such as networks of interconnected physical or biological subsystems. The analysis of these graphs often requires some form of dissimilarity, or distance measure to compare graphs. In this paper, we extend connectivity-based dissimilarity measures previously used to compare unweighted undirected graphs of the same dimensions to: (1) directed weighted graphs of the same dimensions and (2) directed weighted graphs of different dimensions. To our knowledge, this is the first approach proposed for comparing two graphs containing different numbers of nodes. We derive the conditions under which this dissimilarity measure is a pseudo-metric. This derivation provides new insights on our algorithms (previously proposed) for the graph aggregation optimization problem.